Ir al contenido principal

Representaciones de grafos

Misceláneas

Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo

1 ----- 2
| \     |
|  3    |
| /     |
4 ----- 5

se puede representar por la matriz de adyacencia

|0 1 1 1 0|
|1 0 0 0 1|
|1 0 0 1 0|
|1 0 1 0 1|
|0 1 0 1 0|

donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia

[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.

Definir las funciones

matrizAlista :: Matrix Int -> [(Int,[Int])]
listaAmatriz :: [(Int,[Int])] -> Matrix Int

tales que

  • (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por
ejMatriz :: Matrix Int
ejMatriz = fromLists [[0,1,1,1,0],
[1,0,0,0,1],
[1,0,0,1,0],
[1,0,1,0,1],
[0,1,0,1,0]]

se tiene que

λ> matrizAlista ejMatriz
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
  • (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,
λ> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
( 0 1 1 1 0 )
( 1 0 0 0 1 )
( 1 0 0 1 0 )
( 1 0 1 0 1 )
( 0 1 0 1 0 )
λ> matrizAlista it
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

Leer más…

Polinomios de Fibonacci

Misceláneas

La sucesión de polinomios de Fibonacci se define por

p(0) = 0
p(1) = 1
p(n) = x*p(n-1) + p(n-2)

Los primeros términos de la sucesión son

p(2) = x
p(3) = x^2 + 1
p(4) = x^3 + 2*x
p(5) = x^4 + 3*x^2 + 1

Definir la lista

sucPolFib :: [Polinomio Integer]

tal que sus elementos son los polinomios de Fibonacci. Por ejemplo,

λ> take 7 sucPolFib
[0,1,1*x,x^2 + 1,x^3 + 2*x,x^4 + 3*x^2 + 1,x^5 + 4*x^3 + 3*x]
λ> sum (map grado (take 3000 sucPolFib2))
4495501

Comprobar con QuickCheck que el valor del n-ésimo término de sucPolFib para x=1 es el n-ésimo término de la sucesión de Fibonacci 0, 1, 1, 2, 3, 5, 8, ...

Nota. Limitar la búsqueda a ejemplos pequeños usando

quickCheckWith (stdArgs {maxSize=5}) prop_polFib

Leer más…

El pasatiempo de Ulises

Misceláneas

Ulises, en sus ratos libres, juega a un pasatiempo que consiste en, dada una serie de números naturales positivos en una cola, sacar un elemento y, si es distinto de 1, volver a meter el mayor de sus divisores propios. Si el número que saca es el 1, entonces lo deja fuera y no mete ningún otro. El pasatiempo continúa hasta que la cola queda vacía.

Por ejemplo, a partir de una cola con los números 10, 20 y 30, el pasatiempo se desarrollaría como sigue:

C [30,20,10]
C [20,10,15]
C [10,15,10]
C [15,10,5]
C [10,5,5]
C [5,5,5]
C [5,5,1]
C [5,1,1]
C [1,1,1]
C [1,1]
C [1]
C []

Definir la función

numeroPasos :: Cola Int -> Int

tal que (numeroPasos c) es el número de veces que Ulises saca algún número de la cola c al utilizarla en su pasatiempo. Por ejemplo,

numeroPasos (foldr inserta vacia [30])        ==  4
numeroPasos (foldr inserta vacia [20])        ==  4
numeroPasos (foldr inserta vacia [10])        ==  3
numeroPasos (foldr inserta vacia [10,20,30])  ==  11

Leer más…

Caminos reducidos

Misceláneas

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]

Definir la función

reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

reducido []                              ==  []
reducido [N]                             ==  [N]
reducido [N,O]                           ==  [N,O]
reducido [N,O,E]                         ==  [N]
reducido [N,O,E,S]                       ==  []
reducido [N,O,S,E]                       ==  [N,O,S,E]
reducido [S,S,S,N,N,N]                   ==  []
reducido [N,S,S,E,O,N]                   ==  []
reducido [N,S,S,E,O,N,O]                 ==  [O]
reducido (take (10^7) (cycle [N,E,O,S])) ==  []

Nótese que en el penúltimo ejemplo las reducciones son

    [N,S,S,E,O,N,O]
--> [S,E,O,N,O]
--> [S,N,O]
--> [O]

Leer más…

Descomposiciones de N como sumas de 1, 3 ó 4.

Misceláneas

El número 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 ó 4:

5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 3
5 = 1 + 3 + 1
5 = 3 + 1 + 1
5 = 1 + 4
5 = 4 + 1

Definir las funciones

descomposiciones  :: Integer -> [[Integer]]
nDescomposiciones :: Integer -> Integer

tales que

  • (descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
λ> descomposiciones1 4
[[4],[3,1],[1,3],[1,1,1,1]]
λ> descomposiciones1 5
[[4,1],[1,4],[3,1,1],[1,3,1],[1,1,3],[1,1,1,1,1]]
λ> descomposiciones1 6
[[3,3],[4,1,1],[1,4,1],[1,1,4],[3,1,1,1],[1,3,1,1],[1,1,3,1],
[1,1,1,3],[1,1,1,1,1,1]]
  • (nDescomposiciones n) es el número de descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
nDescomposiciones 5                       ==  6
nDescomposiciones 10                      ==  64
nDescomposiciones 20                      ==  7921
nDescomposiciones 30                      ==  974169
length (show (nDescomposiciones (10^5)))  ==  20899

Nota: Se puede usar programación dinámica.

Leer más…

Caminos en un grafo

Misceláneas

Definir las funciones

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

tales que

  • (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,
λ> grafo [(2,4),(4,5)]
G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])
  • (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
[[1,3,5,7],[1,3,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
[[2,5,3,7],[2,5,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
[[1,3,5,2],[1,3,7,5,2]]
λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
[]
λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
109601

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo).

Leer más…

Problema del dominó

Misceláneas

Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.

Definir la función

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

tal que (domino fs) es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,

λ> domino [(1,2),(2,3),(1,4)]
[[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]
λ> domino [(1,2),(1,1),(1,4)]
[[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]
λ> domino [(1,2),(3,4),(2,3)]
[[(1,2),(2,3),(3,4)]]
λ> domino [(1,2),(2,3),(5,4)]
[]
λ> domino [(x,y) | x <- [1..2], y <- [x..2]]
[[(2,2),(2,1),(1,1)],[(1,1),(1,2),(2,2)]]
λ> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
λ> mapM_ print (domino [(x,y) | x <- [1..3], y <- [x..3]])
[(1,3),(3,3),(3,2),(2,2),(2,1),(1,1)]
[(1,2),(2,2),(2,3),(3,3),(3,1),(1,1)]
[(2,2),(2,3),(3,3),(3,1),(1,1),(1,2)]
[(3,3),(3,2),(2,2),(2,1),(1,1),(1,3)]
[(2,3),(3,3),(3,1),(1,1),(1,2),(2,2)]
[(2,1),(1,1),(1,3),(3,3),(3,2),(2,2)]
[(3,3),(3,1),(1,1),(1,2),(2,2),(2,3)]
[(3,2),(2,2),(2,1),(1,1),(1,3),(3,3)]
[(3,1),(1,1),(1,2),(2,2),(2,3),(3,3)]
λ> length (domino [(x,y) | x <- [1..3], y <- [x..3]])
9
λ> length (domino [(x,y) | x <- [1..4], y <- [x..4]])
0
λ> length (domino [(x,y) | x <- [1..5], y <- [x..5]])
84480

Leer más…

El algoritmo de Damm

Misceláneas

El algoritmo de Damm se usa en la detección de errores en códigos numéricos. Es un procedimiento para obtener un dígito de control, usando la siguiente matriz, como describimos en los ejemplos

  |  0   1   2   3   4   5   6   7   8   9
--+---------------------------------------
0 |  0   3   1   7   5   9   8   6   4   2
1 |  7   0   9   2   1   5   4   8   6   3
2 |  4   2   0   6   8   7   1   3   5   9
3 |  1   7   5   0   9   8   3   4   2   6
4 |  6   1   2   3   0   4   5   9   7   8
5 |  3   6   7   4   2   0   9   5   8   1
6 |  5   8   6   9   7   2   0   1   3   4
7 |  8   9   4   5   3   6   2   0   1   7
8 |  9   4   3   8   6   1   7   2   0   5
9 |  2   5   8   1   4   3   6   7   9   0

Ejemplo 1: cálculo del dígito de control de 572

  • se comienza con la fila 0 y columna 5 de la matriz -> 9
  • a continuación, la fila 9 y columna 7 de la matriz -> 7
  • a continuación, la fila 7 y columna 2 de la matriz -> 4

con lo que se llega al final del proceso. Entonces, el dígito de control de 572 es 4.

Ejemplo 2: cálculo del dígito de control de 57260

  • se comienza con la fila 0 y columna 5 de la matriz -> 9
  • a continuación, la fila 9 y columna 7 de la matriz -> 7
  • a continuación, la fila 9 y columna 2 de la matriz -> 4
  • a continuación, la fila 6 y columna 4 de la matriz -> 5
  • a continuación, la fila 5 y columna 0 de la matriz -> 3

con lo que se llega al final del proceso. Entonces, el dígito de control de 57260 es 3.

Representamos las matrices como tablas cuyos índices son pares de números naturales.

type Matriz a = Array (Int,Int) a

Definimos la matriz:

mDamm :: Matriz Int
mDamm = listArray ((0,0),(9,9)) [0,3,1,7,5,9,8,6,4,2,
                                 7,0,9,2,1,5,4,8,6,3,
                                 4,2,0,6,8,7,1,3,5,9,
                                 1,7,5,0,9,8,3,4,2,6,
                                 6,1,2,3,0,4,5,9,7,8,
                                 3,6,7,4,2,0,9,5,8,1,
                                 5,8,6,9,7,2,0,1,3,4,
                                 8,9,4,5,3,6,2,0,1,7,
                                 9,4,3,8,6,1,7,2,0,5,
                                 2,5,8,1,4,3,6,7,9,0]

Definir la función

digitoControl :: Int -> Int

tal que (digitoControl n) es el dígito de control de n. Por ejemplo:

digitoControl 572          == 4
digitoControl 57260        == 3
digitoControl 12345689012  == 6
digitoControl 5724         == 0
digitoControl 572603       == 0
digitoControl 123456890126 == 0

Comprobar con QuickCheck que si añadimos al final de un número n su dígito de control, el dígito de control del número que resulta siempre es 0.

Leer más…

El problema de la bicicleta de Turing

Misceláneas

Cuentan que Alan Turing tenía una bicicleta vieja, que tenía una cadena con un eslabón débil y además uno de los radios de la rueda estaba doblado. Cuando el radio doblado coincidía con el eslabón débil, entonces la cadena se rompía.

La bicicleta se identifica por los parámetros (i,d,n) donde

  • i es el número del eslabón que coincide con el radio doblado al empezar a andar,
  • d es el número de eslabones que se desplaza la cadena en cada vuelta de la rueda y
  • n es el número de eslabones de la cadena (el número n es el débil).

Si i = 2, d = 7 y n = 25, entonces la lista con el número de eslabón que toca el radio doblado en cada vuelta es

[2,9,16,23,5,12,19,1,8,15,22,4,11,18,0,7,14,21,3,10,17,24,6,...

Con lo que la cadena se rompe en la vuelta número 14.

Definir las funciones

eslabones :: Int -> Int -> Int -> [Int]
numeroVueltas :: Int -> Int -> Int -> Int

tales que

  • (eslabones i d n) es la lista con los números de eslabones que tocan el radio doblado en cada vuelta en una bicicleta de tipo (i,d,n). Por ejemplo,
take 10 (eslabones 2 7 25)  ==  [2,9,16,23,5,12,19,1,8,15]
  • (numeroVueltas i d n) es el número de vueltas que pasarán hasta que la cadena se rompa en una bicicleta de tipo (i,d,n). Por ejemplo,
numeroVueltas 2 7 25  ==  14

Leer más…

Grafo de divisibilidad

Misceláneas

El grafo de divisibilidad de orden n es el grafo cuyos nodos son los números naturales entre 1 y n, cuyas aristas son los pares (x,y) tales que x divide a y o y divide a x y el coste de cada arista es el cociente entre su mayos y menor elemento.

Definir las siguientes funciones:

grafoDivisibilidad :: Int -> Grafo Int Int
coste :: Int -> Int

tales que

  • (grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo,
λ> grafoDivisibilidad 12
G ND (array (1,12)
            [(1,[(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),
                 (8,8),(9,9),(10,10),(11,11),(12,12)]),
             (2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]),
             (3,[(1,3),(6,2),(9,3),(12,4)]),
             (4,[(1,4),(2,2),(8,2),(12,3)]),
             (5,[(1,5),(10,2)]),
             (6,[(1,6),(2,3),(3,2),(12,2)]),
             (7,[(1,7)]),
             (8,[(1,8),(2,4),(4,2)]),
             (9,[(1,9),(3,3)]),
             (10,[(1,10),(2,5),(5,2)]),
             (11,[(1,11)]),
             (12,[(1,12),(2,6),(3,4),(4,3),(6,2)])])
  • (coste n) es el coste del árbol de expansión mínimo del grafo de divisibilidad de orden n. Por ejemplo,
coste 12    ==  41
coste 3000  ==  605305

Leer más…