lunes, 21 de julio de 2014

SWI_Prolog / Arbol Genealogico




Este es un ejemplo de como se hace  un árbol genealógico de la familia en "SWI Prolog" que se descarga directamente desde internet. este programa  es muy funcional para hacer consultas solo agregando relaciones o hechos en los cuales para el árbol solo se utilizan hechos  padre a hijo.

el signo de % significa un comentario
el singo de , significa conjunción
el singo de . significa disyunción
los signos :- significan condicional

-los hecho se definen de la siguiente manera:

padre(Silvio,laura)  % se lee Silvio es el padre de laura
madre(elvira,lisbe)  % se lee elvira es el madre de lisbe

y asi sucesivamente todos los hechos padre e hijoo madre e hijo.

-las condiciones se definen de la siguiente manera:

hermanos(X,Y) :-  padre(Z,X), padre(Z,Y). % se lee X es hermano de Y si Z es el padre de X y Z es el padre de Y
abuelos(X,Z):- padre(X,A),padre(A,Z). % se lee X es abuelo de Z  si X es padre de A y A es padre de Z

-para las consultas después de tener los hechos en relación padres e hijos se hace de la siguiente manera:

?- hermanos(Andres,laura). % se escribe tal cual, los nombres pueden variar!
?- tios(ruben,daniela). % se escribe tal cual, los nombres pueden variar!

Un ejemplo de como se hacen los hechos y las condiciones basados en el árbol genealógico:

madre(lisbe,laura).
madre(lisbe,alejandra).
madre(lisbe,daniela).
madre(lisbe,andres).
padre(silvio,laura).
padre(silvio,alejandra).
padre(silvio,daniela).
padre(silvio,andres).
padre(francisco,silvio).
padre(francisco,jesus).
padre(francisco,rosalva).
padre(francisco,nelsy).
madre(erlinda,silvio).
madre(erlinda,jesus).
madre(erlinda,rosalva).
madre(erlinda,nelsy).
madre(nelsy,tatiana).
madre(nelsy,miguel).
madre(rosalva,natalia).
madre(rosalva,diego).
padre(luis,lisbe).
padre(luis,johanna).
padre(luis,brigithe).
padre(luis,hsneider).
madre(elvira,lisbe).
madre(elvira,johanna).
madre(elvira,brigithe).
madre(elvira,hsneider).
madre(johanna,carlos).
madre(brigithe,nicole).
madre(hsneider,steven).
diferente(X,Y):- X\=Y.
hermanos(X,Y):- madre(W,X),madre(W,Y),diferente(X,Y).
hermanos(X,Y):- padre(P,X),padre(P,Y),diferente(X,Y).
tios(X,Y):- padre(Z,Y),hermanos(X,Z).
tios(X,Y):- madre(Z,Y),hermanos(X,Z).
abuelos(X,Z):- padre(X,A),madre(A,Z).
abuelos(X,Z):- madre(X,B),madre(B,Z).
abuelos(X,Z):- madre(X,C),padre(C,Z).
abuelos(X,Z):- padre(X,D),padre(D,Z).
sobrinos(X,Y):- padre(W,X),hermanos(W,Y).
sobrinos(X,Y):- madre(P,X),hermanos(P,Y).
primos(X,Y):-  padre(W,X),padre(Z,Y),hermanos(Z,W).
primos(X,Y):-  padre(W,X),madre(Z,Y),hermanos(Z,W).
primos(X,Y):-  madre(W,X),madre(Z,Y),hermanos(Z,W).
primos(X,Y):-  madre(W,X),padre(Z,Y),hermanos(Z,W).
nietos(Z,X):- padre(X,A),madre(A,Z).
nietos(Z,X):- madre(X,B),madre(B,Z).
nietos(Z,X):- madre(X,C),padre(C,Z).
nietos(Z,X):- padre(X,D),padre(D,Z).

?- hermanos(andres,alejandra).
true

?- abuelo(luis,nicole).
true

?- tios(ruben,steven).
false

?- primos(laura,natalia).
true 

SAT(Problema de la satisfactibilidad)


SAT(Problema de satis-factibilidad)


Andrés David Rozo

20141578042


Nelson Becerra Correa


Sistematización de datos

grupo 303 2014-1


10-Julio-2014

Universidad Distrital Francisco José de Caldas

Bogotá D.C.


Índice

 

 
  1. Que es SAT?
  2. Para que sirve SAT?
  3. Cuales  revolvedores hay?
  4. Davis and Putman? 
    ¿QUE ES SAT?


fue un problema que se identificó como perteneciente a la clase de complejidad y NP-completo. En el cual trata de un problema donde interesa saber si una expresión booleana con variables y sin cuantificadores tiene asociada una asignación de valores para sus variables que hace que la expresión sea verdadera. Por ejemplo, una instancia de SAT sería el saber si existen valores para X1, X2, X3, X4   tales que la expresión:

 (X1 v ¬X3 v X4) ^ (¬X2 v X3 v ¬X4)

es cierta.

Por el contrario, el problema de si la expresión en cuestión adquiere valor falso para todas las combinaciones de sus variables, se denomina UNSAT 

 

¿PARA QUE SIRVE SAT?

 

    SAT (Problema de la satisfactibiliadad) sirve para hallar la satisfactibiliadad de una formula sin cuantificadores, en el cual emplean muchos procesos para dar solución a este problema como

Stephen Cook  que demostró SAT en 1971 con el  Teorema de Cook.

“La 3-satisfactibilidad es un caso especial de -satisfactibiliadad (-SAT), o simplemente satisfactibiliadad (SAT), en la que cada cláusula contiene exactamente 3 literales. Fue uno de 21 problemas NP-completos de Karp.

Partiendo de SAT (el caso general) se reduce a 3-SAT y SAT 3 -en 1 y se puede demostrar que son NP-completos, entonces podemos usarlos para demostrar también otros problemas NP-completos. Esto se hace mostrando cómo una solución a otro problema podría ser utilizado para resolver 3-SAT Un ejemplo de este tipo de reducción es el problema del Clique. Por lo general, es más fácil de utilizar reducción de 3-SAT que cuando se está tratando de probar que algún otro problema es NP-completo.

El SAT 3-puede ser más limitado a la 3SAT Uno-en-tres, cuando lo que pedimos sea sólo una de las variables verdadera en cada cláusula, en vez de por lo menos una. 3SAT Uno-en-tres sigue siendo NP-completo.”

 

¿CUALES RESOLVEDORES HAY?


Lista de los principales programas que resuelven el problema de satis-factibilidad

  1. WalkSAT
  2. DPLL
  3. Davis and Putman
    DAVIS AND PUTMAN
    El algoritmo de Davis-Putnam fue desarrollado por Martin Davis y Hilary Putnam para comprobar la satisfactibiliadad de las fórmulas de la lógica proposicional en forma normal conjuntiva, es decir, en conjuntos de cláusulas. Esto es una forma de resolución en la cual las variables son elegidas iterativamente y eliminadas mediante la resolución de cada cláusula en la que la variable aparece afirmada con una cláusula en la que la variable es negada.
    El algoritmo es como sigue:
           para cada variable en la fórmula
           para cada cláusula  C que contenga la variable y cada cláusula   n que contenga la negación de la variable
           resolver  C y n  y añadir la resolución a la fórmula
           eliminar todas las cláusulas originales que contengan la variable o su negación
    El nombre algoritmo Davis-Putnam o algoritmo DP a veces es empleado incorrectamente para referirse al algoritmo DPLL, el cual está relacionado pero es diferente.

BIBLIOGRAFIA