Download CP 12 mia

Asignatura: Introducción a la Inteligencia Artificial
Carrera: Ingeniería Informática
Tipo de Curso: C. R. D
Año: 2do
Semestre: 1ro
Actividad No.18
Clase Práctica No.12
Tema No. 3
Título:
Objetivos:Desarrollar habilidades para el trabajo con árboles, árboles binarios y diccionarios binarios.
Bibliografía
Bratko, Ivan: Prolog Programming for Artificial Intelligence, Addison Wesley, 1986.Cap. 3, Pag 64 -78.
Introducción
Recordar, mediante preguntas a los estudiantes, los conceptos, estructura de los árboles, árboles
binarios y diccionarios binarios, y los predicados estudiados en la conferencia.
Ejercicios
1. Determina si un árbol es vacío
vacio(aárbol(nil)):-!.
2. Determina si un elemento pertenece a un árbol
pert_aárbol(aárbol(A,X,Y),A):-!.
pert_aárbol(aárbol(A,X,Y),B):-pert_aárbol(X,B),!.
pert_aárbol(aárbol(A,X,Y),B):-pert_aárbol(Y,B),!.
3. Cuenta la cantidad de elementos que posee el árbol
cant_elem(nil,0):-!.
cant_elem(tree(A,X,Y),N):-cant_elem(X,N1),cant_elem(Y,N2),N isN1 + N2+1.
4. Calcula la profundidad del árbol
profundidad(nil,0):-!.
profundidad(tree(A,Y,X),N):-profundidad(X,B),profundidad(Y,C), mayor(B,C,M),N is M+1.
mayor(B,C,B):-B>=C,!.
mayor(_,C,C).
5. Determina si un árbol es completo
arbol_comp(nil):-!.
arbol_comp(tree(A,X,Y)):-porfundidad(X,N),profundidad(Y,N),arbol_comp(X),arbol_comp(Y),!.
6. Arma una lista con todos los elementos del árbol
elem_arbol(nil,[]):-!.
elem_arbol(tree(A,X,Y),L):-elem_arbol(X,I),elem_arbol(Y,D),concatenar([A|I], [D],L) .
7. Buscar el mayor elemento de un árbol binario. El menor..
Yo hice hasta aquí y le di las instrucciones del adicionar y eliminiar
8. Dada la representación de árbol binario estudiada en clase,
define los siguientes predicados sobre árboles binarios:
es_arbolB(A)
A es un árbol binario bien formado
es_arbolB_nat(A)
A es un árbol binario de naturales
raiz(R,A)
hoja(H,A)
miembro(X,A)
padre(X,Y,A)
hijo(X,Y,A)
descendiente(X,Y,A)
ascendiente(X,Y,A)
rama(Rs,A)
esta(X,A)
no_esta(X,A)
sustituye(X,Y,AX,AY)
R es la raíz de A
H es una hoja de A
X es elemento de A
X es padre de Y en A
X es hijo de Y en A
X es descendiente de Y en A
X es ascendiente de Y en A
la lista Rs es una rama de A
X está en A(sólo en modo test(+,+))
X no está en A(sólo en modo test (+,+))
AY es AX sustituyendo todas las Xpor Y
9. Modificar el programa de búsqueda en diccionario binario para el caso en que los nodos del
árbol sean letras. Verificar con un árbol de ejemplo. (Sugerencia: tener en cuenta el predicado
predefinido name(Atomic, List)).
10. Elaborar un programa que permita agregar un elemento X a un diccionario binario T para
obtener otro T1. (agregar( T, X, T1)).
11. Elaborar un programa que permita eliminar un elemento X a un diccionario binario T para
obtener otro T1. (eliminar( T, X, T1)).
Estudio independiente
Ejercicio 1. Define las siguientes relaciones sobre árboles binarios:
subarbol(A,B)
simetricos(A,B)
isomorfos_estruc(A,B)
isomorfos_ramas(A,B)
Aessubárbol de B
AyBsonsimétricos
AyBtienen la mismaestructura
AyBtienenlasmismasramas
Ejercicio 2. Define versiones recursivas de los siguientes predicados sobre árboles binarios:
num_nodos(A,N)
AtieneNnodos
Pes la profundidad de A
profundidad(A,P)
maximo(A,M)
Mes el máximo de A
suma(A,S)
Ses la suma de los nodos de A
frontera(A,Fs)
Fs es la frontera de A
Ejercicio 3. Define los siguientes predicados de recorrido sobre árboles binarios:
miembro_preorden(X,A)
generador de elementos de A en preorden
preorden(Rs,A)
Rs es una lista con el recorrido en preorden de A
miembro_inorden(X,A)
generador de elementos de A en inorden
inorden(Rs,A)
Rs es una lista con el recorrido en inorden de A
miembro_postorden(X,A) generador de elementos de A en postorden
postorden(Rs,A)
Rs es una lista con el recorrido en postorden de A
miembro_anchura(X,A)
generador de elementos de A en anchura
anchura(Rs,A)
Rs es una lista con el recorrido en anchura de A
Ejercicio 4.Define un predicado arbol_inorden(Rs,A) tal que, dada una lista Rs, generetodos los árboles
binarios A tales que su recorrido en inorden es Rs.
Ejercicio 5. Define un predicado construye_arbol(Ps,Is,A) que reconstruya un árbol binario A a partir de
sus recorridos en preordenPs e inordenIs.
Ejercicio 6. Define un predicado camino(X,A,Cs) que, dado un árbol binario A, se satisfaga si la lista Cs
contiene un camino desde la raíz de A hasta un nodo X. El camino debe almacenar las raíces de los
nodos que lo componen, así como los lados del árbol por los que se desciende.
Por ejemplo:
?arbol_
ejemplo(_A), camino(5,_A,Cs).
Cs = [ (4>der), (6>izq), 5] ;
No
Significa que hay un camino en el árbol A que parte de la raíz 4, desciende por la derecha visitando 6 y
desciende por la izquierda hasta llegar al nodo destino 5.
Ejercicio 7. Define un predicado camino_entre(X,Y,A,Cs) que, dado un árbol binario A, se satisfaga si la
lista Cs contiene un camino desde un nodo X hasta un nodo Y. El camino debe almacenar las raíces de
los nodos que lo componen, así como los lados del árbol por los que se desciende. Por ejemplo:
?arbol_
ejemplo(_A), camino_entre(6,5,_A,Cs).
Cs = [(6>izq), 5] ;
No
Significa que hay un camino en el árbol A que parte del nodo 6 y desciende por la izquierda hasta llegar
al nodo destino 5.
Ejercicio 8. Define un predicado nodos_prof_i(I,A,Is) que, dados un árbol binario A y unentero positivo I,
devuelva una lista Is con los nodos de A situados a profundidad I.
Ejercicio 9. Define un predicado por_profundidad(A,Iss) que, dado un árbol binario A, devuelva una lista
de listas Iss tal que la lista i-ésima contenga los nodos de A situados a profundidad i-ésima. Escribe dos
versiones: una que haga uso del predicado nodos_prof_i(I,A,Is) y otra que no.
Método de evaluación de la CP
•
•
Preguntas orales a lo largo de la CP
Participación en la resolución de los ejercicios en la pizarra