Sistemas LI
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
- Que es SAT?
- Para que sirve SAT?
- Cuales revolvedores hay?
- 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
“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
- WalkSAT
- DPLL
- Davis and PutmanDAVIS AND PUTMANEl 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ónEl 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
Suscribirse a:
Entradas (Atom)
