Temas Avanzados en Ingeniería Informática (I)-Lógica Curso 2011-2012 1. Fecha de entrega La fecha límite de entrega será el 22 de Marzo (jueves) hasta las 20:00 horas.

2. Objetivo El objetivo de esta práctica contacto con la Programación de programación Prolog. Para simples que permiten definir en Prolog.

consiste en realizar una primera toma de Lógica, y más concretamente con el lenguaje ello, se implementarán varios ejercicios bases de hechos (o de conocimiento) y reglas

En esta, y en el resto de las prácticas de la asignatura, podrá utilizarse el intérprete SWI-Prolog (http://www.swi-prolog.org/), o el intérprete Prolog de GNU (gprolog, http://ftp.gnu.org/gnu/gprolog/). También puede utilizarse cualquier otro intérprete Prolog que se desee, siempre y cuando, no se utilicen predicados, instrucciones, o procedimientos propios. Las prácticas serán corregidas utilizando SWIProlog, o GProlog, por lo que se recomienda la utilización de uno de estos dos intérpretes. Para aquellos que lo deseen, la instalación en Linux (distribución Ubuntu) tanto de GProlog como de Swi-Prolog (versión 5.6.14 para Linux), puede realizarse ejecutando desde línea de comandos: :~$ sudo apt-get install gprolog :-$ prolog :-$ gprolog

//ejecuta gnu-prolog //ejecuta gnu-prolog

:-$ sudo apt-get install swi-prolog :-$ swipl //ejecuta swi-prolog :-$ swiprolog //ejecuta swi-prolog La práctica se ha dividido en un conjunto de ejercicios básicos que deben ser implementados y documentados.

3. Descripción de la práctica 3.1.

Árboles genealógicos

• (a) Se pide buscar un árbol genealógico, real o ficticio, y crear un base de hechos que lo represente y el conjunto de cláusulas necesarias que me permitan establecer las relaciones habituales en cualquier familia. Se pide crear (como mínimo) los siguientes predicados: 1. prole(X,Y): cierto, si X es hijo de Y (cualquiera de los dos sexos). 2. hija(X,Y): cierto, si X es hija de Y.

1

3. hijo(X,Y): cierto, si X es hijo varón de Y. 4. progenitor(X,Y): cierto, si X es un progenitor de Y. 5. padre(X,Y): cierto, si X es el padre de Y. 6. madre(X,Y): cierto, si X es la madre de Y. 7. fraterno(X,Y): cierto, si X e Y son hermanos/as. 8. hermano(X,Y): cierto si X es hermano varón de Y. 9. hermana(X,Y): cierto si X es hermana de Y. 10. primo(X,Y): cierto si X e Y son primos (cualquiera de los dos sexos). 11. abuelo(X,Y): cierto si X es abuelo varón de Y. 12. abuela(X,Y): cierto si X es abuela de Y. 13. tio(X,Y): cierto si X es tío de Y (tanto carnal como político). 14. tia(X,Y): cierto si X es tía de Y (tanto carnal como política). 15. suegro(X,Y): cierto si X es suegro de Y. 16. suegra(X,Y): cierto si X es suegra de Y. 17. yerno(X,Y): cierto si X es yerno de Y. 18. nuera(X,Y): cierto si X es nuera de Y. 19. esposo(X,Y): cierto si X e Y están casados. 20. marido(X,Y): cierto si X es marido de Y. 21. mujer(X,Y): cierto si X es la mujer de Y. 22. varon(X): cierto si X es varón. 23. mujer(X): cierto si X es mujer.

También se diseñarán cláusulas que nos permitan relacionar diferentes familias, por ejemplo: 24. cuniado(X,Y): cierto si X es cuñado de Y. 25. cuniada(X,Y): cierto si X es cuñada de Y.

Se crearán cláusulas de carácter recursivo como: 26. antepasado(X,Y): cierto si X es antepasado de Y. 27. descendiente(X,Y): cierto si X es descendiente de Y. 28. pariente(X,Y): cierto si X e Y son parientes.

• (b) Se modificará el programa anterior, para permitir la inserción de nuevos hechos en nuestra base de conocimiento. Como característica básica se considerará la inserción de este nuevo conocimiento: "A, cuyos padres son B y C, decide casarse con D (sus padres no son conocidos para nuestra base de hechos). Como efecto de este matrimonio tienen una hija a la que deciden ponerle el nombre de E." Es decir, podremos ejecutar un predicado desde el intérprete de Prolog (por ejemplo, casados(X,Y)) que añadiría automáticamente ese conocimiento a la base de hechos. • (c) (opcional) Modificar la base de hechos anterior sobre un caso libre y aplicar los predicados ya definidos. La complejidad de la nueva base de hechos, así como particularidades de la misma (i.e. múltiples padres, múltiples matrimonios) definirán la nota de este apartado. • (d) (opcional) Modificar la base de hechos anterior y permitir la utilización de listados familiares para generar representaciones más compactas de los hechos, modificando adecuadamente las reglas.

2

3.2.

•

Búsqueda en laberintos

(a) Se desea formalizar en PROLOG el diseño de un pequeño laberinto que tenga un único camino válido y sin posibilidad de ciclos. Únicamente será posible realizar los siguientes movimientos: arriba, abajo, izquierda y derecha. El laberinto sería el siguiente:

Los hechos del problema serán: o Los pasillos existentes entre dos casillas: pasillo(1,1,1,2), … o La salida: salida(1,4) Deberá implementar las reglas mover, para moverse hacia arriba, abajo, izquierda y derecha. Puede ser necesaria la implementación de alguna regla adicional. El objetivo será: mover(1,1,[paso(1,1)],Solucion) Y devolverá: Solucion=[paso(1,1), paso(1,2), paso(2, 2), paso(3, 2), paso(3, 3), paso(4, 3), paso(4, 4), paso(3, 4), paso(2, 4), paso(1, 4)] •

(b) (opcional) Se trata de ampliar el programa anterior introduciendo estructuras más complejas. El nuevo programa deberá funcionar para cualquier laberinto (puede tener bucles). Deberá devolver el camino óptimo entre una entrada y una salida. El camino óptimo será aquel que requiere menos pasos. Para optimizar el proceso de búsqueda deberá llevar un listado de caminos visitados, para evitar recorrerlos de nuevo.

3.3. Parentesco (OPCIONAL) El parentesco es el vínculo que liga unas personas con otras (www.iabogado.com/esp/guialegal/guialegal.cfm?IDCAPITULO=01020000). Puede ser de consanguinidad, que sería el vínculo de sangre que une a las personas y el de afinidad, también denominado político, que sería el que liga a un esposo con los parientes de sangre del otro. Dentro del parentesco de consanguinidad hay que distinguir lo que es la línea recta (ascendente o descendente) de lo que es la línea colateral. •

Línea recta. La proximidad del parentesco de consanguinidad se mide por grados, siendo un grado la distancia que hay entre dos personas engendradas una de otra. De una a otra hay una generación y por

3

tanto cada generación es un grado. Así padre e hijo son parientes en primer grado. Abuelo y nieto hay dos grados, uno entre padre e hijo y otro entre padre y abuelo. Por lo tanto el grado de parentesco entre el nieto y el abuelo es el de segundo grado de consanguinidad en línea recta. •

Línea colateral. Nos viene dada por aquellas personas que no descienden unas de otras, sino de un antepasado común (primos entre sí, siendo el antepasado común el abuelo). La medición o el grado de parentesco se calcula de la siguiente manera. Ascendemos hasta llegar al más próximo antepasado común con la otra persona, y luego se baja por la línea recta descendente que une a este antepasado con la otra cuyo parentesco con la primera se mide. Por lo tanto dos hermanos son parientes en segundo grado de consanguinidad en línea colateral.

Se pide crear las cláusulas correspondientes para poder consang(X,Y,Z),afinidad(X,Y,Z), lrecta(X,Y,Z), lcolat(X,Y,Z).

calcular

3.4. Diseño de menús para un restaurante (a)

Se desea formalizar en PROLOG el diseño de menús en un restaurante, para ello se deben construir un conjunto de predicados que contengan los diferentes tipos de alimentos. A partir, de esos predicados se definirán otros que nos permitan construir menús dependiendo del gusto de los posibles clientes. En el siguiente ejemplo damos algunos predicados donde almaceno los distintos alimentos de los que dispone el restaurante: pescados(Besugo,Atun,Emperador,Mero,Sardina). carnes(Cerdo,Ternera,Pollo,Pato,Jabali). vegetales(Zanahoria,Lechuga,Repollo,Coliflor,Acelga).

Un menú de este restaurante deberá constar de tres platos compuestos por un primer y segundo plato (entrada y plato principal) y de un postre. Deberemos crear por lo menos un predicado que me permita definir un menú para vegetarianos, y otro para personas que no deseen incluir nunca pescado en su comida. vegetarianos(X,Y,Z). X = primer plato, Y = segundo plato, Z = postre. no-pescado(X,Y,Z). Nota: En el segundo tipo de menús es aconsejable emplear la negación. (b)

Se trata de refinar el funcionamiento del programa anterior introduciendo estructuras más complejas. En este apartado debemos de modificar el anterior para poder añadir o eliminar un determinado alimento a su lista de comida, además modificaremos la base de cláusulas para permitir la existencia de sublistas, en estas sublistas introduciremos los valores calóricos de cada alimento. Definir el subconjunto de reglas necesarias para poder

4

modificar un conjunto de alimentos, buscar las calorías que contiene un alimento en particular, y crear reglas para definir menús equilibrados. Ej: pescados([Besugo,300],[Bacalao,350],[Emperador,400],[Mero,200],[ Sardina,100]). carnes([Cerdo,700],[Ternera,450],[Pollo,250],[Pato,250],[Jabali, 200]). Se pueden diseñar otro tipo de sublistas que organicen la información de una forma más conveniente, por ejemplo los pescados podríamos definirlos en función de la clase a la que pertenecen: pescados([blanco,[Besugo,Emperador,Mero] ,azul,[Sardina,Bonito], marisco,[Langosta,Centollo,Langostino]]). O bien podemos definir una estructura todavía más compleja que la anterior, en base a la cual podemos definir nuevos predicados, Ej: pescados([blanco,[[Besugo,300],[Emperador,400],[Mero,200]],azul[ [Sardina,100],[Bonito,300]],marisco[[Langosta,150],[Centollo,200 ],[Langostino,100]]). Los nuevos predicados mostrarán, además de los diferentes menús, el valor calórico total de los mismos.

4. Entrega de la memoria y del programa La práctica (tanto el código como la memoria) se entregarán en un fichero comprimido como se indica en la página de la asignatura, y cuyo nombre debe indicar, el número de práctica y el número de grupo del que se trata. Se aceptarán ficheros comprimidos zip, rar, tar.gz, o tgz. Ejemplo: par05prac1.tar.gz, par06prac1.tgz, par02prac1.zip, par04prac1.rar La práctica se entregará utilizando la zona de envío de prácticas de la EPS (http://www.ii.uam.es/esp/alumnos/practicas/envio_practicas.php3). El código fuente entregado tendrá todo lo necesario para que se pueda ejecutar los diferentes procedimientos, así como los casos de prueba que se consideren necesarios. El código deberá estar adecuadamente comentado. La memoria constará de las siguientes secciones: 1. Introducción (una hoja de descripción de lo que hay que hacer desde vuestro punto de vista y no copiando el enunciado).

5

2. Descripción a alto nivel de lo realizado: qué predicados se han definido y porqué, qué problema resuelve cada uno de ellos y cómo se relacionan unos con otros, etc.

3. Código fuente completo con comentarios (el código final no debería ser muy largo)

4. Consideraciones sobre la eficiencia del programa, si es que se han tenido en cuenta cuestiones como el orden de las cláusulas, orden de los objetivos en los cuerpos, cut, …

5. Conclusiones (qué se ha aprendido, dificultades encontradas, comentarios sobre PROLOG, etc.).

6. Medida del esfuerzo del desarrollo de la práctica}, en este último apartado podrá mostrarse una tabla donde los alumnos indiquen (de forma aproximada) el número de horas dedicadas al desarrollo de la misma. Pueden indicarse los siguientes elementos (u otros que se consideren oportunos): Análisis del problema, Desarrollo del programa, Diseño de la solución, Verificación y Pruebas, Creación de la documentación.

5. Criterios de evaluación Se valorará: 1. 2. 3. 4.

La corrección del programa (que funcione en todos los casos) La claridad del código La claridad de las explicaciones en la memoria Las consideraciones que haya hecho el alumno para mejorar la eficiencia (cambiar el orden de los objetivos, etc.), si estas están justificadas en la memoria

6