PDF de programación - Programación lógica con árboles

Programación lógica con árboles

Ingeniería Informática

Ingeniería Técnica en Informática

Departamento de Lenguajes y

Ciencias de la Computación

Universidad de Málaga

Contenido

1. Programación con árboles
2. Otras estructuras arbóreas

Programación lógica con árboles

2

Introducción

Introducción

Objetivo: representar en Prolog estructuras de datos y
procesarlas

Para cada estructura de datos, daremos:

definición formal (conjunto inductivo)
representación sintáctica (gramática formal)
definición de dominio
relaciones

Aplicaremos las técnicas de programación básicas: recursión,
recursión de cola, generar/comprobar

Programación lógica con árboles

4

Programación con árboles

Definición de árbol binario

Sea D un dominio o tipo base

Definición: el conjunto de árboles binarios B de D se define
1. nil ∈ B (árbol vacío)
[base]
[recursivo]
2. si I, D ∈ B ∧ R ∈ D, entonces I::R::D ∈ B

:: ::

es un constructor ternario: B × D × B → B
hijo izquierdo :: raíz :: hijo derecho

Ejemplo:

(nil :: a :: nil ) :: b :: (nil :: c :: nil)

Programación lógica con árboles

b

a

c

6

Representación Prolog de árboles binarios

Necesitamos términos recursivos para representar árboles

Seguimos la definición inductiva de B:
1. nil ∈ B (árbol vacío)
2. si I, D ∈ B ∧ R ∈ D, entonces I::R::D ∈ B

[base]
[recursivo]

Caso base
Caso recursivo estructura funtor nodoB/3 nodoB(I,R,D)

constante vacioB

Un árbol binario bien formado es un término de la gramática:

7

AB ::= vacioB

| nodoB(AB,T,AB)

donde T es un término Prolog
Programación lógica con árboles

Ejemplo de árbol binario bien construido

El árbol binario:

4

2

6

1

3

5

7

se representa por el término Prolog:

nodoB(nodoB(nodoB(vacioB, 1, vacioB),
nodoB(vacioB, 3, vacioB)),

2,

nodoB(nodoB(vacioB, 5, vacioB),
6,
nodoB(vacioB, 7, vacioB)))

Programación lógica con árboles

4,

8

El predicado arbolB_ej/1
% arbolB_ej(?A)
arbolB_ej(
nodoB(nodoB(nodoB(vacioB, 1, vacioB),

nodoB(vacioB, 3, vacioB)),

1

2,

nodoB(nodoB(vacioB, 5, vacioB),
6,
nodoB(vacioB, 7, vacioB)))).

Cada hecho define un árbol binario bien construido:

?- arbolB_ej(A), miembro(3,A).

Programación lógica con árboles

4,

9

Definición de dominio

Seguimos la definición inductiva de B:

1. nil ∈ B (árbol vacío)
2. si I, D ∈ B ∧ R ∈ D, entonces I::R::D ∈ B

[base]
[recursivo]

% es_arbolB(+A)
es_arbolB(vacioB).
es_arbolB(nodoB(I,R,D)) :-
es_arbolB(I),
es_arbolB(D).

% base
% recursivo

Programación lógica con árboles

10

% test

% generador anómalo

Usos de es_arbolB/1
?- arbolB_ej(A), es_arbolB(A).
Yes
?- es_arbolB(A).
A = vacioB ;
A = nodoB(vacioB, _G309, vacioB) ;
A = nodoB(vacioB, _G309,
A = nodoB(vacioB, _G309, nodoB(vacioB, _G313,
...

nodoB(vacioB, _G313, vacioB)) ;
nodoB(vacioB, _G317, vacioB))) ;

Programación lógica con árboles

11

Tabla de comportamiento de es_arbolB/1

es_arbolB(A)
Uso
(+)
(-)

Comportamiento
test
generador anómalo

Significado
A ∈ B

Ejercicio: ¿Por qué no funciona el uso (-)? ¿Cómo
solucionarías?

lo

Programación lógica con árboles

12

El predicado miembro/2
miembro(?X,+A) – X pertenece al árbol binario A
Es similar a miembro/2 para listas:
miembro(X,nodoB(_,X,_)).
miembro(X,nodoB(I,_,_)) :-
miembro(X,nodoB(_,_,D)) :-

miembro(X,I).
miembro(X,D).

% base
% recursivo (I)
% recursivo (D)

caso base acceso directo a la raíz
casos base y recursivos no son excluyentes

Programación lógica con árboles

13

% test

Usos de miembro/2
?- arbolB_ej(A), miembro(5,A).
Yes
9 ?- arbolB_ej(A), miembro(X,A).
X = 4 ;
X = 2 ;
X = 1 ;
X = 3 ;
X = 6 ;
X = 5 ;
X = 7 ;
No
Ejercicio: ¿En qué orden se generan los elementos del árbol?
Programación lógica con árboles

% gen acotado

14

Tabla de comportamiento de miembro/2

miembro(X,A)
Uso
(+,+) test
(-,+) generador acotado

Comportamiento

Significado
comprueba que X ∈ A
genera elementos de A
en preorden

Ejercicio: ¿Cómo se comportan los usos (+,-) y (-,-)? ¿De qué
depende el orden en que se generen los elementos? Escribir
definiciones que generen los elementos en inorden y postorden.

¿Cómo almacenar el recorrido en predorden en una lista?

Programación lógica con árboles

15

El predicado preorden/2
preorden(+A,?Rs) – Rs es el recorrido en preorden de A
Aplicamos recursión sobre el árbol A :
preorden(vacioB,[]).
preorden(nodoB(I,R,D),RID) :-

% base
% recursivo

preorden(I,PreI),
preorden(D,PreD),
concatena([R|PreI],PreD,RID).

Ejercicio: definir los recorridos en inorden y postorden

Programación lógica con árboles

16

Usos de preorden/2
% test
?- arbolB_ej(A), preorden(A,[4,2,1,3,6,5,7]).
Yes
% generador único
?- arbolB_ej(A), preorden(A,Rs).
Rs = [4,2,1,3,6,5,7] ;
No
% generador anómalo
?- preorden(A,[4,2,1,3,6,5,7]).
A = arbolB_ej ;
% y se cuelga...
Programación lógica con árboles

17

Tabla de comportamiento de miembro/2

Comportamiento

preorden(+A,?Rs)
Uso
(+,+) test
(+,-) generador único

Significado
comprueba que Rs es el recorrido
en preorden de A
genera en Rs el recorrido en
preorden de A

Ejercicio: Construir las tablas de inorden/2 y postorden/2

¿Es posible generar el árbol a partir del recorrido?

Programación lógica con árboles

18

Generación de árboles binarios
arbol_preorden(+Rs,?A) – Rs es el recorrido preorden de A

Hay que dirigir la recursión por la lista (el recorrido):
arbol_preorden([],vacioB).
arbol_preorden([R|Rec],nodoB(I,R,D)) :- % recursivo

% base

concatena(RecI,RecD,Rec), % (-,-,+)
arbol_preorden(RecI,I),
arbol_preorden(RecD,D).

Ejercicio: definir
arbol_postorden/2

los

predicados arbol_inorden/2

y

Programación lógica con árboles

19

El predicado suma/2
suma(+A,?N) – los nodos del árbol binario A suman N
Aplicamos recursión al árbol binario A:
suma(vacioB,0).
suma(nodoB(I,R,D),N) :-

% base
% recursivo

suma(I,SI),
suma(D,SD),
N is SI+R+SD.

Programación lógica con árboles

20

El predicado sustituye/3
sustituye(+X,+AX,+Y,?AY) –

el árbol AY es AX, con todas las X reemplazadas por Y

Aplicamos recursión al árbol AX:
sustituye(_,_,vacioB,vacioB).
sustituye(X,Y,nodoB(Ix,R,Dx),nodoB(Iy,R,Dy)) :-

sustituye(X,Y,nodoB(Ix,R,Dx),nodoB(Iy,Y,Dy)) :-

X \== R,
sustituye(X,Y,Ix,Iy),
sustituye(X,Y,Dx,Dy).
X == R,
sustituye(X,Y,Ix,Iy),
sustituye(X,Y,Dx,Dy).

Programación lógica con árboles

21

Ejercicios

1. Define los siguientes predicados sobre árboles binarios:
iguales(+A,+B)
simetricos(+A,+B)
frontera(+A,?F)
2. Los árboles binarios de búsqueda se pueden representar por
términos de la forma:

ArbolBB ::= vacioBB

| nodoBB(ArbolBB,T,ArbolBB)

donde T es un término Prolog.
Define
inserta(+X,+A,?AX) y borra(+X,+AX,?A). Utiliza
predicados extralógicos de comparación de términos

los predicados esta(+X,+A), no_esta(+X,+A),
los

Programación lógica con árboles

22

Otras estructuras arbóreas

Fórmulas proposicionales sin variables

Definición: el conjunto F se define
1. >, ⊥ ∈ F
2. si A, B ∈ F entonces

[base]
[recursivo]

A ∧ B ∈ F
A ∨ B ∈ F
¬ A ∈ F
Términos Prolog:

F := cierto
| falso
| y(F,F)
| o(F,F)
| no(F)

Programación lógica con árboles

24

Definición de dominio
es_fbf(P) – se satisface si P es una fórmula proposicional sin
variables

es_fbf(cierto).
es_fbf(falso).
es_fbf(o(P,Q)) :-
es_fbf(P),
es_fbf(Q).
es_fbf(y(P,Q)):-
es_fbf(P),
es_fbf(Q).
es_fbf(no(P)) :-
es_fbf(P).

Programación lógica con árboles

25

Derivación simbólica (I)
derivada(+Fx,+X,?DF)– DF es la derivada de Fx respecto de X

derivada(X,X,1).
derivada(C,X,0) :-

atomic(C), % C es constante y
C \= X. % no coincide con el diferencial

derivada(-U,X,-DU) :-

derivada(U,X,DU).

Programación lógica con árboles

26

Derivación simbólica (II)

derivada(U+V,X,DU+DV) :-
derivada(U,X,DU),
derivada(V,X,DV).
derivada(U-V,X,DU-DV) :-
derivada(U,X,DU),
derivada(V,X,DV).

Programación lógica con árboles

27

Derivación simbólica (III)

derivada(U*V,X,U*DV+DU*V) :-

derivada(U,X,DU),
derivada(V,X,DV).

derivada(U/V,X,(DU*V-U*DV)/V*V) :-

U \== 1,
derivada(U,X,DU),
derivada(V,X,DV).

Programación lógica con árboles

28

Derivación simbólica (y IV)

derivada(1/V,X,-DV/(V*V)) :-

derivada(V,X,DV).

derivada(sin(X),X,cos(X)).
derivada(cos(X),X,-sin(X)).
derivada(X^N,X,N*X^NN) :-

N>0,
NN is N-1.

Programación lógica con árboles

29

Ejemplos

Prolog deriva bastante bien:

pero no sabe nada de conmutatividad:

?- derivada(x^3+x,x,U).
U = 3*x^2+1 ;
No
?- derivada(x^3+x,x,3*x^2+1).
Yes
?- derivada(x^3+x,x,1+3*x^2).
No
ni simplifica las derivadas:
?- derivada(3*x,x,U).
U = 3*1+0*x ;
No

Programación lógica con árboles

30