Vestigium

LI2012: Estrategias de resolución proposicional

PorJosé A. Alonso 13 noviembre 20128 marzo 2013

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”

I1M2012: Números sin coprimos no primos

PorJosé A. Alonso 13 noviembre 20128 marzo 2013

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

solP2 :: [Integer]
solP2 = [n | n <- [1..1977], 
             and [primo m | m <- [2..n-1], gcd n m == 1]]

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

primo :: Integer -> Bool
primo n = factores n == [1,n]

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

factores :: Integer -> [Integer]
factores n = [m | m <- [1..n], n `rem` m == 0]

1 2	factores :: Integer -> [Integer] factores n = [m \| m <- [1..n], n `rem` m == 0]

La solución del problema se calcula con

ghci> solP2
[1,2,3,4,6,8,12,18,24,30]

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.

solP2' :: Integer -> [Integer]
solP2' x = [n | n <- [1..x], 
                and [primo m | m <- [2..n-1], gcd n m == 1]]

solP2' :: Integer -> [Integer]

solP2' x = [n | n <- [1..x],

and [primo m | m <- [2..n-1], gcd n m == 1]]

Por ejemplo,

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]

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.

I1M2012: Definiciones por recursión (1)

PorJosé A. Alonso 12 noviembre 20128 marzo 2013

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)”

LI2012: Ejercicios de resolución proposicional

PorJosé A. Alonso 8 noviembre 20128 marzo 2013

En la clase de hoy del curso Lógica Informática se han comentado soluciones de los ejercicios propuestos del tema 5 del libro de ejercicios.

I1M2012: 1º examen de la evaluación continua

PorJosé A. Alonso 8 noviembre 20128 marzo 2013

En la clase de hoy de Informática de 1º del Grado en Matemáticas se ha realizado el 1º examen de la evaluación continua.

A continuación se muestra el examen junto con su solución:

-- Informática (1º del Grado en Matemáticas)
-- 1º examen de evaluación continua (8 de noviembre de 2012)
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función primosEntre tal que (primosEntre x y)
-- es la lista de los número primos entre x e y (ambos inclusive). Por
-- ejemplo, 
--    primosEntre 11 44  ==  [11,13,17,19,23,29,31,37,41,43]
-- ---------------------------------------------------------------------

primosEntre x y = [n | n <- [x..y], primo n]

-- (primo x) se verifica si x es primo. Por ejemplo,
--    primo 30  == False
--    primo 31  == True  
primo n = factores n == [1, n]

-- (factores n) es la lista de los factores del número n. Por ejemplo,
--    factores 30  \valor  [1,2,3,5,6,10,15,30]  
factores n = [x | x <- [1..n], n `mod` x == 0]

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función posiciones tal que (posiciones x ys)
-- es la lista de las posiciones ocupadas por el elemento x en la lista
-- ys. Por ejemplo, 
--    posiciones 5 [1,5,3,5,5,7]  ==  [1,3,4]
--    posiciones 'a' "Salamanca"  ==  [1,3,5,8]
-- ---------------------------------------------------------------------

posiciones x xs = [i | (x',i) <- zip xs [0..], x == x']

-- ---------------------------------------------------------------------
-- Ejercicio 3. El tiempo se puede representar por pares de la forma
-- (m,s) donde m representa los minutos y s los segundos. Definir la
-- función duracion tal que (duracion t1 t2) es la duración del
-- intervalo de tiempo que se inicia en t1 y finaliza en t2. Por
-- ejemplo, 
--    duracion (2,15) (6,40)  ==  (4,25)
--    duracion (2,40) (6,15)  ==  (3,35)
-- ---------------------------------------------------------------------

tiempo (m1,s1) (m2,s2)
       | s1 <= s2  = (m2-m1,s2-s1)
       | otherwise = (m2-m1-1,60+s2-s1)

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función cortas tal que (cortas xs) es la
-- lista de las palabras más cortas (es decir, de menor longitud) de la
-- lista xs. Por ejemplo,
--    ghci> cortas ["hoy", "es", "un", "buen", "dia", "de", "sol"]
--    ["es","un","de"]
-- ---------------------------------------------------------------------

cortas xs = [x | x <- xs, length x == n]
    where n = minimum [length x | x <- xs]

-- Informática (1º del Grado en Matemáticas)

-- 1º examen de evaluación continua (8 de noviembre de 2012)

-- ---------------------------------------------------------------------

-- Ejercicio 1. Definir la función primosEntre tal que (primosEntre x y)

-- es la lista de los número primos entre x e y (ambos inclusive). Por

-- ejemplo,

-- primosEntre 11 44 == [11,13,17,19,23,29,31,37,41,43]

-- ---------------------------------------------------------------------

primosEntre x y = [n | n <- [x..y], primo n]

-- (primo x) se verifica si x es primo. Por ejemplo,

-- primo 30 == False

-- primo 31 == True

primo n = factores n == [1, n]

-- (factores n) es la lista de los factores del número n. Por ejemplo,

-- factores 30 \valor [1,2,3,5,6,10,15,30]

factores n = [x | x <- [1..n], n `mod` x == 0]

-- ---------------------------------------------------------------------

-- Ejercicio 2. Definir la función posiciones tal que (posiciones x ys)

-- es la lista de las posiciones ocupadas por el elemento x en la lista

-- ys. Por ejemplo,

-- posiciones 5 [1,5,3,5,5,7] == [1,3,4]

-- posiciones 'a' "Salamanca" == [1,3,5,8]

-- ---------------------------------------------------------------------

posiciones x xs = [i | (x',i) <- zip xs [0..], x == x']

-- ---------------------------------------------------------------------

-- Ejercicio 3. El tiempo se puede representar por pares de la forma

-- (m,s) donde m representa los minutos y s los segundos. Definir la

-- función duracion tal que (duracion t1 t2) es la duración del

-- intervalo de tiempo que se inicia en t1 y finaliza en t2. Por

-- ejemplo,

-- duracion (2,15) (6,40) == (4,25)

-- duracion (2,40) (6,15) == (3,35)

-- ---------------------------------------------------------------------

tiempo (m1,s1) (m2,s2)

| s1 <= s2 = (m2-m1,s2-s1)

| otherwise = (m2-m1-1,60+s2-s1)

-- ---------------------------------------------------------------------

-- Ejercicio 4. Definir la función cortas tal que (cortas xs) es la

-- lista de las palabras más cortas (es decir, de menor longitud) de la

-- lista xs. Por ejemplo,

-- ghci> cortas ["hoy", "es", "un", "buen", "dia", "de", "sol"]

-- ["es","un","de"]

-- ---------------------------------------------------------------------

cortas xs = [x | x <- xs, length x == n]

where n = minimum [length x | x <- xs]