Examen Bloque I. Noviembre 2017
Instrucciones
El examen consta de dos partes diferentes que han de realizarse en orden:
- La parte teórica se ha de realizar en primer lugar, y durante su resolución se tendrán que tener los ordenadores apagados.
- Una vez se haya terminado esta parte, el alumno deberá entregar al profesor los folios correspondientes con su solución y encabezados con su nombre y apellidos.
- Solo entonces podrá comenzar a resolverse la parte práctica con su ordenador.
- Cuando acabe esta parte ha de preparar todos los ficheros necesarios con su solución, comprimirlos en un fichero ZIP que debe llevar por nombre ApellidosNombre del alumno, y avisar al profesor para que lo copie en un USB.
Parte Teórica
EJERCICIO 1 (3 ptos):
Explica los fundamentos y características principales del algoritmo de búsqueda local por Templado Simulado, y escribe un procedimiento en pseudocódigo que refleje claramente su funcionamiento.
EJERCICIO 2 (2 ptos):
Prueba que el siguiente conjunto de clausulas es insatisfactible:
{ {$p$, $q$}, {$q$, $r$}, {$r$, $w$}, {$\neg r$, $\neg p$}, {$\neg w$, $\neg q$}, {$\neg q$, $\neg r$}, {$\neg r$} }
- Aplicando el Algoritmo DPLL.
- Aplicando el método de Resolución.
Parte Práctica
EJERCICIO 3 (5 ptos):
Trabajaremos con números de 3 cifras (de 000 a 999). Inicialmente, tenemos dos números prefijados, que denotaremos por I (Inicial) y F (Final), y un conjunto de números que denotaremos por P (de Prohibidos). En cada turno, podemos transformar un número en otro añadiendo/sustrayendo 1 a uno de sus dígitos (por ejemplo, pasando de 678 a 679, o de 234 a 134). Además, tenemos estas restricciones:
- No se permite añadir 1 a 9, ni sustraer 1 a 0.
- No se permite convertir un número en un elemento de P (están prohibidos).
- No se puede cambiar un mismo dígito 2 veces seguidas.
El objetivo es llegar desde I hasta F por medio de transformaciones válidas. Utiliza la librería BFS para dar una solución general al problema, y resuélvelo en el caso particular I=567, F=778 y P={666,667}.