ActividadC4

Actividad C4: Ejemplos utilizando estructuras
En esta actividad estudiaremos tres ejemplos de Prolog orientados al desarrollo de aplicaciones prácticas: bases de datos, matemáticas e inteligencia artificial.

4.1  Recuperación de la información estructurada de una base de datos
(A). Estudiar el Programa: la base de datos inicial y los procedimientos que se van adicionando al programa.

Una base de datos se puede representar en Prolog como un conjunto de hechos. Por
ejemplo,  una base de datos acerca de familias: 

• Cada familia se representa con una sola cláusula y tiene tres componentes: Esposo, Esposa e Hijos. 
• El número de hijos es variable y se debe representar con una lista. 
• A su vez cada persona (esposo, esposa ó hijo) tiene cuatro componentes: nombre, apellido, fecha de nacimiento y trabajo.

En PROLOG lo podemos ver de la siguiente forma:
 
familia(
persona(juan,perez,fecha(7,mayo,1950),trabaja(uag,2000)),
persona(ana,flores,fecha(9,mayo,1951),no_trabaja),
[persona(jose,perez,fecha(5,mayo,1973),no_trabaja),
persona(susana,perez,fecha(5,junio,1975),no_trabaja)
]).
familia(
persona(jorge,flores,fecha(21,abril,1953),trabaja(uag,2500)),
persona(edith,juarez,fecha(5,enero,1960),no_trabaja),
[persona(pedro,flores,fecha(1,julio,1980),no_trabaja)
]).
...
Una vez definida la base de datos, es posible ir adicionando procedimientos que hagan
más práctica la interacción con ella :
% X es esposo.
esposo(X) :- familia(X,_,_).
% X es esposa.
esposa(X) :- familia(_,X,_).
% X es hijo.
hijo(X) :- familia(_,_,Hijos), miembro(X,Hijos).
miembro(X, [X|L]).
miembro(X, [Y|L]) :- miembro(X, L).
... 

La programación en PROLOG seria:

familia(
persona(sergio,maggi,fecha(08,enero,1983),trabaja(independiente,2500)), % esposo
persona(yareni,catalan,fecha(18,agosto,1984),trabaja(secretaria,3000)), % esposa
[ %, hijos.
persona(ineray,maggi,fecha(8,noviembre,2010),no_trabaja),
persona(alejandra,maggi,fecha(10,julio,2011),no_trabaja)
]
).
familia(
persona(ernesto,maggi,fecha(13,julio,1959),trabaja(descartables,4000)),
persona(julia,canalini,fecha(12,julio,1957),no_trabaja),
[ persona(paolo,maggi,fecha(18,noviembre,1989),trabaja(descartables,4000)) ]
).
 % Asi definiremos quien es esposo: Y es esposo.
esposo(Y) :- familia(Y,_,_).
 % Asi definiremos quien es esposa: X es esposa.
esposa(X) :- familia(_,X,_).
 % Asi definiremos quien es hijo:
hijo(Z) :- familia(_,_,Hijos), miembro(Z,Hijos).
miembro(X, [X|_]). % Asi utilizaremos esta operacion para enlistar a todos los Hijos.
miembro(X, [_|L]) :- miembro(X, L).
% Asi podremos saber si hay una persona en la base de datos.
existe(Persona) :- esposo(Persona); esposa(Persona); hijo(Persona).
% Con este por fecha de nacimiento.
fecha_nacimiento(persona(_,_,Fecha,_), Fecha).
% Con esta el salario de una persona.
salario(persona(_,_,_,trabaja(_,S)),S).
salario(persona(_,_,_,no_trabaja),0).
% Con este ultimo el ingreso total de la familia.
total([],0).
total([Persona|Lista],Suma) :- salario(Persona,S),
total(Lista,Resto), Suma is S + Resto.

 (B). Cargar el programa en Swi-Prolog y estudiar y probar las preguntas de ejemplo.

Petición	PREGUNTA	RESPUESTA
1.- Encontrar Nombre y Apellido de todas las personas que existen en la Base de Datos	existe(persona( Nombre, Apellido,_,_)).	Nombre = sergio, Apellido = maggi; Nombre = yareni, Apellido = catalan; Nombre = ineray, Apellido = maggi; Nombre = alejandra, Apellido = maggi; Nombre = paolo, Apellido = maggi; Nombre = julia, Apellido = canalini; Nombre = ernesto, Apellido = maggi; false.
2.- Encontrar Nombre y Apellido de todas las esposas que no trabajan	esposa( persona( Nombre, Apellido,_,no_trabaja)).	Nombre = julia, Apellido = canalini;
3.- Encontrar todos los hijos que hayan nacido en 1975	hijo(X), fecha_nacimiento( X, fecha(_,_,1975)).	false.
4.- Hallar los nombres de todas las madres que tienen al menos dos hijos	familia(_, persona( Nombre, Apellido,_,_),[_,_|_]).	Nombre = yareni, Apellido = catalan
5.- Encontrar todos los nombres de las personas desempleadas que nacieron después de 1970	existe( persona(Nombre, Apellido, fecha(_,_,Anio), no_trabaja)), Anio > 1970.	Nombre = ineray, Apellido = maggi; Nombre = alejandra, Apellido = maggi,
6.- Hallar todas las personas nacidas antes de 1955 cuyo salario sea menor a 2500	existe(Persona), fecha_nacimiento( Persona, fecha(_,_,Anio)), Anio < 1975, salario( Persona, Salario), Salario < 2500.	false.
7.- El ingreso total por familia	familia(Esposo, Esposa, Hijos), total( [Esposo, Esposa|Hijos], Ingreso).	Esposo = persona( sergio, maggi, fecha(08,enero,1983), trabaja(independiente,2500)), Esposa = persona( yareni, catalán, fecha(18,agosto,1984), trabaja(secretaria, 3000)), Hijos = [persona(ineray, maggi, fecha(8,noviembre,2010), no_trabaja), persona(alejandra, maggi, fecha(10,julio,2011), no_trabaja)], Ingreso = 5500 ; Esposo = persona( ernesto, maggi, fecha(13,julio,1959), trabaja(descartables,4000)), Esposa =  persona(julia, canalini, fecha(12,julio,1957),no_trabaja), Hijos = [persona(paolo,maggi, fecha(18,noviembre,1989), trabaja(descartables,2000))], Ingreso = 6000 ; false.
8.- Todas las familias que tengan un ingreso por miembro de familia menor a 1000. (Promedio)	familia(Esposo,Esposa,Hijos), total([Esposo, Esposa|Hijos], Ingreso), length([Esposo, Esposa|Hijos],N), Ingreso/N < 1000.	Esposo = persona( sergio, maggi, fecha(08,enero,1983), trabaja(independiente,2500)), Esposa = persona( yareni, catalán, fecha(18,agosto,1984), trabaja(secretaria, 3000)), Hijos = [persona(ineray, maggi, fecha(8,noviembre,2010), no_trabaja), persona(alejandra, maggi,  fecha(10,julio,2011), no_trabaja)], Ingreso = 5500 N = 4; Esposo = persona( ernesto, maggi, fecha(13,julio,1959), trabaja(descartables,4000)), Esposa =  persona(julia, canalini, fecha(12,julio,1957),no_trabaja), Hijos = [persona(paolo,maggi, fecha(18,noviembre,1989), trabaja(descartables,2000))], Ingreso = 6000 N = 3; false.

(C). Resuelva usted solo los 5 ejercicios (pag. 46) y reporte en su blog tanto las respuestas como el resultado de la ejecución de las preguntas.

Pregunta	Pregunta en PROLOG	Respuesta
Nombres                  de las familias que no tienen hijos.	familia(Esposo,Esposa,[]).	false.
Nombres de todos los hijos que no trabajan.	hijo(X), salario(X,0).	X= persona(ineray,maggi, fecha(8,noviembre,2010), no_trabaja); X = persona(alejandra,maggi, fecha(10,julio,2011),no_trabaja); false
Nombres de las familias con esposas que trabajan y esposos que no trabajan.	familia(Y,Esposa,_), salario(Y,0).	false.
Todos los hijos cuyos padres difieren en edad con al menos 10 años.	familia(Esposo,Espasa,Hijos), fecha_n(Esposo,fecha(_,_,A1)), fecha_n(Espasa,fecha(_,_,A2)), A2-A1 > 9. Creo que es así.	false.
Definir la relación: gemelos (Hijo1, Hijo2) que sirva para encontrar gemelos en la base de datos.	Me falta programar esta parte.

4.2 Simulación de un autómata no determinístico.
(A). Investigue (Internet, libros, publicaciones,…) y escriba una entrada en su blog explicando con sus propias palabras y ejemplos qué es un autómata no determinístico. Recuerde que al incluir texto o imágenes o vídeo o audio de otras fuentes debe entrecomillar y escribir la referencia documental de lo que incluye.

Un autómata finito es cualquier objeto que se puede encontrar en un número finito de estados y que puede transitar de un estado a otro mediante una acción: por ejemplo una puerta puede estar en dos estados “abierta” o “cerrada”, transita de abierta a cerrada mediante la acción “cerrar” y de cerrada a abierta mediante la acción “abrir”. Normalmente los autómatas finitos se representan con “diagramas de estado”: En un diagrama de estado pones un círculo por cada estado posible y por cada acción pones una flecha que pasa de un estado a otro.

Normalmente los autómatas finitos se usan para diseñar computadoras que utilizan muy poca memoria, por ejemplo las máquinas de dulces o los teléfonos fijos.

El determinismo y no determinismo es un concepto de computación un poco abstracto, y se usa principalmente de forma teórica (no práctica). Se refiere al hecho de que “el siguiente paso está bien determinado”. En el caso de los autómatas finitos deterministas a cada estado y a cada acción le corresponde uno y exactamente un solo estado siguiente (o sea que dado un estado y una acción, el estado siguiente está siembre bien determinado). En el caso de los autómatas finitos no deterministas puedes tener varias flechas saliendo del mismo estado y con la misma acción hacia varios diferentes “estados siguientes”, o inclusive podrías no tener ninguna. Se sabe que todo autómata finito no determinista se puede transformar en un autómata finito determinista equivalente (que hace lo mismo).

http://mx.answers.yahoo.com/question/index?qid=20111230155845AAlEViD

(B). Estudiar el programa de ejemplo (cómo un autómata se puede representar en Prolog).

(C). Probar el Programa en Swi-Prolog y los ejemplos de ejecución.

4.3 El problema de las ocho reinas (ajedrez)
(A). Estudiar cuál es el problema de las ocho reinas. Investigar en Internet el problema de las ocho reinas en general y escribir una entrada en su blog explicando con sus propias palabras y con ejemplos, puede incluir información de otras fuentes siempre y cuando refiera las fuentes documentales de manera correcta.

Lo que se estudia es el problema de n Reinas, pero ahora nos enfocaremos como nos pidió el profesor de 8 reinas.

antes de comenzar a leer lo que publico otro autor, este problema consta de lo siguiente, de que hay un tablero de nxn, y con n reinas, lo que tenemos que hacer nosotros es tratar de colocar las n reinas en esta matriz de nxn o tablero como quieran llamarle, de tal manera que ninguna reina pueda cruzarse o estar en la dirección en la que ella puede moverse.

Este es un problema muy recurrido al estudiar algoritmos, por lo que se puede encontrar en muchos libros. La versión original del problema busca las formas en que se puede acomodar en un tablero de ajedrez (un tablero de 8×8 casillas) a 8 reinas, de tal forma que ninguna de las reinas esté en posición de ataque. Una reina puede atacar a otra pieza de ajedrez cuando se encuentra en el mismo renglón, columna o diagonal. Una de la variantes más comunes del problema es poner n reinas en un tablero de n×n.

El problema de las 8 reinas cuenta con 92 soluciones distintas, pero si consideramos que las soluciones que difieren sólo por rotaciones o reflexiones son iguales, entonces sólo cuenta con 12 soluciones únicas. Para los primeros valores de n tenemos:

n	1	2	3	4	5	6	7	8	9	10	11	12
Únicas	1	0	0	1	2	1	6	12	46	92	341	1787
Distintas	1	0	0	2	10	4	40	92	352	724	2680	14200

Ejemplo

El Problemas de las Ocho Reinas de Ajedrez

Problema

En el ajedrez es posible colocar a ocho reinas en el tablero de tal forma que ninguna reina pueda ser atacada por otra. Escribe un programa que determine todas posibles posiciones en que se pueden acomodar las reinas dada la posición inicial de una de ellas.

No intentes escribir un programa que evalúe todas las 8 posibles posiciones de las 8 reinas en el tablero. Esto requeriría 8⁸ evaluaciones y saturaría el sistema. Habrá un tiempo límite razonable para que corra tu programa.

Entrada

La primera línea de la entrada contiene la cantidad de casos, y está seguida por un espacio en blanco. Cada caso consiste en dos números separados por un espacio en blanco. Los números representan la posición de una de las ocho reinas. Siempre será una posición permitida, por lo que no necesitas validar la entrada.

Para estandarizar la notación, asumiremos que la esquina superior izquierda del tablero ocupa la posición (1, 1). Las filas van a lo horizontal y la que se encuentra arriba es la fila 1. Las columnas van en vertical y la columna que esta a la izquierda es la 1. Cualquier referencia a un cuadro se hace primero por fila y después columna; por lo tanto (4, 6) se refiere a la fila 4, columna 6.

Cada caso está separado por una línea en blanco.

Salida

Por cada caso en la entrada deber haber una línea con la solución a la salida.

Cada solución deberá estar numerada secuencialmente de 1 a n. Cada solución contendrá 8 números. Cada uno de los 8 números será la coordenada de la fila de la solución. La coordenada de la columna estará dada por el orden en que los 8 números están impresos. Esto es, el primer número representa la fila en el que está la reina de la primera columna; el segundo número representa la fila en el que está la reina de la segunda columna; y así sucesivamente.

Cada solución deberá estar en una solo línea, con la representación de 8 dígitos que se acaba de mencionar.

http://pier.guillen.com.mx/algorithms/09-busqueda/09.7-problema_reinas.htm


(B). Estudiar el programa de las ocho reinas descrito en los apuntes y pruebe el programa en Swi-Prolog.



  4.4 (Opcional).
Buscar en Internet un programa un programa interactivo del juego del gato (tres en raya) en Prolog, estudiar y probar el programa en Swi-Prolog, reportar en su blog personal esta experiencia.