1. No category

Chapter 1
Lenguajes de programación para
resolver problemas
Objetivo
El alumno podrá instrumentar programas de Inteligencia Artificial
Figure 1.1: Pregunta incómoda
Un lenguaje de programación es un lenguaje artificial diseñado para expresar instrucciones
que pueden ser llevadas a cabo por máquinas como las computadoras. De acuerdo al nivel de
abstracción, se clasifican en lenguajes de bajo nivel y lenguajes de alto nivel.
Un programa es un conjunto de instrucciones que una vez ejecutadas realizarán una o varias
tareas en una computadora.
1.1
Estructuras básicas
De acuerdo al paradigma de programación que utilizan, los lenguajes se pueden clasificar como
imperativos o declarativos.
♦ La programación imperativa describe la programación en términos del estado del programa y sentencias que cambian dicho estado. Los programas imperativos son un conjunto
1
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
2
de instrucciones que le indican a la computadora cómo realizar una tarea.
♦ La programación declarativa es un paradigma de programación que está basado en el
desarrollo de programas especificando o "declarando" un conjunto de condiciones, proposiciones, afirmaciones, restricciones, ecuaciones o transformaciones que describen el problema
y detallan su solución. La solución es obtenida mediante mecanismos internos de control,
sin especificar exactamente cómo encontrarla, tan sólo se le indica a la computadora qué es
lo que se desea obtener o qué es lo que se está buscando.
Lenguajes de
Programación
Estructurados
C
Pascal
COBOL
php
...
Imperativos
Declarativos
Orientados a
Objetos
Funcionales
Python
C++
Java
C#
php5
...
Lógicos
Prolog
CLIPS
...
Haskell
LISP
Dr. Scheme
Dr. Racket
...
Figure 1.2: Clasificación de lenguajes de acuerdo al paradigma
Un programa (algoritmo) contiene instrucciones elementales seleccionadas cuidadosamente que
pueden ser realizadas por un robot ó un procesador; el procesador recibe las órdenes y ejecuta lo
que indican, resulta obvio que la disposición de las instrucciones resulta crucial al momento de
llevarlas a cabo. Por tanto, el algoritmo debe incluir instrucciones de control que modifiquen la
ruta que debe seguir el procesador, además de indicar que debe hacerse en cada paso, así como el
momento en el cual debe detenerse.
Se ha probado que para implementar cualquier algoritmo, son suficientes tres construcciones
básicas para control de flujo:
♦ Secuencia.
♦ Condicional.
♦ Ciclos iterativos (repetitivos).
A continuación se describe cada una de ellas y se muestra su representación en pseudocódigo.
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
3
Ejecución secuencial
La ejecución secuencial consiste en ejecutar una instrucción y al terminar, realizar lo que indica
el siguiente paso del algoritmo.
. . .
n. Instrucción i
o. Instrucción i+1
. . .
Figure 1.3: Ejecución secuencial
Ejecución condicional
Consiste en ejecutar un grupo de acciones A ó un grupo de acciones B (pero no ambos) en función
del resultado de la evaluación de una condición C (V erdadero ó F also).
. . .
n. SI c ENTONCES
n.1. Subinstrucción 1
. . .
n.k. Subinstrucción k
o. SI NO
o.1 Subinstrucción 1
. . .
o.j. Subinstrucción j
. . .
Figure 1.4: Ejecución condicional
Un algoritmo que sólo contiene las estructuras de control anteriores funciona para tareas de
longitud fija, dado que cada instrucción se ejecuta solamente una vez. Sin embargo, generalmente
se requiere que algunas instrucciones sean ejecutadas más de una vez, para esto, existen estructuras
de control que se encargan de la ejecución repetida de bloques de instrucciones, se conocen de
forma genérica como estructuras iterativas o ciclos.
Iteración definida
Sirve para ejecutar un grupo de instrucciones A exactamente N veces, donde N es un entero
positivo.
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
4
. . .
n. DESDE cont←1 HASTA N
n.1. Subinstrucción 1
. . .
n.k. Subinstrucción k
n.k+1 cont←cont+1
. . .
Figure 1.5: Iteración definida
Iteración condicional.
Conocida también como iteración indefinida, se utiliza para repetir un bloque de acciones A,
mientras una condición C sea verdadera, C es una condición de paro.
. . .
n. MIENTRAS c HACER
n.1. Subinstrucción 1
. . .
n.k. Subinstrucción k
. . .
Figure 1.6: Iteración condicional
1.2
Estructuras compuestas
Actualmente existen lenguajes de programación (tanto imperativos como declarativos) más expresivos, entre otras cosas incluyen estructuras de datos compuestas (conocidas como tipos abstractos
de datos ADT ) entre sus tipos básicos. Esto permite desarrollar aplicaciones en tiempos mucho
más cortos.
1.2.1
Listas
Una lista (list) consiste de una secuencia de nodos, en los que se almacenan campos de datos
arbitrarios y una o dos referencias (apuntadores) al nodo anterior o posterior. La ventaja principal
de las listas ligadas respecto a los arreglos es que el tamaño de la misma puede crecer y disminuir
en tiempo de ejecución, es decir, no es necesario conocer el tamaño máximo de la lista desde el
principio.
1.2.1.1
Lista ligada
Una lista ligada (linked list) es un tipo de dato recursivo que es una lista vacía (nulo, nil o null )
o una referencia a un nodo compuesto de un dato y una referencia a una lista ligada.
Figure 1.7: Lista ligada
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
5
Las operaciones y la complejidad temporal asintótica de las mismas se muestran en la siguiente
tabla:
Operación
crearListaCircular ()
esV acia (l)
insertar (l, x)
buscar (l, x)
sacar (l, x)
1.2.1.2
Orden
O (1)
O (1)
O (1)
O (n)
O (n)
Lista doblemente ligada
Una lista doblemente ligada (doubly linked list) consiste de una secuencia de nodos, en los que
se almacenan campos de datos arbitrarios y dos referencias (apuntadores) al nodo anterior y
siguiente.
Figure 1.8: Lista doblemente ligada
La complejidad temporal asintótica de las operaciones es:
Operación
crearListaDobleLigada ()
esV acia (l)
insertar (l, x)
buscar (l, x)
sacar (l, x)
Orden
O (1)
O (1)
O (1)
O (n)
O (n)
La lista es un ADT muy importante, ya que tomando como base una listas se pueden implementar otros ADT (como pilas o colas) sin la restricción de tener un número máximo de elementos
a almacenar.
1.2.2
Tablas de símbolos
Un caso particular de los métodos de hash, son las llamadas tablas de símbolos. Su objetivo
principal es asociar un valor con una llave (comúnmente una cadena). Se pueden insertar parejas
clave-valor esperando que posteriormente se puede recuperar el valor asociado a una llave dada.
Estas operaciones son tan importantes en muchas aplicaciones computacionales que las tablas
de símbolos se encuentran disponibles en muchos lenguajes de programación, por ejemplo:
♦ En php se dispone de arreglos asociativos.
♦ Python provee el tipo básico diccionario.
♦ En java se utiliza la clase Hashtable, etc.
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
6
Figure 1.9: Diccionario en Python
La definición del ADT tabla de símbolos es la siguiente:
Una tabla de símbolos es una estructura de datos que almacena parejas llave-valor y que
soporta las operaciones de:
♦ Insertar una nueva pareja llave-valor.
♦ Buscar el valor asociado a una llave.
♦ Eliminar una pareja llave-valor.
Idealmente, una tabla de símbolos realiza las operaciones de insertar y buscar sean O (1) en el peor
caso. Sin embargo, esto sólo sucede si se tiene conocimiento a priori, es decir, se sabe de antemano
qué elementos se almacenarán; desafortunadamente, en general no se tiene esta información. Por
lo tanto, solo se garantiza obtener O (1) para el caso promedio.
1.2.3
Árboles
Un árbol es una gráfica acíclica dirigida totalmente conexa en la que cada nodo tiene cero o más
nodos hijos y a lo más un nodo padre.
Solamente puede existir un nodo que no tiene padre, llamado nodo raíz , los nodos que no
tienen hijos se llaman nodos hoja y los nodos intermedios (que tiene padre e hijos) se llaman
nodos rama o subárboles.
Figure 1.10: Un árbol
1.2.3.1
Representación de árboles en la computadora
Una manera de representar un árbol es la siguiente.
Nodo :
dato : e n t e r o
#data
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
7
h i j o s : l i s t a D e N o d o s #h o j a => l i s t a v a c í a
Arbol :
Arbol : Nodo
Esta definición tiene un problema en la representación de lista de nodos hijos, si se hace
mediante un arreglo, se tiene el problema de calcular el máximo número de hijos posibles, si
se utiliza una lista, la estructura completa se puede volver muy compleja, dado que incluirá la
estructura del mismo árbol dentro de la estructura de una lista ligada.
Figure 1.11: Un árbol que utiliza la representación de lista de hijos
Una forma alternativa de representar un árbol es la siguiente.
Nodo :
dato : e n t e r o
h i j o : Nodo
hermano : Nodo
#data
#h o j a => h i j o=n u l o
Arbol :
Arbol : Nodo
En esta forma de representar árboles, cada nodo apunta a su nodo hermano siguiente, de forma
tal que el problema de representar la lista de todos los hijos desaparece.
Figure 1.12: Un árbol que utiliza la representación de nodos hermanos
Otro atractivo de esta representación es que se obtiene una estructura muy conocida: árbol
binario.
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
8
Inducción estructural
La inducción estructural es un método de demostración utilizado en lógica matemática, computación y en otras áreas. Se trata de una generalización de la inducción matemática. Una
prueba por inducción estructural consiste en demostrar que una proposición se cumple para todos
los elementos mínimos del tipo (caso base), y si la propiedad se cumple para todas las subestructuras de una cierta estructura S, entonces se debe cumplir también para S.
Listas
Por ejemplo, considerando las siguientes funciones recursivas sobre listas:
longitud [ ]
longitud (h : t )
= 0
= 1 + longitud t
( long1 )
( long2 )
[ ] ++ l i s t a = l i s t a
( h : t ) ++ l i s t a = h : ( t ++ l i s t a )
( concat1 )
( concat2 )
donde:
♦ [ ] denota la lista vacía.
♦ (h:t) es una lista en la que h representa el primer elemento (head ) y t denota el resto (tail )
de la lista.
♦ ++ denota la operación de concatenación de listas.
Y se desea probar la propiedad:
l o n g i t u d (L ++ M) = l o n g i t u d L + l o n g i t u d M
El caso base se tiene cuando L es [ ]:
l o n g i t u d ( [ ] ++ M) = l o n g i t u d M
longitud [ ] + longitud M = 0 + longitud M
{ concat1 }
{ long1 , a r i t m é t i c a }
Ahora se debe demostrar que la propiedad se cumple cuando L es una lista no vacía. Como L
es no vacía, debe ser de la forma x :xs para un elemento x y una lista xs. La hipótesis inductiva
dice que la propiedad se cumple para cualquier lista M cuando L es xs:
l o n g i t u d ( xs ++ M) = l o n g i t u d xs + l o n g i t u d M
( hip )
Para demostrar que la propiedad se cumple también para cualquier lista M cuando L es x :xs,
se deben utilizar las definiciones de las funciones y la hipótesis inductiva:
l o n g i t u d ( ( x : xs)++ M) =
l o n g i t u d ( x : ( xs ++ M) ) =
1 + l o n g i t u d ( xs ++ M) =
1 + l o n g i t u d xs + l o n g i t u d M =
l o n g i t u d ( x : xs ) + l o n g i t u d M
{
{
{
{
concat2 }
long2 }
hip . }
long2 }
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
9
Árboles
Considerando las siguientes definiciones recursiva de árbol binario:
Arbol i n t = Hoja i n t | Rama ( Arbol i n t Arbol i n t )
Y las siguientes funciones recursivas sobre esta estructura:
nHojas Hoja
nHojas Rama ( I D)
= 1
= nHojas I + nHojas D
( hojas1 )
( hojas2 )
nNodos Hoja
nNodos Rama ( I D)
= 0
= 1 + nNodos I + nNodos D
( nodos1 )
( nodos2 )
Y se desea probar la propiedad:
nHojas (A) = nNodos (A) + 1
El caso base se tiene cuando A es una Hoja:
nNodos Hoja
nHojas Hoja
= 0
= 1
{ nodos1 }
{ hojas1 }
La hipótesis inductiva dice que la propiedad se cumple para cualquier subárbol izquierdo I y
derecho D.
nHojas ( I ) = nNodos ( I ) + 1
nHojas (D) = nNodos (D) + 1
( hip1 )
( hip2 )
Para demostrar que la propiedad se cumple también para cualquier árbol A que se compone
de un subárbol izquierdo I y otro derecho D, se deben utilizar las definiciones de las funciones y
la hipótesis inductiva:
nHojas Rama ( I D) = nNodos Rama ( I D) + 1
nHojas I + nHojas D
=
nNodos ( I ) + 1 + nNodos (D) + 1 =
nNodos ( I ) + nNodos (D) + 2
1 + nNodos I + nNodos D + 1 =
nNodos ( I ) + nNodos (D) + 2
{
{
{
{
{
hojas2 }
hip1 , h i p 2 }
aritmética }
nodos2 }
aritmética }
Otra propiedad interesante es la siguiente:
♦ Si A es un árbol binario, entonces nN odos (a) ≤ 2altura(A)+1 − 1.
Para probar esta propiedad, será necesario definir la función altura, que devuelve el número de
nodos existentes entre la raíz y la hoja más lejana a ésta.
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
1.3
10
Programación funcional
Cálculo lambda
La programación funcional está inspirada en un fundamento de teoría de la computabilidad diferente a la basada en las máquinas de Turing, pero equivalente en el sentido de que puede resolver
el mismo conjunto de problemas: el cálculo − λ.
La sintaxis del cálculo − λ es extremadamente austera y puede expresarse en una sola línea:
M ::= X| (M M ) | (λX.M )
Donde: X es un no terminal que representa una variable genérica, M es el símbolo inicial, el
punto y los paréntesis son símbolos terminales.
También puede darse en forma extendida:
expr →
|
|
|
|
constante
variable
expr expr
(expr)
λvariable.expr
Las constantes son números, las variables son identificadores y operandos.
El alcance de una expresión λ se extiende a la derecha hasta donde sea posible, i.e. λx.xy
quiere decir (λx. (xy)) y no ((λx.x) y). Sin embargo, es común no usar la convención y utilizar
los paréntesis para evitar confusiones. También es común hablar de subtérminos: (xy) es un
subtérmino de (λx. (xy)), pero λx no lo es.
En una expresión, cada variable puede ser libre (sin relación con una λ) o ligada (argumento
de una λ). Ser libre o ligada está en función de la posición de cada variable y de su contexto
(figura 1.13).
Figure 1.13: Variables libres y ligadas
Por ejemplo, en λx. ∗ 2 x, x es una variable ligada, puede verse como un parámetro formal de
una función: ∗ 2 x es el cuerpo.
El cuerpo puede ser cualquier expresión lambda válida, incluso otra función: λx.λy.∗ (+ x y) 2:
“la función de x que regresa la función de y que regresa el producto de la suma de x y y con 2”.
La abstracción del operador enlaza la variable sobre la que actúa, en ambos sentidos:
♦ Semánticamente: el renombramiento consistente de una variable ligada no modifica la
semántica de la expresión
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
11
♦ Sintácticamente: posibles substituciones no tienen efecto en variables ligadas.
En efecto, el nombre de la variable no es importante cuando se aplica un operador λ, solo la forma
en la que se utiliza. En otra palabras, dos términos se consideran equivalentes que solo difieren
en el nombre de sus variables ligadas. Por ejemplo: λx.x y λy.y; o λx.λy.x y λv.λw.v.
Tarea Leer:
♦ “¿Qué define un lenguaje funcional? ” (http://bit.ly/11yf3zK).
• Right definition: A functional programming language is a language that emphasises
programming with pure functions and immutable data.
♦ “El robot y el bebé” (http://stanford.io/1hTZNLg) de John McCarthy (http://bit.ly/XQa3HI)
Y dar una pequeña opinión (no resumen) por cada lectura y por cada integrante del equipo; en
el caso del cuento escrito por McCarthy, describir cómo se relaciona a la IA con otras disciplinas
(computabilidad, ética, filosofía, lógica, etc.).
Evaluación de expresiones lambda
El cálculo lambda puro no tiene funciones predefinidas, por el momento lo usaremos de forma
impura. Para evaluar (+ (∗ 5 6) (∗ 8 3)) no es posible iniciar con + porque solo opera sobre
números. Antes existen dos expresiones ruducibles: (∗ 5 6) y (∗ 8 3); por tanto el proceso es el que
se muestra en la figura 1.14:
Figure 1.14: Evaluando una expresión
Similar a derivar una sentencia a partir de una gramática.
Cómputo: usando la β-reducción
Para recuperar la pureza del cálculo lambda se utiliza la β-reducción (figura 1.15).
Figure 1.15: β-reducción
Un parámetro formal puede usarse muchas veces (figura 1.16).
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
12
Figure 1.16: Uso múltiple del parámetro
Con más parámetros (figura 1.17).
Figure 1.17: Múltiples parámetros
Las funciones pueden ser argumentos (figura 1.18).
Figure 1.18: Funciones como argumentos
Hay que tener cuidado con nombres repetidos para las variables (figura 1.19).
Figure 1.19: Nombres repetidos
En la primer línea, la x más interna pertenece a la λ más interna, mientras la x más externa
pertenece a la λ externa. Es común tratar de evitar usar el mismo nombre de variable usando la
α-equivalencia (figura 1.20).
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
Figure 1.20: Uso de la α-equivalencia
Cálculo lambda para programadores (http://goo.gl/pwYCyc).
Cálculo lambda en el navegador (http://goo.gl/ym2dAU).
1.3.1
Dr. Racket
Sitio: http://racket-lang.org/
How to Design Programs: http://bit.ly/gZOOtU
Figure 1.21: Evaluación perezosa
13
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
1.4
14
Programación lógica
La programación lógica es uno de los paradigmas de programación más alejados del imperativo.
Un sistema de demostración de teoremas funciona como un mecanismo computacional. La programación lógica es declarativa: un programa es una declaración de qué se desea, y no una receta
de cómo obtenerlo.
En la práctica, no siempre se puede alcanzar este ideal, por cuestiones de eficiencia. La fundamentación semántica de la programación lógica son los modelos de Herbrand. El lenguaje Prolog
es un compromiso entre los principios de la programación lógica y la eficiencia de implementación.
1.4.1
Cláusulas definidas
En principio se podría tener un lenguaje de programación lógica que abarcara todo el cálculo de
predicados de primer orden. Por cuestiones de eficiencia computacional nos ocuparemos sólo de
las fórmulas que se ajustan a una sintaxis particular y que se conocen como cláusulas definidas.
α ← β1 , . . . , β n
La fórmula α se conoce como el encabezado, mientras que β1 , . . . , βn son el cuerpo. Una
fórmula puede caracer de cuerpo o de encabezado, y en este último caso se llamará meta. Un
programa lógico es un conjunto de cláusulas definidas, ninguna de las cuales es una meta.
Por otra parte, conviene notar que de acuerdo con nuestra notación una meta equivale a la
negación del enunciado:
← β ≡ ¬β
Ejemplo:
1. P12 (c, f1 (c)) ←
2. P12 (f1 (c) , f1 (c)) ←
3. P12 f1 (f1 (x)) , f12 (y, z) ← P12 (x, y) , P12 (f1 (x) , z)
Interpretando la constante c como 0, las funciones f1 como sucesor y f12 como +; P12 corresponde
a una relación que asocia el natural n con el n-ésimo número de Fibonacci.
Para hacer más transparentes los programas lógicos, se suelen incluir símbolos que hagan obvia
su interpretación. El programa anterior se puede rescribir así:
1. F ib (0, s (0)) ←
2. F ib (s (0) , s (0)) ←
3. F ib (s (s (x)) , y + z) ← F ib (x, y) , F ib (s (x) , z)
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
1.4.2
15
Resolución
La resolución es una regla de inferencia que permite demostrar teoremas por medio de refutación.
Supóngase que se tiene un programa lógico Γ y se quiere demostrar que una fórmula atómica α
se sigue de Γ. Entonces se incluye como premisa la meta ← α (es decir, ¬α). Una demostración
por resolución nos permitirá derivar fórmulas hasta que, en caso de éxito, lleguemos a una contradicción y entonces se afirmará que α se sigue de Γ.
Resolución
α ← β1 , . . . , βn
← α, γ1 , . . . , γk
← β1 , . . . , βn , γ1 , . . . , γk
Las dos premisas son resolventes y la conclusión es la resolución.
`R denota los teoremas de resolución y Res es nombre de la regla. Prog significa “cláusula del
programa lógico”.
Ejemplo;
♦ q ∧ r ⇒ p, q, r `R p:
SWI-Prolog: http://www.swi-prolog.org
Ejemplos:
♦ Gustos:
% ejem . p l
% c o n s u l t ( ejem ) .
l e _ g u s t a ( f u l a n o , agua ) .
le_gusta ( fulano , cerveza ) .
le_gusta ( fulano , r e f r e s c o ) .
le_gusta ( fulano , l e c h e ) .
l e _ g u s t a ( zutano , c e r v e z a ) .
l e _ g u s t a ( zutano , r e f r e s c o ) .
l e _ g u s t a ( mengano , agua ) .
l e _ g u s t a ( mengano , l e c h e ) .
Consultas al intérprete:
?−
?−
?−
?−
?−
le_gusta ( fulano , X) .
l e _ g u s t a ( zutano , Y ) .
l e _ g u s t a ( mengano , Z ) .
l e _ g u s t a (X, agua ) .
l e _ g u s t a (X, Y ) .
♦ Pertenencia a un rango:
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
% Y < X < Z
p e r t e n e c e (X, Y, Z): − X>Y, X<Z .
Consultas:
?− p e r t e n e c e ( 5 , 3 , 7 ) .
?− p e r t e n e c e ( 3 , 5 , 7 ) .
N:
% Sucesor
suc ( 0 , 1 ) .
s u c (X,Y): − X>0, Y i s X+1.
% D e f i n i c i ó n de l o s n a t u r a l e s
n( c ) .
n ( s (X)): − n (X ) .
Consultas:
?−
?−
?−
?−
suc (0 ,Z ) .
suc (5 ,Z ) .
n( c ) .
n ( s (X ) ) .
♦ Tipográficamente, la suma puede definirse como:
a+0 = a
a+s ( b ) = s ( a+b )
En prolog:
suma ( c , Y,Y): − n (Y ) .
suma ( s (X) ,Y, s (Z)): − suma (X, Y, Z ) .
Consultas:
?−
?−
?−
?−
suma ( s ( s ( c ) ) , s ( c ) , s ( s ( s ( c ) ) ) ) .
suma ( s ( s ( c ) ) , s ( c ) , Z ) .
suma ( s ( c ) ,Y, s ( s ( c ) ) ) .
suma (X, s ( c ) , s ( s ( c ) ) ) .
♦ Tipográficamente, la multiplicación se define como:
a·0 = 0
a · s ( b ) = ( a · b )+a
En prolog:
¿?
♦ Factorial tipográfico:
16
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
17
fact (0 , s ( 0 ) ) .
f a c t ( s (X) ,Y∗ s (X)): − f a c t (X,Y ) .
Consultas:
?− f a c t ( 0 ,Y ) .
?− f a c t ( s ( 0 ) ,Y ) .
?− f a c t ( s ( s ( s ( 0 ) ) ) ,Y ) .
♦ Factorial numérico:
fact2 (0 ,1).
f a c t 2 (X,Y): − X>0, X1 i s X−1, f a c t 2 (X1 , Y1 ) , Y i s X∗Y1 .
Consultas:
?− f a c t ( 0 ,Y ) .
?− f a c t ( 6 ,X ) .
♦ Fibonacci tipográfico:
f i b (0 , s ( 0 ) ) .
fib ( s (0) , s (0)).
f i b ( s ( s (X) ) ,Y+Z): − f i b (X,Y) , f i b ( s (X) , Z ) .
Consultas:
?− f i b ( 0 ,X ) .
?− f i b ( s ( 0 ) ,X ) .
?− f i b ( s ( s ( s ( 0 ) ) ) ,X+Y ) .
♦ Fibonacci numérico:
?− ¿ ?
♦ Learn Prolog Now : http://bit.ly/hY3gM
♦ Temas de “Programación lógica e I.A.”: http://bit.ly/YGHVbT
1.5
Aplicaciones de representación y uso de conocimiento
Un sistema experto es un sistema computacional que contiene el conocimiento de uno o más
humanos expertos sobre un tema específico. Estos sistemas permiten guardar más conocimiento
y extraerlo inteligentemente.
Un sistema experto está conformado por:
♦ Base de conocimientos: contiene conocimiento modelado extraído del diálogo con un
experto.
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
18
♦ Base de hechos (memoria de trabajo): contiene los hechos que se han descubierto durante
el análisis de un problema.
♦ Motor de inferencia: modela el proceso de razonamiento.
♦ Módulos de justificación: explica el razonamiento utilizado por el sistema para llegar a
una determinada conclusión.
♦ Interfaz de usuario: es la interacción entre el SE y el usuario, y se realiza mediante
lenguaje natural.
Figure 1.22: Arquitectura básica de un sistema experto
A continuación se explican con más detalle dos de los módulos más importantes en un sistema
experto.
1.5.1
Base de conocimientos
La base de conocimientos se expresa con reglas de lenguaje natural del tipo SI ... ENTONCES
...; por ejemplo:
♦ “SI está vivo ENTONCES es mortal”
♦ “SI edad=conocida ENTONCES año de nacimiento ← fecha actual - edad en años”
♦ “IF the identity of the germ is not known with certainty AND the germ is gram-positive
AND the morphology of the organism is "rod" AND the germ is aerobic THEN there is a
strong probability (0.8) that the germ is of type enterobacteriacae”(regla de Mycin)
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
19
Esta formulación tiene la ventaja de utilizar lenguaje cotidiano (poco común en ciencia de la
computación, en donde generalmente se usa algún tipo de codificación). Las reglas expresan el
conocimiento que será explotado por el sistema. Existen otras maneras de formular las reglas, que
no son en lenguaje común, cada regla puede adaptarse a un estilo diferente.
1.5.2
Motor de inferencia
El motor de inferencia es un programa de computadora diseñado para producir un razonamiento,
debe estar basado en lógica. Existe gran variedad de lógicas: proposicional, de predicados,
epistémica, modal, temporal, difusa, etc.
La lógica proposicional es la lógica básica de los humanos, se expresa por silogismos (http://bit.ly/IQVgA):
Todos l o s hombres son m o r t a l e s
Todos l o s mexicanos son hombres
=> Todos l o s mexicanos son m o r t a l e s
Si un sistema experto utiliza esta lógica se conoce como de orden cero (zeroth-order ). Con la
lógica, el sistema es capaz de generar información nueva a partir del conocimiento que contiene
en la base, las reglas y los datos a procesar.
El motor puede ejecutarse en dos formas:
1. En batch: en este, el sistema tiene todos los datos necesarios para procesar desde el inicio;
para el usuario se comporta como un programa convencional : recibe los datos y entrega los
resultados rápidamente.
2. En forma conversacional : este método se vuelve necesario cuando el desarrollaron no puede
obtener toda la información al inicio; el software debe “inventar” una forma de resolver ese
problema, por ejemplo, solicitar más datos al usuario, y con esto acercarse gradualmente al
objetivo, tan pronto como sea posible. El resultado da la impresión de ser un diálogo con
algún experto.
El interés por usar lógica es que este tipo de sistemas debe ser capaz de dar una explicación
clara de lo que está haciendo (el “¿Por qué?”) y que deduce (el “¿Cómo?”). Aún más, gracias a
la lógica los sistemas expertos más sofisticados existentes pueden detectar contradicciones en la
información que ingresa el usuario o en la base de conocimientos y explicarlas claramente.
1.5.3
Ejemplos en Prolog
Prolog es un excelente lenguaje para desarrollar aplicaciones en las que se tiene conocimiento
previo de algún tipo.
1.5.3.1
Árbol genealógico
% Hechos
hombre ( pedro ) .
hombre ( paco ) .
mujer ( l u z ) .
mujer ( maria ) .
p r o g e n i t o r ( pedro , paco ) .
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
p r o g e n i t o r ( pedro , maria ) .
p r o g e n i t o r ( l u z , paco ) .
p r o g e n i t o r ( l u z , maria ) .
% Reglas
madre (X,Y): − p r o g e n i t o r (X,Y) , mujer (X ) .
padre (X,Y): − p r o g e n i t o r (X,Y) , hombre (X ) .
Tarea:
1. Agregar reglas para las relaciones:
♦ Hija e hijo
♦ Abuela y abuelo
♦ Hermana y hermano
♦ Tía y tío
♦ Prima y primo
2. Añadir el conocimiento necesario para probar las relaciones anteriores.
1.5.3.2
House M.D.
% Hechos
t i e n e _ s i n t o m a ( manuel , f i e b r e ) .
tiene_sintoma ( a l i c i a , cansancio ) .
sintoma_de ( f i e b r e , g r i p e ) .
sintoma_de ( t o s , g r i p e ) .
sintoma_de ( c a n s a n c i o , anemia ) .
elimina ( vitaminas , cansancio ) .
elimina ( aspirinas , f i e b r e ) .
elimina ( jarabe , tos ) .
% Reglas
r e c e t a r _ a (X,Y): − enfermo_de (Y,A) , a l i v i a (X,A ) .
a l i v i a (X,Y): − e l i m i n a (X,A) , sintoma_de (A,Y ) .
enfermo_de (X,Y): − t i e n e _ s i n t o m a (X, Z ) , sintoma_de ( Z ,Y ) .
Programa:
1. Representar la red semántica de la figura:
20
CHAPTER 1. LENGUAJES DE PROGRAMACIÓN PARA RESOLVER PROBLEMAS
Figure 1.23: Red semántica
2. Representar el árbol genealógico de la figura:
Figure 1.24: Árbol Genealógico
Para ambos:
♦ Establecer el conocimiento base
♦ Definir las reglas necesarias para determinar características recursivamente
• Propiedades la red semántica
• Determinar si se tuvo un ancestro de ojo azul para el árbol genealógico
21