Definir, usando puntoCero, la función

   inversa :: (Double -> Double) -> Double -> Double

tal que inversa g x es el valor de la inversa de g en x. Por ejemplo,

   inversa (^2) 9  ==  3.000000002941184

Definir, usando inversa, las funciones raizCuadrada, raizCubica, arcoseno y arcocoseno que calculen la raíz cuadrada, la raíz cúbica, el arco seno y el arco coseno, respectivamente. Por ejemplo,

   raizCuadrada 9  ==  3.000000002941184
   raizCubica 27   ==  3.0000000000196048
   arcoseno 1      ==  1.5665489428306574
   arcocoseno 0    ==  1.5707963267949576

Leer más…

Los ceros de una función pueden calcularse mediante el método de Newton basándose en las siguientes propiedades:

• Si \(b\) es una aproximación para el punto cero de \(f\), entonces \[ b-\frac{f(b)}{f'(b)} \] donde \(f'\) es la derivada de \(f\), es una mejor aproximación.
• el límite de la sucesión \(x_n\) definida por \begin{align} x_0 &= 1 \newline x_{n+1} &= x_n-\frac{f(x_n)}{f'(x_n)} \end{align} es un cero de \(f\).

Definir la función

   puntoCero :: (Double -> Double) -> Double

tal que puntoCero f es un cero de la función f calculado usando la propiedad anterior. Por ejemplo,

   puntoCero cos  ==  1.5707963267949576

Leer más…

El método de Herón para calcular la raíz cuadrada de un número se basa en las siguientes propiedades:

• Si \(y\) es una aproximación de la raíz cuadrada de \(x\), entonces \[\frac{y+\frac{x}{y}}{2}\] es una aproximación mejor.
• El límite de la sucesión definida por \begin{align} x_{0} &= 1 \newline x_{n+1} &= \frac{x_n+\frac{x}{x_n}}{2} \end{align} es la raíz cuadrada de x.

Definir la función

   raiz :: Double -> Double

tal que raiz x es la raíz cuadrada de x calculada usando la propiedad anterior con una aproximación de 0.00001 y tomando como valor inicial 1. Por ejemplo,

   raiz 9  ==  3.000000001396984

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

   (  1  6 11  2 )
   (  7 12  3  8 )
   (  3  8  4  9 )

moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:

   [1,6,11,2,8,9]
   [1,6,11,3,8,9]
   [1,6,12,3,8,9]
   [1,7,12,3,8,9]
   [1,6,11,3,4,9]
   [1,6,12,3,4,9]
   [1,7,12,3,4,9]
   [1,6,12,8,4,9]
   [1,7,12,8,4,9]
   [1,7, 3,8,4,9]

La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

   caminoMaxSuma :: Matrix Int -> [Int]

tal que caminoMaxSuma m es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

   λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [1,7,12,8,4,9]
   λ> sum (caminoMaxSuma (fromList 500 500 [1..]))
   187001249

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

   (  1  6 11  2 )
   (  7 12  3  8 )
   (  3  8  4  9 )

moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:

   [1,6,11,2,8,9]
   [1,6,11,3,8,9]
   [1,6,12,3,8,9]
   [1,7,12,3,8,9]
   [1,6,11,3,4,9]
   [1,6,12,3,4,9]
   [1,7,12,3,4,9]
   [1,6,12,8,4,9]
   [1,7,12,8,4,9]
   [1,7, 3,8,4,9]

La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

   maximaSuma :: Matrix Int -> Int

tal que maximaSuma m es el máximo de las sumas de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia a derecha. Por ejemplo,

   λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   41
   λ> maximaSuma (fromList 800 800 [1..])
   766721999

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

   (  1  6 11  2 )
   (  7 12  3  8 )
   (  3  8  4  9 )

moviéndose en cada paso una casilla hacia la derecha o abajo, son los siguientes:

   [1,6,11,2,8,9]
   [1,6,11,3,8,9]
   [1,6,12,3,8,9]
   [1,7,12,3,8,9]
   [1,6,11,3,4,9]
   [1,6,12,3,4,9]
   [1,7,12,3,4,9]
   [1,6,12,8,4,9]
   [1,7,12,8,4,9]
   [1,7, 3,8,4,9]

Definir la función

   caminos :: Matrix Int -> [[Int]]

tal que caminos m es la lista de los caminos en la matriz m desde extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia la derecha o abajo. Por ejemplo,

   λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [[1,6,11,2,8,9],
    [1,6,11,3,8,9],
    [1,6,12,3,8,9],
    [1,7,12,3,8,9],
    [1,6,11,3,4,9],
    [1,6,12,3,4,9],
    [1,7,12,3,4,9],
    [1,6,12,8,4,9],
    [1,7,12,8,4,9],
    [1,7, 3,8,4,9]]
   λ> length (caminos (fromList 12 12 [1..]))
   705432

Leer más…

Se considera una retícula con sus posiciones numeradas, desde el vértice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la retícula de dimensión 3x4 se numera como sigue:

   |-------+-------+-------+-------|
   | (1,1) | (1,2) | (1,3) | (1,4) |
   | (2,1) | (2,2) | (2,3) | (2,4) |
   | (3,1) | (3,2) | (3,3) | (3,4) |
   |-------+-------+-------+-------|

Definir la función

   caminos :: (Int,Int) -> [[(Int,Int)]]

tal que caminos (m,n) es la lista de los caminos en la retícula de dimensión mxn desde (1,1) hasta (m,n). Por ejemplo,

   λ> caminos (2,3)
   [[(1,1),(1,2),(1,3),(2,3)],
    [(1,1),(1,2),(2,2),(2,3)],
    [(1,1),(2,1),(2,2),(2,3)]]
   λ> mapM_ print (caminos (3,4))
   [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)]
   [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)]
   [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)]
   [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)]
   [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)]
   [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)]
   [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)]
   [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)]
   [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)]
   [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)]

Leer más…

La distancia de Levenshtein (o distancia de edición) es el mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edición que se pueden hacer son:

• insertar un carácter (por ejemplo, de "abc" a "abca")
• eliminar un carácter (por ejemplo, de "abc" a "ac")
• sustituir un carácter (por ejemplo, de "abc" a "adc")

Por ejemplo, la distancia de Levenshtein entre "casa" y "calle" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro:

   "casa"  --> "cala"  (sustitución de 's' por 'l')
   "cala"  --> "calla" (inserción de 'l' entre 'l' y 'a')
   "calla" --> "calle" (sustitución de 'a' por 'e')

Definir la función

   levenshtein :: String -> String -> Int

tal que levenshtein xs ys es la distancia de Levenshtein entre xs e ys. Por ejemplo,

   levenshtein "casa"  "calle"    ==  3
   levenshtein "calle" "casa"     ==  3
   levenshtein "casa"  "casa"     ==  0
   levenshtein "ana" "maria"      ==  3
   levenshtein "agua" "manantial" ==  7

Leer más…

Si a una secuencia X de elementos (pongamos por ejemplo, le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, "aaoa" es una subsecuencia de la secuencia "amapola".

El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).

Dadas dos secuencias X e Y, decimos que Z es una subsecuencia de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = "amapola" e Y = "matamoscas", la secuencia "aaoa" es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 "maoa" o "amoa".

Definir la función

   scm :: Eq a => [a] -> [a] -> [a]

tal que scm xs ys es una de las subsecuencias comunes de longitud máxima de xs e ys. Por ejemplo,

   scm "amapola" "matamoscas" == "amoa"
   scm "atamos" "matamoscas"  == "atamos"
   scm "aaa" "bbbb"           == ""

Leer más…

Si a una secuencia X de elementos (pongamos por ejemplo, caracteres) le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, "aaoa" es una subsecuencia de la secuencia "amapola".

El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).

Dadas dos secuencias X e Y, decimos que Z es una subsecuencia común de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = "amapola" e Y = "matamoscas", la secuencia "aaoa" es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 "maoa" o "amoa".

Se desea encontrar la longitud de las subsecuencias comunes más largas de dos secuencias de caracteres dadas.

Definir la función

   longitudSCM :: Eq a => [a] -> [a] -> Int

tal que longitudSCM xs ys es la longitud de la subsecuencia máxima de xs e ys. Por ejemplo,

   longitudSCM "amapola" "matamoscas" == 4
   longitudSCM "atamos" "matamoscas"  == 6
   longitudSCM "aaa" "bbbb"           == 0

Leer más…