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.

 Este ejemplo muestra cómo representar y manipular objetos de datos estructurados y también sirve para ejemplificar el uso de Prolog como un lenguaje natural de consulta a bases de datos. 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) tienecuatro componentes: nombre, apellido, fecha de nacimiento y trabajo :

En Prolog

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)
]).
% 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).
% Existencia de una persona en la base de datos.
existe(Persona) :- esposo(Persona); esposa(Persona); hijo(Persona).
% Fecha de nacimiento
fecha_de_nacimiento(persona(_,_,Fecha,_), Fecha).
% Salario de una persona.
salario(persona(_,_,_,trabaja(_,S)),S).
salario(persona(_,_,_,no_trabaja),0).
% Ingreso total de una 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.

1). Encontrar Nombre y Apellido de todas las personas que existen en la
Base de Datos:

 2). Encontrar Nombre y Apellido de todas las esposas que no trabajan:

3). Encontrar todos los hijos que hayan nacido en 1975:

4). Hallar los nombres de todas las madres que tienen al menos dos hijos:

5). Encontrar todos los nombres de las personas desempleadas que nacieron después de
1970:

6). Hallar todas las personas nacidas antes de 1955 cuyo salario sea menor a 2500:

7). El ingreso total por familia:

8). Todas las familias que tengan un ingreso por miembro de familia menor a 1000.

(C). Resuelva usted solo los 5 ejercicios.

a). Nombres de las familias que no tienen hijos.

 familia(Esposo,Esposa,[]).

 
b). Nombres de todos los hijos que no trabajan.


hijo(X), salario(X,0).

c). Nombres de las familias con esposas que trabajan y esposos que no trabajan.




familia(Y,Esposa,_), salario(Y,0).

Ayuda Fuente: http://cocolibre.blogspot.mx/2013/04/ia-con-prolog-actividad-c41-usando.html 


d). Todos los hijos cuyos padres difieren en edad con al menos 10 años.

familia(Espo,Espa,Hijos), fecha_nacimiento(Espo,fecha(_,_,A1)), fecha_nacimiento(Espa,fecha(_,_,A2)), A2-A1 > 9, Hijos \= [].

e). Definir la relación: gemelos(Hijo1, Hijo2) que sirva para encontrar geme-los en la
base de datos.

gemelos(H1,H2).

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 video o audio de otras fuentes debe entrecomillar y escribir la referencia documental de lo que incluye.

 AUTÓMATA FINITO DETERMINÍSTICO (AFD).

Es un modelo matemático que consiste de : 

• Un conjunto de estados, denominado S

• Un conjunto ( alfabeto) de símbolos de entrada, denominado ∑.

• Una función de transición move que mapea un par P ( s , a ) a un estado t.

• s y t son estados contenidos en S, a es un símbolo de entrada.

• Un estado de inicio, denotado por s(sub)0.

• Un conjunto de estados de aceptación (finales), denotado por F.

.

Además, un autómata finito determinístico AFD debe cumplir con las siguientes características: 

a) No hay transiciones etiquetadas por ∈.

b) Para cada estado s y un símbolo de entrada a, existe a lo más un arco etiquetado por a

saliendo de s

http://www.monografias.com/trabajos-pdf/automatas-finitos/automatas-finitos.pdf

(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.

a). La cadena de entrada aaab a partir de s1:

b). A partir de qué estados acepta la cadena ab:

c). Cuáles son todas las cadenas de longitud tres que pueden ser aceptadas a partir del
estado s1 ?

d). Si la salida se desea escrita en forma de lista.

4.3 El problema de las ocho reinas (ajedrez)

Implementación del problema de las N-Reinas en Prolog (programación lógica)

Una implementación sencilla del problema de las n-reinas en Prolog consiste en tres simples pasos:

1. Generar un tablero de dimensión n.
2. Generar una permutación sobre ese tablero.
3. Comprobar si ese tablero cumple la condición de que todas las reinas colocadas no se amenacen entre sí. ...

http://programacionilogica.wordpress.com/2008/02/07/implementacion-del-problema-de-las-n-reinas-en-prolog/

Muy buena explicacion...

Ejercicio. 3

3. Listas, operadores y aritmética.

3.1. Representación de listas.

La "lista" es una estructura de datos ampliamente utilizada en la programación no numérica. Una lista es una secuencia de cualquier número de elementos, tales como los objetos ana, tenis, tomás, eskí. Esta lista se puede escribir en Prolog como:

[ ana, tenis, tomás, eskí ]

En Prolog todos los objetos estructurados son árboles y las listas no son una excepción.

¿Cómo puede una lista representarse como un objeto Prolog? Tenemos que considerar dos casos: si la lista está ó no vacía. En el primer caso la lista se escribe como un átomo Prolog : [].

En el segundo caso la lista puede verse como formada por dos cosas:

• (1). el primer elemento, llamado "cabeza" de la lista.

• (2). los elementos restantes, llamados en conjunto: "cola" de la lista.

Para el ejemplo anterior : [ ana, tenis, tomás, eskí ] la cabeza es : ana y la cola es : [ tenis, tomás, eskí ].

La cabeza y la cola se combinan en una estructura con un functor especial. El símbolo para este functor
depende de la implementación de Prolog. Asumiremos que se trata del punto [.] .

.( Cabeza, Cola)

Debido a que la cola es a su vez una lista, se tratará de una lista vacía ó una lista con cabeza y cola. Por lo tanto para representar listas de cualquier longitud no se necesita establecer ningún principio adicional. El ejemplo anterior se representa con el término:

.( ana, .( tenis, .( tomás, .( eskí, [] ))))

3.2. Operaciones sobre listas.

Las listas se pueden utilizar para representar conjuntos aunque se debe tomar en cuenta que existen diferencias: el orden de los elementos en un conjunto no interesa mientras que en una lista sí, además los objetos se pueden repetir en una lista y en un conjunto no. Aún con estas diferencias, las operaciones más frecuentes sobre listas son semejantes a las operaciones sobre conjuntos:

Pertenencia a una lista.

Implementaremos la relación miembro como:
miembro( X, L) donde X es un objeto y L es una lista. La meta miembro( X, L) es cierta si X es miembro de la lista L, por ejemplo :

miembro( b, [ a, b, c]) es cierta, y miembro( b, [ a, [ b, c] ]) no es cierta, pero miembro( [ b, c], [ a, [ b, c]])
es cierta. El programa para la relación de pertenencia se puede basar en la siguiente observación :

X es un miembro de L si,

• (1) X es la cabeza de L, ó

• (2) X es un miembro de la cola de L.

Esto puede representarse con dos cláusulas, la primera es un hecho simple y la segunda es una regla:

miembro( X, [ X | Cola]).
miembro( X, [ Cabeza | Cola] ) :- miembro( X, Cola).

Concatenación.

Para la operación de concatenación definiremos la relación:

concat( L1, L2, L3) donde L1 y L2 son dos listas y L3 es su concatenación. Por ejemplo:
concat( [a,b], [c,d], [a,b,c,d]) es cierta, pero concat( [a,b], [c,d], [a,b,a,c,d]) es falsa. En la definición de concat tendremos dos casos dependiendo del primer argumento L1:

• (1) Si el primer argumento es la lista vacía entonces el segundo y el tercer argumento deben ser la misma lista:c oncat( [], L, L).

• (2). Si el primer argumento de concat no es una lista vacía, entonces tiene cabeza y cola, es decir, se ve como : [ X | L1]

Ejercicios.

1. Escriba una meta, usando concat, para eliminar los tres últimos elementos de una lista L produciendo otra lista L1. Recomendación: L es la concatenación de L1 y una lista de tres elementos.

Solucion:
eliminar3(L, L1) :- concat([X,Y,Z], L1, L).
concat( [], L, L).
concat( [X|L1], L2, [X|L3]) :- concat( L1, L2, L3).
Ejecucion:
?- eliminar3([a,b,c,d,e], L).
L = [d, e] ;
No

2. Escriba una secuencia de metas para eliminar los tres primeros elementos y los tres
últimos elementos de una lista L produciendo la lista L2.

Solucion:
eliminar3(L, L1) :- concat([X,Y,Z], L1, L).
concat( [], L, L).
concat( [X|L1], L2, [X|L3]) :- concat( L1, L2, L3).
Ejecucion:
?- eliminar3([a,b,c,d,e], L).
L = [d, e] ;
No

3. Defina la relación: ultimo( Elemento, Lista) de tal modo que Elemento sea el último elemento de la lista Lista. Escriba dos versiones:

(a) usando la relación concat
(b) sin usarla.

4. Defina la relación max(X,Y,Max) de tal modo que Max sea el mayor valor de los
dos números X y Y.


5. Defina el predicado maxlist(List, Max) de tal manera que Max sea el mayor
número de la lista List de números.
6. Defina el predicado sumlist(List, Sum) donde Sum es la suma de una lista de
números dada en List.

7. Defina el predicado ordenada(List) el cual es cierto (devolverá yes) si List es una
lista ordenada de números en forma ascendente o descendente, por ejemplo,
?- ordenada(1,5,6,6,9,12).
Yes

8. Defina el predicado subsum(Set, Sum, Subset) donde Set es una lista de números,
Subset es un subconjunto de esta lista y Sum es la suma de los números en
Subset. Por ejemplo,
?- subsum([1,2,5,3,2], 5, Sub).
Sub = [1,2,2];
Sub = [2,3];
Sub = [5];
...

Ejercicio. 2

Representación de objetos geométricos simples mediante objetos estructurados en Prolog:

Ejemplo. 1

a). Un punto en un espacio de dos dimensiones se puede definir con dos coordenadas.

Esto es la definición de un punto y el lugar geométrico correspondiente al plano.

P1 = punto(1,1).

P2 = punto(1,0).

b). Un segmento de línea con dos puntos.

Una línea se puede representar mediante dos puntos, uno inicial y el otro final.

S = línea( P1, P2) = línea( punto(1,1), punto(2,3) ).

c). Un triángulo con tres puntos.

EL triangulo es formado por tres puntos.

T = triangulo( punto(4,2), punto(6,4), punto(7,1) ).

Ejercicio. Sugiera una representación para rectángulos, cuadrados y círculos como objetos Prolog estructurados. Escriba algunos ejemplos que representen objetos físicos concretos utilizando la representación que sugirió.

Para rectángulos 

Un rectángulo es un polígono de 4 lados (una figura plana de lados rectos) en donde cada ángulo es un ángulo recto (90°). Entonces lo podemos representar conforme a su presentación en una grafica

Entonces hacemos referencia al número que se encuentra en cada ordenada y asi obtenemos a quien corresponde cada valor de la grafica.

P1=punto(A,B), P2=punto(C,B), P3=punto(A,D), P4=punto(C,D)

La representacion en Prolog es de esta manera

R=rectángulo(P1,P2,P3,P4)=((punto(A,B),(punto(C,B),punto(A,D),punto(C,D)).

 

Para cuadrados

Un polígono de 4 lados (una figura plana de lados rectos) donde todos los lados tienen igual longitud y todos los ángulos son rectos (90°). De manera análoga a la anterior construyamos una grafica de un cuadrado con líneas de igual longitud y con ángulos rectos de 90° grados.

Se puede escribir de la siguiente manera ya que existen dos números que se repiten entre ellos entonces escogeremos A y B, dado que A=-3 y B=3 entonces

P1=punto(A,B), P2=punto(B,B), P3=(A,A), P4=(B,A). Y en Prolog

C=cuadrado(P1,P2,P3,P4)=((Punto(A,B),punto(B,B)punto(A,A),Punto(B,A)).

Circulo

Una figura de 2 dimensiones que se realiza dibujando una curva que está siempre a la misma distancia de un centro. Representación grafica

Existe el punto de origen y un radio para construir una circunferencia o circulo. Entonces

D=circulo(puntoorigen(A,B),radio(X)).

2.2. Matching (empatamiento).

La operación más importante sobre los términos es la de matching (empatamiento). Dados dos términos cualesquiera decimos que "empatan" si se cumple lo siguiente :

(1). Son idénticos; ó,

(2). Las variables en ambos términos pueden instanciarse a objetos de tal modo que después de la sustitución de las variables por estos objetos los términos puedan ser idénticos.

El matching es un proceso que toma como entrada dos términos y checa si empatan.

• Si no empata falla

• Si empatan el proceso tiene éxito y las variables se instancian en ambos términos a los valores que las hacen ser idénticas.

Las reglas generales para decidir si dos términos S y T empatan son las siguientes :

• Si S y T son constantes entonces S y T empatan únicamente si se trata de los mismos objetos.

•  Si S es una variable y T es cualquier cosa, entonces empatan y S se instancia a T. Y a la inversa, si T es la variable, entonces T se instancia a S.

•  Si S y T son estructuras empatan únicamente si :
• (a). S y T contienen el mismo functor principal, y
• (b). Todos sus componentes correspondientes empatan.

Ejercicios. 2

1. ¿ Las siguiente operaciones de matching tienen éxito ó fallan ?Si tienen éxito, ¿cuáles son las instanciaciones resultantes en las variables?

(a). punto( A, B) = punto( 1, 2).

Tiene exito ya que A=1 y B=2 y hay un empatamiento.

 (b). punto( A, B) = punto( X, Y, Z).

 Falla ya que no son identicos.

(c). +( 2, 2) = 4.

Tiene exito ya que 2+4=4. Pero cuando se hace el ejercicio en prolog sale lo siguiente, declaramos

 + (2,2). //* El signo + es como funtor entonces cuando se le pregunta si son iguales muestra lo siguiente*//

?- +(2,2)=4.
false.  

(d). +( 2, D) = +( E, 2).

A mi parecer tiene exito ya que 2=D y E=2 toma los valores correspondientes empatan. Pero en el programa hace algo similar a esto

?- +(2,D)=+(E,2).
ERROR: Syntax error: Operator expected
ERROR: +(2,D)
ERROR: ** here **
ERROR: =+(E,2) . 

 (c). triangulo(punto(-1,0),P2,P3) = triangulo(P1,punto(1,0),punto(0,Y)).

Tiene exito ya que punto(-1,0)=P1, P2=(1,0), P3=punto(0,Y) con Y= a cualquier valor dado.

2. Usando la representación que se definió anteriormente para segmentos de línea, escriba un término que represente cualquier segmento de línea vertical en x = 5.

S=linea(P1,P2)=(punto(5,A),punto(5,B)).

3. Asuma que un rectángulo se representa con el término rectángulo( P1, P2, P3, P4) donde P1,P2,P3,P4 son los vértices del rectángulo ordenado positivamente. Defina la relación regular( R) que es verdad (true) si R es un rectángulo cuyos lados son vertical y horizontal.

2.3 Significado Declarativo.

El significado declarativo de los programas determina si una meta dada es cierta, y si es el caso, para qué valores de las variables es cierta. Para definir de manera más precisa el significado declarativo, necesitamos introducir antes el concepto de "instancia" de una cláusula.

Una instancia de una cláusula C es la cláusula C con cada una de sus variables sustituidas por algún término. Una "variante" de una cláusula C es una instancia de la cláusula C tal que cada variable se sustituye por otra variable.


Ejercicios.

1. Considere el siguiente programa:
f( 1, uno).
f( s(1), dos).
f( s(s(1)), tres).
f( s(s(s(X))), N) :- f( X, N).

¿cómo contestará Prolog las siguientes preguntas? Cuando sean posibles varias respuestas, dé al menos dos de ellas.

(a). ?- f( s(1), A).
(b). ?- f( s(s(1)), dos).
(c). ?- f( s(s(s(s(s(s(1)))))), C).
(d). ?- f( D, tres).

2. El siguiente programa dice que dos personas son parientes si,

(a). uno es predecesor del otro, ó
(b). ambos tienen un predecesor común, ó
(c). ambos tienen un sucesor común :

parientes( X, Y) :- predecesor( X, Y)
parientes( X, Y) :- predecesor( Y, X).
parientes( X, Y) :- predecesor( Z, X), predecesor( Z, Y).
parientes( X, Y) :- predecesor( X, Z), predecesor( Y, Z).

¿puede usted acortar el programa usando la notación de ';' ?

parientes( X, Y) :- predecesor( X, Y); parientes( X, Y) :- predecesor( Y, X).
parientes( X, Y) :- predecesor( Z, X), predecesor( Z, Y); parientes( X, Y) :- predecesor( X, Z), predecesor( Y, Z).

3. Reescriba el siguiente programa sin utilizar la notación de ';' :

traducir( Numero, Palabra) :-
Numero = 1, Palabra = uno;
Numero = 2, Palabra = dos;
Numero = 3, Palabra = tres.

traducir( Numero, Palabra) :- Numero = 2, Palabra = dos.
traducir( Numero, Palabra) :- Numero = 3, Palabra = tres.

traducir( Numero, Palabra) :- Numero = 1, Palabra = uno.

2.4. Significado procedural.

El significado procedural especifica el cómo contesta Prolog a las preguntas. Responder a una pregunta significa tratar de satisfacer una lista de metas. Estas pueden satisfacerse si las variables que existen en las metas pueden instanciarse de tal modo que las metas se sigan lógicamente del programa. Así el significado procedural de Prolog es un procedimiento para ejecutar una lista de metas con respecto a un programa dado.Ejecutar las metas significa tratar de satisfacerlas. Llamemos a este procedimiento 'ejecuta':

Ejercicio.

1. Considere el programa anterior y realize la traza de ejecución a la pregunta :
 

?- enorme(X), oscuro(X).
 

compare su traza de ejecución con la anterior, ya que esencialmente es la misma
pregunta pero con otro orden. ¿En cuál de ambos casos Prolog realiza más trabajo antes
de encontrar la respuesta final?

 

Al parecer es el mismo tiempo