Programación Declarativa Avanzada
Ingeniería en Informática
Profesor: Jaime Sánchez Hernández


Material para la asignatura:

  • REPASO: Apuntes de Programación Lógica proglog.pdf

  • Transparencias introducción restricciones pda.pdf
  • Ejemplos de DCG's en Prolog: dcgs.zip
  • Presentación del sistema frolog frolog.pdf
  • Transparencias sobre Erlang:
    1. Erlang secuencial erlang_secuencial.pdf
    2. Erlang concurrente erlang_concurrente.pdf
  • Otro material:
    1. Referencia de funciones, librerías...
    2. Tutorial online
    3. Tutorial en pdf para descargar
    4. Otro mini tutorial


    Algunos proyectos del curso 2013/14

    1. Calculadora de dietas equilibradas dietas.zip
    2. Juego de zorros y sabuesos zorros-sabuesos.zip
    3. Juego Chat Noir chat-noir.zip
    4. Juego del Molinero molinero.zip
    5. Juego de las Siete y Media siete-y-media.zip
    6. Planificador de horarios planificador-horarios.zip
    7. Puzzle lógico matemático puzzle.zip


    Ejercicios:

    1. Criptograma "send + more = money" visto en clase send.pl
      Extenderlo para criptogramas genéricos "lista + lista = lista". El predicado de resolución será de la forma "cripto([S,E,N,D]+[M,O,R,E]=[M,O,N,E,Y])".
      Otros criptogramas: "[D,I,E,Z]+[T,R,E,S] = [T,R,E,C,E]". Aun más genérico, con tres sumandos: "[S,E,I,S]+[D,E]+[E,N,E,R,O] = [R,E,Y,E,S]" Criptograma genérico criptogramaGenerico.pl

    2. Problema de las reinas 4x4 reinas.pl
      Generalizar la última versión para colocar N reinas en un tablero NxN (N paramétrico). ¿Sería fácil generalizar también las dos primeras versiones?


    3. Coloreado de un mapa. Dado un mapa sobre el plano hay un conocido resultado que afirma que es posible colorearlo con 4 colores, de modo que los paises con frontera común tengan distinto color. Encontrar una representación adecuada para este problema y resolverlo utilizando dominios finitos (probarlo con el mapa de la figura). Una solucion mapa.pl




    4. Problema de la cebra. Hay cinco casas consecutivas, cada casa tiene un color diferente y cada una está habitada por un hombre de distinta nacionalidad, cada uno de ellos tiene una mascota distinta, una bebida favorita distinta y conduce un coche distinto. Tenemos además las siguientes pistas:

      1. El inglés vive en la casa roja
      2. El español tiene un perro
      3. En la casa verde se bebe café
      4. El ucraniano bebe té
      5. La casa verde esta inmediatamente a la derecha de la casa color blanco
      6. El dueño del Porsche tiene caracoles
      7. El Maserati lo condude el hombre que vive en la casa amarilla
      8. En la casa de en medio se bebe leche
      9. El noruego vive en la primer casa (de izquiera a derecha)
      10. El hombre que conduce un Saab vive en la casa de al lado del que que tiene un zorro
      11. El Maseratti lo conduce un hombre que vive en la casa al lado de donde esta el caballo
      12. El dueño del Honda bebe zumo ugo de naranja
      13. El japones conduce un Jaguar
      14. El noruego vive al lado de la casa azúl

      Determinar quién tiene una cebra y quién bebe agua. Una solución: cebra.pl


    5. Series mágicas: una serie de enteros no negativos S=(e0,e1,e2,...,en) es mágica si hay exactamente ei ocurrencias de i en la serie S para cada i=0..n. Encontrar todas las series mágicas de longitud menor o igual que 10. Implementar dos versiones: una con dominios finitos y otra por generación y prueba (sin utilizar dominios finitos). Comparar el rendimiento de ambas versiones. Una solución: magic.pl


    6. Sudoku: implementar un resolutor de sudokus utilizando la librería de dominios finitos de Swi Prolog. Rehacer la implementación sin utilizar dicha librería, empezando con generate and test e ir refinando la implementación de modo análogo a como se hizo con el problema de las reinas. Solución en el manual de ayuda de SWI Prolog.


    7. Planificación de tareas. El siguiente grafo


      representa 6 tareas t1 a t6, cada una de las cuales utiliza un recurso m1 o m2 y que tiene una duración determinada indicada por el subíndice. Los arcos indican precedencia entre las tareas (por ejemplo, t1 debe realizarse antes que t5). Implementar un programa que planifique la ejecución en el tiempo de estas tareas cumpliendo las restricciones expresadas en el grafo.
      ¿Cómo podría generalizarse el programa para problemas de este tipo? ¿Cómo podría minimizarse el tiempo de la planificación de las tareas?


    8. Planificación de tareas (CLPR): Calcular el menor tiempo necesario para realizar las tareas A, B, C y D teniendo en cuenta que los tiempos empleados en cada una son 2, 3, 5 y 4, respectivamente, y además que A precede a B y a C y que B precede a D.


    9. Supongamos un heptágono donde en cada arista hay que colocar tres números: uno en cada vértice y otro en el centro de la arista. Hay que colocar todos los números del 1 al 14 alrededor de las aristas del heptágono de manera que la suma de los números en cada arista (el del centro y los dos de los vértices) sumen lo mismo en todas las aristas. ¿Cuánto vale esa suma? ¿Se podría extender la solución para polígonos de cualquier número de lados? Una solución: heptaFD.pl


    10. Implementar una DCG en Prolog para reconocer expresiones aritméticas con número enteros en notación postfija (o polaca inversa). La expresión 5*(3+4), en notación postfija se escribe como 5 3 4 + *. Decorar la DCG construida para que evalúe las expresiones reconocidas. Otras posibles extensiones: incorporar números reales en notación científica; generar código para una máquina de pila, que pueda interpretarse después (evaluando las expresiones); hacer lo mismo para notación prefija (la expresión anterior en notación prefija se escribiría como * 5 + 3 4), ...


    11. Programar en Frolog una función que genere el triángulo de Pascal. Utilizando dicha función definir otra que obtenga la n-ésima fila de dicho triángulo. Intentar mejorar la eficiencia poniendo las declaraciones de pereza adecuadas.


    12. Definir en Frolog una función que genere la serie (infinita) de números de Fibonacci, intentando mejorar la eficiencia en lo posible.


    13. Programar en Frolog una función que tome un conjunto de valores de moneda disponibles y un total, y obtenga el cambio para dicho total utilizando valores del conjunto de monedas. Después mejorar la implementación para que obtenga el cambio con el menor número de monedas posible.


    14. Programar en Frolog el juego de cifras y letras (la parte de las cifras): dado un conjunto de números y un total obtener una expresión formada con los elementos del conjunto y los operadores aritméticos básicos, de modo que la evaluación de la misma produzca el total (si es posible). Después, mejorar la implementación de modo que obtenga la mejor aproximación al total cuando no sea posible obtener dicho total.


    15. Extender la implementación del servidor de archivos presentado en clase (módulos afile_server y afile_client) de manera que pueda modificarse el directorio de trabajo una vez creado el servidor, mediante el envío de un mensaje (para simplificar, asumiremos que se utilizan solo con rutas absolutas como directorios de trabajo). Para ello, el proceso servidor admitirá mensajes de la forma {change dir,AbsolutePath} y el cliente se extenderá con una función cd(AbsolutePath).


    16. Implementar una función que lance dos procesos Ping y Pong que intercambien mensajes entre ellos y simulen N jugadas de una partida de ping-pong (una jugada consiste en un pase de Ping y otro de Pong). Después ambos procesos terminarán (y morirán). Por ejemplo, para una partida de 3 pases, la salida sería:
      > ej:pingPong(3).
      recibe ping
      recibe pong
      <0.129.0>
      recibe ping
      recibe pong
      recibe ping
      recibe pong
      ping termina
      pong termina

      Pensar distintas posibilidades de implementación para manejar el contador de jugadas N. ¿Que ocurre si otro proceso envía un mensaje a Ping y se mete en la partida? ¿Cómo podría evitarse que otro proceso se colase en la partida enviando un mensaje a uno de nuestros procesos?

    Enlaces útiles:


    Puedes ponerte en contacto conmigo en: