Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller09_2

Diferencias

Muestra las diferencias entre dos versiones de la página.

Enlace a la vista de comparación

Ambos lados, revisión anteriorRevisión previa
Próxima revisión		Revisión previa
introalg:taller09_2 [2009/04/06 01:12] – lauraintroalg:taller09_2 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 1: Línea 1:
-=====Consolidando conceptos de programación lógica=====+======Consolidando conceptos de programación lógica======
  
 En esta clase vamos a consolidar los conceptos que vimos en la clase anterior. Primero, vamos a repasar y profundizar algunos de los conceptos que vimos en la clase anterior. Luego, vamos a profundizar en el ejercicio de definir las relaciones familiares, tal como lo planteamos en [[http://www.cs.famaf.unc.edu.ar/wiki/doku.php?id=introalg:taller09_1#ejercicios|los ejercicios de la clase anterior]]. Para profundizar, vamos a usar algunas de las herramientas que nos ofrece prolog y SWIProlog en particular para observar cómo el intérprete de prolog trata de solucionar las preguntas que le planteamos, con una base de conocimiento dada. En esta clase vamos a consolidar los conceptos que vimos en la clase anterior. Primero, vamos a repasar y profundizar algunos de los conceptos que vimos en la clase anterior. Luego, vamos a profundizar en el ejercicio de definir las relaciones familiares, tal como lo planteamos en [[http://www.cs.famaf.unc.edu.ar/wiki/doku.php?id=introalg:taller09_1#ejercicios|los ejercicios de la clase anterior]]. Para profundizar, vamos a usar algunas de las herramientas que nos ofrece prolog y SWIProlog en particular para observar cómo el intérprete de prolog trata de solucionar las preguntas que le planteamos, con una base de conocimiento dada.
Línea 5: Línea 5:
 Para empezar la clase, vamos a crear una base de conocimiento con una de las posibles soluciones al problema de definir relaciones familiares. Abran el editor de texto, creen un archivo y copien [[http://www.cs.famaf.unc.edu.ar/wiki/doku.php?id=introalg:taller09_soluciones#familia|esta solución al problema]]. Después, ejecuten el intérprete de prolog, con el comando ''swipl'' en la terminal. Carguen en memoria la base de conocimiento sobre relaciones familiares, y empecemos. Para empezar la clase, vamos a crear una base de conocimiento con una de las posibles soluciones al problema de definir relaciones familiares. Abran el editor de texto, creen un archivo y copien [[http://www.cs.famaf.unc.edu.ar/wiki/doku.php?id=introalg:taller09_soluciones#familia|esta solución al problema]]. Después, ejecuten el intérprete de prolog, con el comando ''swipl'' en la terminal. Carguen en memoria la base de conocimiento sobre relaciones familiares, y empecemos.
  
-====Repaso====+=====Repaso=====
  
-===Cláusulas de Horn y hechos===+====Cláusulas de Horn y hechos====
  
 Los programas en Prolog se componen de ''[[http://es.wikipedia.org/wiki/Cl%C3%A1usula_de_Horn|cláusulas de Horn]]'' que constituyen reglas del tipo "[[http://es.wikipedia.org/wiki/Modus_ponendo_ponens|modus ponendo ponens]]", es decir, "Si es verdad el ''antecedente'', entonces es verdad el ''consecuente''". En prolog se escribe primero el consecuente y luego el antecedente. Por ejemplo, si quiero decir "Si llueve y no llevo paraguas, me empapo", lo escribo así: Los programas en Prolog se componen de ''[[http://es.wikipedia.org/wiki/Cl%C3%A1usula_de_Horn|cláusulas de Horn]]'' que constituyen reglas del tipo "[[http://es.wikipedia.org/wiki/Modus_ponendo_ponens|modus ponendo ponens]]", es decir, "Si es verdad el ''antecedente'', entonces es verdad el ''consecuente''". En prolog se escribe primero el consecuente y luego el antecedente. Por ejemplo, si quiero decir "Si llueve y no llevo paraguas, me empapo", lo escribo así:
Línea 41: Línea 41:
  
  
-===Variables y unificación===+====Variables y unificación====
  
 Recordemos que las reglas de prolog suelen estar expresadas con variables((En prolog las variables se escriben con la primera letra en mayúscula, para distinguirlas de las constantes, que se escriben con la primera en minúscula.)). Las variables son huecos en los que podemos poner cualquier valor, siempre que mantengamos el mismo valor para una variable con el mismo nombre dentro de una misma regla. Por lo tanto, el valor de las variables va puede ser distinto en cada ejecución. Por ejemplo, en nuestro ejemplo de la familia, en la regla ''madre(X,Y) :- mujer(X), progenitor(X,Y).'', las variables X e Y pueden tomar todos los siguientes valores: Recordemos que las reglas de prolog suelen estar expresadas con variables((En prolog las variables se escriben con la primera letra en mayúscula, para distinguirlas de las constantes, que se escriben con la primera en minúscula.)). Las variables son huecos en los que podemos poner cualquier valor, siempre que mantengamos el mismo valor para una variable con el mismo nombre dentro de una misma regla. Por lo tanto, el valor de las variables va puede ser distinto en cada ejecución. Por ejemplo, en nuestro ejemplo de la familia, en la regla ''madre(X,Y) :- mujer(X), progenitor(X,Y).'', las variables X e Y pueden tomar todos los siguientes valores:
Línea 66: Línea 66:
 A veces queremos comparar dos términos, ya sean constantes o variables a las cuales se ha asignado un valor. El mecanismo que determina si esos valores son iguales o no se llama [[http://en.wikipedia.org/wiki/Unification|unificación]], y vimos un ejercicio en la clase anterior. A veces queremos comparar dos términos, ya sean constantes o variables a las cuales se ha asignado un valor. El mecanismo que determina si esos valores son iguales o no se llama [[http://en.wikipedia.org/wiki/Unification|unificación]], y vimos un ejercicio en la clase anterior.
  
-===Términos, funciones y aridad===+====Términos, funciones y aridad====
  
 Los términos de prolog pueden ser simples (booleanos, números, constantes, variables) o complejos. Los términos complejos son ''funciones'' con argumentos, posiblemente con 0 argumentos. El número de argumentos de una función se conoce como ''aridad'', y las funciones pueden llamarse unarias si tienen un argumento, binarias si tienen dos, ternarias si tienen tres, etc.  Los términos de prolog pueden ser simples (booleanos, números, constantes, variables) o complejos. Los términos complejos son ''funciones'' con argumentos, posiblemente con 0 argumentos. El número de argumentos de una función se conoce como ''aridad'', y las funciones pueden llamarse unarias si tienen un argumento, binarias si tienen dos, ternarias si tienen tres, etc. 
  
-Las funciones (también llamadas ''predicados'') se definen con su nombre y el número de argumentos que tienen, por ejemplo:+Las funciones (también llamadas ''predicados'', porque son funciones cuyo resultado posible es ''true'' o ''false'') se definen con su nombre y el número de argumentos que toman, por ejemplo:
 <code> <code>
 llueve/0. llueve/0.
Línea 84: Línea 84:
 Muchas veces los programas fallan porque no estamos trabajando con el número correcto de argumentos de una función. Por esta razón, es muy importante fijarse en el número de argumentos de las funciones que nos aparecen en los mensajes de error o de aviso que genera prolog. Muchas veces los programas fallan porque no estamos trabajando con el número correcto de argumentos de una función. Por esta razón, es muy importante fijarse en el número de argumentos de las funciones que nos aparecen en los mensajes de error o de aviso que genera prolog.
  
-====Consultando la traza de la ejecución====+=====Consultando la traza de la ejecución=====
  
 Cuando prolog trata de resolver una pregunta o ''objetivo'', busca una cláusula de Horn que tenga ese objetivo en la cabeza, y sustituye el objetivo por el cuerpo de la cláusula. Entonces, los objetivos del intérprete pasan a ser cada una de las cláusulas del cuerpo. Por ejemplo, si preguntamos: Cuando prolog trata de resolver una pregunta o ''objetivo'', busca una cláusula de Horn que tenga ese objetivo en la cabeza, y sustituye el objetivo por el cuerpo de la cláusula. Entonces, los objetivos del intérprete pasan a ser cada una de las cláusulas del cuerpo. Por ejemplo, si preguntamos:
Línea 100: Línea 100:
 Si alguno de los objetivos es falso o no se encuentra en la base de conocimiento, el intérprete no puede llegar a un ''true'' y el objetivo falla.  Si alguno de los objetivos es falso o no se encuentra en la base de conocimiento, el intérprete no puede llegar a un ''true'' y el objetivo falla. 
  
-===Vuelta atrás o Backtracking===+====Vuelta atrás o Backtracking====
  
-Pero a veces sucede que cuando hacemos una pregunta al intérprete, éste nos dá responde ''true'', y, si le escribimos '';'' para que nos siga dando opciones, nos devuelve ''false''. Este comportamiento sigue la misma lógica que si le pedimos al intérprete los posibles valores de una variable, y nos los devuelve todos. Para resolver un objetivo, el intérprete explora todas las posibles opciones, es decir, trata de resolver todas las cláusulas que tengan al objetivo en la cabeza, que puede ser más de una. Cada una de estas posibilidades se denomina ''punto de elección''.+Pero a veces sucede que cuando hacemos una pregunta al intérprete, éste nos dá responde ''true'', y, si le escribimos '';'' para que nos siga dando opciones, nos devuelve ''false''. Este comportamiento sigue la misma lógica que si le pedimos al intérprete los posibles valores de una variable, y nos los devuelve todos. Para resolver un objetivo, el intérprete explora todas las posibles opciones, es decir, trata de resolver todas las cláusulas que tengan al objetivo en la cabeza, que puede ser más de una. Esta situación se puede entender como una disyunción: para satisfacer el objetivo, se puede hacer o bien satisfaciendo un subconjunto de objetivos (el cuerpo de una cláusula) o bien satisfaciendo otro subconjunto de objetivos (el cuerpo de otra cláusula). De hecho, es equivalente escribir dos cláusulas con la misma cabeza o escribir los cuerpos de esas dos cláusulas unidos por una disyunción en el cuerpo de una sola cláusula. Por ejemplo, serían equivalentes: 
 +<code> 
 +hasBroom(X) :- quidditchPlayer(X). 
 +wizard(X) :- hasBroom(X), hasWand(X). 
 +wizard(X) :- quidditchPlayer(X), hasWand(X). 
 +</code> 
 +y 
 +<code> 
 +hasBroom(X) :- quidditchPlayer(X). 
 +wizard(X) :- ( hasBroom(X), hasWand(X) ) ; 
 +             ( quidditchPlayer(X), hasWand(X) ). 
 +</code> 
 + 
 +Cada uno de estos puntos donde encontramos varias formas (o caminos) para que un predicado llegue a ser ''true'' o ''false'' se llaman ''punto de elección''.
  
 Cuando uno de los objetivos encontrados resulta ser falso, el intérprete vuelve para atrás hasta el punto de elección inmediatamente anterior, y busca otras reglas por las que sustituir el objetivo, y así hasta que agota todas las posibles reglas por las que sustituir el objetivo. El procedimiento de volver atrás se conoce como  [[http://es.wikipedia.org/wiki/Vuelta_Atr%C3%A1s|backtracking]], y consiste en deshacer todo lo ejecutado, situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección. Entonces se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso. Como resultado, el intérprete nos ofrece todos los resultados a los que fue llegando en esta exploración de los caminos a los que le llevan los puntos de elección. Cuando uno de los objetivos encontrados resulta ser falso, el intérprete vuelve para atrás hasta el punto de elección inmediatamente anterior, y busca otras reglas por las que sustituir el objetivo, y así hasta que agota todas las posibles reglas por las que sustituir el objetivo. El procedimiento de volver atrás se conoce como  [[http://es.wikipedia.org/wiki/Vuelta_Atr%C3%A1s|backtracking]], y consiste en deshacer todo lo ejecutado, situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección. Entonces se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso. Como resultado, el intérprete nos ofrece todos los resultados a los que fue llegando en esta exploración de los caminos a los que le llevan los puntos de elección.
  
-===Inspeccionando la traza===+====Inspeccionando la traza====
  
 Todos los dialectos de prolog nos ofrecen diversas formas de inspeccionar el proceso de backtracking de una ejecución. En SWIProlog, tenemos una interfaz gráfica y una interfaz de texto. La interfaz gráfica se ejecuta de la siguiente manera: Todos los dialectos de prolog nos ofrecen diversas formas de inspeccionar el proceso de backtracking de una ejecución. En SWIProlog, tenemos una interfaz gráfica y una interfaz de texto. La interfaz gráfica se ejecuta de la siguiente manera:
Línea 143: Línea 156:
 </code> </code>
  
-===Un ejemplo de traza===+====Un ejemplo de traza====
  
 Veamos un ejemplo de traza: Veamos un ejemplo de traza:
Línea 173: Línea 186:
 Pero esta no es la única interpretación posible. Si escribimos '';'', el intérprete vuelve atrás, aplica backtracking hasta algún punto de elección donde podría haber tomado una decisión distinta. Con la palabra clave ''Redo: '' nos indica qué subobjetivo va a rehacer, en este caso, ''progenitor(pepa, blanca)''. La evaluación de este subobjetivo resulta ahora falsa, y por lo tanto el objetivo general ''madre(pepa,blanca)'' también será falso. Así el intérprete nos lista todas las posibles soluciones a nuestra pregunta. Pero esta no es la única interpretación posible. Si escribimos '';'', el intérprete vuelve atrás, aplica backtracking hasta algún punto de elección donde podría haber tomado una decisión distinta. Con la palabra clave ''Redo: '' nos indica qué subobjetivo va a rehacer, en este caso, ''progenitor(pepa, blanca)''. La evaluación de este subobjetivo resulta ahora falsa, y por lo tanto el objetivo general ''madre(pepa,blanca)'' también será falso. Así el intérprete nos lista todas las posibles soluciones a nuestra pregunta.
  
-===Otro ejemplo de traza===+====Otro ejemplo de traza====
  
 <code> <code>
Línea 208: Línea 221:
 Por otro lado, notemos que las reglas en las que se involucra el predicado ''not/1'' están marcadas con el símbolo ''^'', esto es así para llamar nuestra atención sobre esta parte de la ejecución, ya que el comportamiento del ''no'' en prolog es muy particular. Por otro lado, notemos que las reglas en las que se involucra el predicado ''not/1'' están marcadas con el símbolo ''^'', esto es así para llamar nuestra atención sobre esta parte de la ejecución, ya que el comportamiento del ''no'' en prolog es muy particular.
  
-====Analizando problemas, sintetizando soluciones====+=====Ejercicios=====
  
-====Ejercicios====+Para proponer una solución para un problema mediante un programa informático, es crucial hacer un buen análisis del problema. En el análisis trataremos de identificar cuáles son las componentes del problema y las relaciones entre ellas. Después, crearemos una solución teniendo en cuenta nuestro análisis.
  
-  - Partiendo del [[http://www.cs.famaf.unc.edu.ar/wiki/doku.php?id=introalg:taller09_soluciones#familia|ejemplo de la familia]], ¿cómo tenemos que ampliarlo para expresar la relación "suegra" o "cuñado"? ¿y "abuelo materno"? ¿o "hermano mayor"?+Por la forma en que se maneja prolog, resulta muy directo escribir programas para cierto tipo de problemas, esencialmente, los que se pueden solucionar mediante la regla "modus ponens". Pero, como en cualquier otra aproximación formal a los problemas, resulta básico hacer un buen análisis del problema antes de ponerse a programarlo.
  
 +En los ejercicios del día de hoy van a tener que proponer soluciones para algunos problemas que seguramente conocen bien. Si las soluciones que proponen no llegan a dar los resultados que esperaban, deben hacer dos cosas:
 +  * leer bien atentamente los mensajes de error o de advertencia que les da el intérprete.
 +  * usar las herramientas que hemos visto en la clase para observar cómo está funcionando el intérprete, seguramente de una forma distinta a como ustedes están pensando.
 +
 +Traten de aportar soluciones para los siguientes problemas:
 +
 +  - Partiendo del [[http://www.cs.famaf.unc.edu.ar/wiki/doku.php?id=introalg:taller09_soluciones#familia|ejemplo de la familia]], ¿cómo tenemos que ampliarlo para expresar la relación "suegra" o "cuñado"? ¿y "abuelo materno"? ¿o "hermano mayor"?
 +  - ¿Cómo sería un programa para recomendar amigos en una red social tipo //facebook//?
 +  - ¿Cómo podemos hacer un programa **no muy largo** que, dado un animal, nos diga si es ovíparo o vivíparo, si vive en la tierra, en el agua o en el aire, si come carne o vegetales, etc.? Traten de usar generalizaciones del tipo ''si es mamífero, entonces...''. En esta aproximación, cómo tratarían excepciones como "delfín" o "guppi"?
 +  - Tenemos una lista de las conexiones por tren entre pares de ciudades, por ejemplo ''conectadas(Tarragona,Barcelona). ''. ¿Cómo sería un programa que nos ayudara a saber si podemos llegar de una ciudad a otra, es decir, si existe una lista de conexiones que nos lleve de una ciudad a otra, o bien eso es imposible? Primero, traten de hacer un programa que nos diga si podemos llegar de una ciudad a otra directamente o bien en dos o en tres pasos...
introalg/taller09_2.1238980355.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)