En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los ejercicios de la 6ª relación que amplía la codificación César vista en clase para incluir las mayúsculas.
Los ejercicios, y sus soluciones, se muestran a continuación
Read More “I1M2012: Ejercicios sobre el cifrado César”
En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell de siguiente problema
Calcular el menor número natural n, mayor que 1, tal que para cualquier número entero x se verifique que x y xⁿ terminan en el mismo dígito.
La especificación matemática del enunciado es
min {n∈ℕ | n>1 ∧ ∀x∈ℤ (U(xⁿ) = U(x))}
donde U(x) es el último dígito de x. La especificación se puede reducir a
min {n∈ℕ | n>1 ∧ ∀x∈{0,…,9} (U(xⁿ) = U(x))}
Su traducción a Haskell es
|
1 2 3 |
solP3 :: Integer solP3 = head [n | n <- [2..], and [ultimo (x^n) == ultimo x | x <- [0..9]]] |
donde (ultimo x) es el último dígito de x
|
1 2 |
ultimo :: Integer -> Integer ultimo x = x `rem` 10 |
La solución del problema se calcula con
|
1 2 |
ghci> solP3 5 |
Se puede generalizar solP3 a una función solP3′ que calcula todos los números naturales n, mayores que 1, tales que para cualquier número entero x se verifique que x y xⁿ terminan en el mismo dígito. Para ello, basta eliminar head en la definición de solP3
|
1 2 3 |
solP3' :: [Integer] solP3' = [n | n <- [2..], and [ultimo (x^n) == ultimo x | x <- [0..9]]] |
El cálculo de los 20 primeros es
|
1 2 |
ghci> take 20 solP3' [5,9,13,17,21,25,29,33,37,41,45,49,53,57,61,65,69,73,77,81] |
Se observa que forman una progresión aritmética de diferencia 4. Basándonos en esta observación se puede redefinir solP3′ como sigue
|
1 2 |
solP3'' :: [Integer] solP3'' = [5,9..] |
Se puede comprobar experimentalmente la conjetura definiendo la función comprobacion tal que (comprobacion n) se verifica si los n primeros elementos de solP3′ son los mismos que los de solP3”.
|
1 2 3 |
comprobacion :: Int -> Bool comprobacion n = take n solP3' == take n solP3'' |
La comprobación para los 1000 primeros elementos es
|
1 2 |
ghci> comprobacion 1000 True |
Queda pendiente la demostración de la conjetura.
En la clase de hoy del curso Lógica Informática hemos continuado la búsqueda de la automatización del razonamiento.
Después de haber visto en la clase anterior el algoritmo de resolución por saturación, hemos estudiado distintas estrategias cuyo objetivo es mejorar la búsqueda de la refutación por resolución.
Las estrategias estudiadas son la resolución positiva, la resolución negativa, la resolución unitaria, la resolución por entradas y la resolución lineal.
Además, se ha presentado la estrategia por pesos y propagación unitaria.
Finalmente, como sistema de demostración por resolución se ha presentado el Prover9.
Como tarea se propone la resolución de los ejercicios del tema 5 del libro de ejercicios.
Las transparencias de esta clase son las páginas 25 a 37 del tema 5
Read More “LI2012: Estrategias de resolución proposicional”
En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell del problema propuesto la Olimpiada Internacional de Matemáticas (IMO) de 1978 cuyo enunciado es
Calcular todos los números naturales n < 1978 con la siguiente propiedad: Si m es un número natural, 1 < m < n, y m y n son coprimos (es decir, el máximo común divisor de m y n es 1), entonces m es un número primo.
La representación matemática del enunciado es
{n∈ℕ | n<1978, ∀m∈ℕ (1 < m < n ∧ mcd(n,m) = 1 ⟶ m es primo}
y su traducción a Haskell es
|
1 2 3 |
solP2 :: [Integer] solP2 = [n | n <- [1..1977], and [primo m | m <- [2..n-1], gcd n m == 1]] |
donde (primo m) se verifica si m es primo
|
1 2 |
primo :: Integer -> Bool primo n = factores n == [1,n] |
y (factores n) es la lista de los números que dividen a n
|
1 2 |
factores :: Integer -> [Integer] factores n = [m | m <- [1..n], n `rem` m == 0] |
La solución del problema se calcula con
|
1 2 |
ghci> solP2 [1,2,3,4,6,8,12,18,24,30] |
Se puede generalizar solP2 a una función solP2′ tal que (solP2′ x) es el conjunto de los números naturales n < x tales que si m es un número natural, 1 < m < n, y m y n son coprimos, entonces m es un número primo.
|
1 2 3 |
solP2' :: Integer -> [Integer] solP2' x = [n | n <- [1..x], and [primo m | m <- [2..n-1], gcd n m == 1]] |
Por ejemplo,
|
1 2 3 4 |
ghci> solP2' 2012 [1,2,3,4,6,8,12,18,24,30] ghci> solP2' 3000 [1,2,3,4,6,8,12,18,24,30] |
A la vista de los cálculos anteriores se conjetura que el conjunto de los números naturales n tales que si m es un número natural, 1 < m < n, y m y n son coprimos, entonces m es un número primo es [1,2,3,4,6,8,12,18,24,30].
Queda pendiente la demostración de la conjetura.
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos iniciado el estudio de las definiciones por recursión en Haskell. Concretamente, hemos visto ejemplos de recursión sobre los números naturales y recursión sobre listas.
Como tarea se ha propuesto escribir de manera colaborativa las soluciones de los ejercicios de la 7ª relación.
Las transparencias usadas en la clase son las comprendidas entre las páginas 1 y 9 del tema 6:
Read More “I1M2012: Definiciones por recursión (1)”