Prácticas de
Inteligencia Artificial
e Ingeniería del
Conocimiento I
Cuarto Curso de
Informática. Curso 2004-2005
Pedro
Álvarez Pérez Aladros
José
Angel Bañares Bañares
Pedro
Muro Medrano
F.
Javier Nogueras Iso
Javier
Zarazaga Soria
Area de Lenguajes y Sistemas
Informáticos
Departamento
de Informática e Ingeniería de Sistemas
Universidad de Zaragoza
Índice
- Programación en Common Lisp (Ficheros connect-four.lsp, minimax.lsp y practica1.lsp)
- Generación automática de frases en Common Lisp (Fichero simple1.lsp), Guión en Word, Guión en HTML.
- Representación y Búsqueda en el Espacio de Estados (Fichero misioneros.lsp), Guión en Word, Guión en HTML.
- Búsqueda ciega, heurística y en juegos con dos jugadores (Ficheros LEEME,blind_search.lsp, heuristic_search.lsp, a_star.lsp, minimax.lsp, puzzle8.lsp, tictactoesinnombres.lsp, connect_four.lsp), Guión en Word, Guión en HTML.
- Representa ción Estructurada del Conocimiento (pract5.lsp, LEEME) R
- Representación Basada en reglas (Ficheros garrafa1.clp, garrafa2.clp y garrafa3.clp)
1.Introducción
1.1 Presentación
· Descripción general: En cualquier curso relacionado con la informática, el desarrollo práctico de programas constituye un medio muy interesante para profundizar en muchos conceptos. En las prácticas del curso podrás poner en práctica algunos de los conocimientos aprendidos, para lo cual nos serviremos del lenguaje de programación Common Lisp.
· Método de trabajo: Las prácticas están pensadas de forma que siguen un desarrollo paralelo al curso. Puesto que no dispondrás de mucho tiempo para utilizar el computador es muy importante que, antes de tu hora de prácticas, estudies cuidadosamente el problema a resolver en la práctica y diseñes la estrategia a seguir y el código de Common Lisp. De este modo podrás aprovechar tu tiempo con el computador editando y comprobando el funcionamiento o comentando tus dudas.
·
Entorno de programación: Para hacer
las prácticas utilizaremos PCs disponibles en el laboratorio L1.02. Más
concretamente, utilizaremos el entorno Allegro
Common Lisp. Es un entorno potente que soporta el estándar Common Lisp. Si tienes a tu disposición
un Macintosh, o un PC puede resultar interesante que prepares tus prácticas, o los trabajos propuestos para casa con
él. Para ambos computadores existe Allegro
Common Lisp.
·
Para invocar este entorno accede a:
->Programas
->Allegro CL Enterprise Edition
5.0
-> Allegro CL Enterprise Edition 5.0 (with IDE)
· Cual es tu trabajo: En primer lugar, deberás hacer y conocer todas las prácticas, es decir, deberás poder justificar las estructuras de datos y control utilizadas así como las estrategias elegidas, tanto de los programas que te proporcionemos nosotros como de los que tu definas.
- En cada sesión de prácticas solo se podrá trabajar con la práctica prevista para ese día.
- En http://diana.cps.unizar.es/banares/IA/IA.html encontrarás este guión de prácticas y todos los ficheros relacionados. En esta hoja de Web aparecerán noticias e información relacionada con la asignatura.
2.Práctica 1
Programación en Common Lisp
2.1 Objetivo
El objetivo de esta práctica es familiarizarse con el lenguaje Common Lisp y con el entorno de programación. Más concretamente, utilizaremos el entorno Allegro Common Lisp.
Por otra parte, veremos la utilidad de utilizar funciones recursivas y funciones de alto nivel en Common Lisp. Así comprobarás sus facilidades para hacer “mapping”, transformar, filtrar, contar o encontrar elementos particulares dentro de estructuras de datos como listas y estructuras. Common Lisp cuenta con un amplio repertorio de funciones, por lo que es importante adquirir el hábito de comprobar si el lenguaje ofrece una función antes de proceder a su implementación. Utiliza la ayuda en línea (clman).
Al finalizar la práctica deberás saber editar, ejecutar y compilar un programa Common Lisp. Además, como objetivo secundario se deben conocer las herramientas de depuración LISP. Busca información de las funciones TRACE, STEP, BREAK, DESCRIBE, DOCUMENTATION, TIME. (En el capítulo 10 del Wiston (LISP) se explican brevemente las primitivas de depuración. Recuerda también que puedes acceder al manual de referencia de Steele en la página web de la asignatura: http://diana.cps.unizar.es/banares/IA/libros/cltl2e/clm.html).
2.2 Parte A. Familizarización con el entorno de programación
Antes de realizar programas en Lisp realiza la siguientes tarea con objeto de familiarizarte con el entorno de programación lisp.
2.2.1.1 Tarea
Ø Escribe el siguiente código en lisp. Consulta las funciones que no conozcas con clman:
(dribble “primera.trz”)
(defparameter *numeros* '(1 2 3 4 5))
(car *numeros*)
(first *numeros*)
(cdr *numeros*)
(rest *numeros*)
*numeros*
(setq *numeros* (cdr *numeros*))
(cons 1 *numeros*)
*numeros*
(setq *numeros* (cons 1 *numeros*))
(+ (first *numeros*)(second
*numeros*))
(> (first
*numeros*)(second *numeros*))
(< (first
*numeros*)(third *numeros*))
(append *numeros* (reverse *numeros*))
(defun ultimo(l) (car (last l)))
(ultimo '(a b c))
(ultimo (ultimo '(a (b (c)))))
(defun ordenado?(lista)
(or (null (cdr
lista))
(and (< (first lista) (second lista))
(ordenado?
(cdr lista)))))
(ordenado? *numeros*)
(ordenado? (append *numeros* *numeros*))
(dribble)
2.3 Parte B. Uso de un programa de juegos
Evalúa el fichero minimax.lsp y el fichero connect-four.lsp, y escribe las siguientes funciones lisp:
(dribble “juego.trz”)
(play)
(dribble)
El computador dibuja un tablero para jugar a cuatro en raya y espera un numero del 0 al 6 indicando tu movimiento. Cuando realices un movimiento aparecerá una X en el último cuadro sin ocupar de la columna que indicaste. A continuación el computador hará un movimiento y esperará tu siguiente movimiento. Gana el que antes haga 4 en raya (horizontal, vertical o diagonalmente).
Puedes repetir el juego, esta vez sin registrar la traza y evaluando los ficheros compilados. Los ficheros compilados tienen la extensión .fasl. Si evalúas los ficheros compilados comprobarás que la ejecución es mucho más rápida.
2.4 Parte C. Trabajo con Lisp
El ejemplo que se aborda en esta parte es la organización de una pequeña base de datos para almacenar la información de libros de una Biblioteca[1]. Para ello hemos creado una librería de funciones de utilidad que nos facilitan el tratamiento. El programa fuente practica1.lsp lo encontrarás en el directorio
La base de datos contiene información acerca del título, autor, clasificación por palabras claves y año de edición de cada libro. En la versión propuesta la estructura de datos elegida para cada libro consiste en una lista con tres listas internas cuyos car respectivos son las palabras clave titulo, autor, clasificacion y agno. Para abstraer al usuario de la estructura de datos utilizada se ha definido el constructor (los parámetros identifican los valores de cada campo):
(crea-libro titulo autor clasificacion agno)
Ø Piensa como se podrían poner esos parámetros identificados por claves (acuérdate de la opción &key de una lambda expresión).
Idénticamente se han definido las funciones:
(libro-titulo
libro)
(libro-autor
libto)
(libro-clasificacion libro)
Se proporcionan también utilidades para recopilar información de la base de datos:
· De un campo concreto: (lista-autores libros).
· Con un acceso más profundo dentro de la estructura de datos:
(lista-libros-de-ficcion libros)
(cuenta-libros-ficcion libros)
(apellidos-de-autores libros)
Podrás encontrar también diversas versiones de algunas de estas funciones, así podrás comprobar diferentes implementaciones y sus distintas eficiencias.
2.4.1 Tarea
Ø Primero lee detenidamente el listado del código y trata de entender el funcionamiento de las funciones. Para hacer esto será necesario que tengas a mano tus apuntes de Lisp o algún libro.
Ø Tu primer trabajo consistirá en sustituir la estructura de datos utilizada para almacenar la información de los libros por una composición basada en estructuras (defstruct). Por supuesto, tendrás que modificar la implementación de las funciones para que realicen la misma tarea que realizaban con la estructura de datos anterior, teniendo cuidado en que no se modifique el lenguaje utilizado por el usuario para la manipulación de la base de datos de los libros. Para hacer este apartado podrás reutilizar gran parte del código que te proporcionamos.
Ø Debes crear una nueva función que reciba un libro y muestre su información por pantalla con un formato agradable:
(escribe-libro-en-bonito libro)
Ø Hacer disponible al usuario la función:
(listado-palabras-clave libros)
Esta función debe recibir como parámetro una base de datos de libros y debe devolver el listado de todas las palabras clave (sin repeticiones de palabras).
Ø Hacer disponible al usuario la función:
(ordenar
libros #'por-antiguedad)
La función debe recibir como primer parámetro una base de datos de libros y como segundo argumento una función que tome como argumentos dos elementos de la lista y devuelva T si y sólo si el primer argumento es estrictamente menor que el segundo en algún sentido. Por ejemplo la función por-antiguedad devuelve T si el año de edición del primer argumento es menor que el del segundo argumento.
Ordena los libros por antigüedad, y a continuación ordena la lista resultante colocando al principio los que tengan un mayor numero de palabras claves en la lista clasificacion.
Ø Registra con dribble en un fichero la comprobación de las funciones definidas.
2.5 Listado de las funciones suministradas
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; iaaa iaaa iaaa iaaa iaaa iaaa iaaa iaaa iaaa iaaa ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;;
;;; idea: winston
;;; creado: 13-2-1991
;;; modificado : 14-4-94 muro
;;; 20-20-95 bagnares
;;;
;;; Departamento de Informatica e Ingenieria de Sistemas
;;; Centro Politecnico Superior
;;; Universidad de Zaragoza
;;;
;;; Titulo: Libros de una Biblioteca
;;;
; Esta practica es la organizacion de una pequena base de datos para
;almacenar la informacion de libros de una biblioteca.
; Para ello hemos creado una libreria de funciones de utilidad que nos
;facilitan el tratamiento.
; La base de datos contiene informacion acerca del titulo, autor y
;clasificacion por palabras claves de cada libro.
; En la version propuesta la estructura de datos elegida para cada libro
;consiste en una lista con tres listas internas cuyos 'car' respectivos
;son las palabras clave 'titulo', 'autor' y 'clasificacion'.
;Para abstraer al usuario de la estructura de datos utilizada se ha
;definido el constructor (los parametros identifican los valores de
;cada campo):'(crea-libro titulo autor clasificacion)'.
(defun crea-libro (titulo autor clasificacion agno)
(LIST (LIST 'TITULO TITULO)
(LIST 'AUTOR AUTOR)
(LIST 'CLASIFICACION CLASIFICACION)
(LIST 'AGNO AGNO)))
;Este constructor crea un nuevo libro
(setf libro-ejemplo
(crea-libro '(Common Lisp)
'(Guy steele)
'(Tecnico Lisp)
'1991))
; Para seguir con el constuctor creamos un conjunto de lectores:
(defun libro-titulo (libro)
(second (assoc 'titulo libro)))
(defun libro-autor (libro)
(second (assoc 'autor libro)))
(defun libro-clasificacion (libro)
(second (assoc 'clasificacion libro)))
(defun libro-agno (libro)
(second
(assoc 'agno libro)))
;Creamos ahora un procedimiento para cambiar el autor
(defun libro-cambio-autor (libro autor)
(if (eql 'autor
(first (first libro)))
(cons (list 'autor autor) (rest libro))
(cons (first libro)
(libro-cambio-autor (rest libro) autor))))
;Ahora construimos mas libros en la base de datos:
(setf bdlibros
(list
(crea-libro '(Common Lisp)
'(Guy L. Steele)
'(Tecnico Lisp)
'1991)
(crea-libro '(Artificial Intelligence)
'(P. H. Winston)
'(Tecnico IA)
'1989)
(crea-libro '(Moby Dick)
'(H. Melville)
'(Ficcion)
'1850)
(crea-libro
'(Tom Sawyer)
'(M. Twain)
'(Ficcion)
'1894)
(crea-libro
'(The Black Orchid)
'(Rex Stout)
'(Ficcion Misterio)
'1710)))
;FILTRADO DE DATOS
; Puede ser interesante sacar listados que contengan informacion parcial de
;la base de datos. Esto es, se requiere un filtrado.
(defun lista-autores (libros)
(if (null
libros)
nil
(cons (libro-autor (first libros))
(lista-autores (rest libros)))))
; Se puede hacer un filtro que acceda a mayor profundidad:
; Primero creamos una funcion booleana que diga si un libro cumple la
;condicion, p.e. que sea de ficcion.
(defun ficcionp (libro)
(member 'ficcion (libro-clasificacion libro)))
; Ahora la podemos usar para encontrar todos los libros de ficcion:
(defun lista-libros-de-ficcion (libros)
(cond ((null libros) nil)
((ficcionp (first libros))
(cons
(first libros)
(lista-libros-de-ficcion (rest libros))))
(t (lista-libros-de-ficcion (rest libros)))))
;;; TAMBIEN ES POSIBLE CONTAR Y ENCONTRAR
;(length (LISTA-LIBROS-DE-FICCION bdlibros))
; Tambien se puede acceder a uno cualquiera de la lista:
; (first (LISTA-LIBROS-DE-FICCION bdlibros))
;Pero esto es muy poco eficiente porque se necesita crear nuevas listas.
;Pero puede contarse directamente:
(defun cuenta-libros-ficcion (libros)
(cond ((null libros) 0)
((ficcionp (first libros))
(+ 1 (cuenta-libros-ficcion (rest libros))))
(t (cuenta-libros-ficcion (rest libros)))))
(defun encuentra-primer-libro-ficcion (libros)
(cond ((null libros) nil)
((ficcionp (first libros))
(first libros))
(t (encuentra-primer-libro-ficcion (rest libros)))))
;Observar los patrones que se repiten en las funciones anteriores.
;;; Funciones de MAPPING
;Para facilitar las cosas
;(lista-autores bdlibros)
;(mapcar #'libro-autor bdlibros)
(defun libro-autor-apellido (libro)
(first (last (libro-autor libro))))
;(mapcar #'libro-autor-apellido bdlibros)
;(mapcar #'(lambda (libro) (first (last (libro-autor libro)))) bdlibros)
;;; Para simplificar las operaciones de filtrado: REMOVE-IF y REMOVE-IF-NOT
;(remove-if-not #'ficcionp bdlibros) ;elimina si NO se verifica la condicion
;(remove-if #'ficcionp bdlibros) ;elimina SI se verifica la condicion
;(count-if #'ficcionp bdlibros) ;cuenta SI se verifica la condicion
;(find-if #'ficcionp bdlibros) ;encuentra SI se verifica la condicion