%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % PRACTICA 3 DE RA (99-00) % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Bratko p.217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Un \'arbol binario es vac\'io o consta de tres partes: % * Una raiz % * Un sub\'arbol izquierdo (que debe ser un \'arbol binario) % * Un sub\'arbol derecho (que debe ser un \'arbol binario) % % Consideraremos la siguiente representaci\'on % * nil representa el \'arbol vac\'io % * Si el \'arbol no es vac\'io, entonces tendr\'a la forma t(I,R,D) donde % R es la raiz, I el sub\'arbol izquierdo y D el sub\'arbol derecho. % % EJEMPLO: El \'arbol % a % / \ % b c % / % d % % Lo representamos como t(t(nil,b,nil),a,t(t(nil,d,nil),c,nil)) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 1: Definir el predicado % arbolbinario(A) % que se verifique ni A es un \'arbol binario. Por ejemplo, % ?- arbolbinario(nil). % Yes % ?- arbolbinario(t(t(nil,b,nil),a,t(t(nil,d,nil),c,nil))). % Yes % ?- arbolbinario(t(t(nil,b,nil),a,t(t(nil,d,e),c,nil))). % No %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 2: Definir el predicado % en(Nodo,Arbol) % que se verifique si Nodo es un nodo del \'arbol binario Arbol. Por % ejemplo % ?- en(Nodo,t(t(nil,b,nil),a,t(t(nil,d,nil),c,nil))). % Nodo = a ; % Nodo = b ; % Nodo = c ; % Nodo = d ; % No % ?- en(b,t(t(nil,b,nil),a,t(t(nil,d,nil),c,nil))). % Yes % ?- en(f,t(t(nil,b,nil),a,t(t(nil,d,nil),c,nil))). % No %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 3: Definir el predicado % profundidad(Arbol,Prof) % que se verifique si Prof es la profundidad nodo del \'arbol binario % Arbol. Consideraremos que la profundidad del \'arbol vacio es 0 y la % del \'arbol con un \'unico nodo es 1. Por ejemplo, % ?- prof(nil,Prof). % Prof = 0 ; % No % ?- prof(t(nil,a,nil),Prof). % Prof = 1 ; % No % ?- prof(t(t(nil,b,nil),a,t(t(nil,d,nil),c,nil)),Prof). % Prof = 3 ; % No %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 4: Definir el predicado % alinea(Arbol,Lista) % que se verifique si Lista es la lista de los nodos del Arbol. Por % ejemplo, % ?- alinea(nil,L). % L = [] ; % No % ?- alinea(t(nil,a,nil),L). % L = [a] ; % No % ?- alinea(t(t(nil,b,nil),a,t(t(nil,d,nil),c,nil)),L). % L = [b, a, d, c] ; % No %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Se dice que un \'arbol binario es un diccionario binario para el orden % lexicogr\'afico @< si es vac\'io o % * Todos los elementos de I son menores que R % * Todos los elementos de D son mayores que R % * I y D son diccionarios binarios %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 5: Definir el predicado % db(A) % que se verifique si A es un diccionario binario. Ejemplos de uso: % ?- db(nil). % Yes % ?- db(t(nil,a,nil)). % Yes % ?- db(t(t(nil,a,nil),b,nil)). % Yes % ?- db(t(t(nil,a,t(nil,b,nil)), % c, % t(t(nil,d,nil),e,t(nil,f,t(nil,g,nil))))). % Yes % ?- db(t(t(nil,a,nil),f,t(nil,d,nil))). % No %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 6: Definir el predicado % en_db(Nodo,Arbol) % que se verifique si Nodo es un nodo de Arbol (Nodo y \'arbol deben % estar instanciados). Por ejemplo, % ?- en_db(a,t(t(nil,a,t(nil,b,nil)), % c, % t(t(nil,d,nil),e,t(nil,f,t(nil,g,nil))))). % Yes % ?- en_db(z,t(t(nil,a,t(nil,b,nil)), % c, % t(t(nil,d,nil),e,t(nil,f,t(nil,g,nil))))). % No %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 7: Definir el predicado % camino(N,Arbol,Camino) % que se verifique si Camino es la lista de los nodos del diccionario % binario Arbol desde la raiz hasta el nodo N. Por ejemplo, % ?- camino(f,t(t(nil,a,t(nil,b,nil)), % c, % t(t(nil,d,nil),e,t(nil,f,t(nil,g,nil)))), % L). % L = [c, e, f] ; % No % ?- camino(z,t(t(nil,a,t(nil,b,nil)), % c, % t(t(nil,d,nil),e,t(nil,f,t(nil,g,nil)))), % L). % No %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 8: Definir el predicado % dibuja(Arbol) % que dibuje el \'arbol. Por ejemplo, % ?- dibuja(t(t(nil,b,t(nil,c,nil)), % e, % t(t(nil,g,nil),h,t(nil,m,t(nil,x,nil))))). % x % m % h % g % e % c % b % % Yes % ?- dibuja(t(t(nil,b,nil),e,t(t(nil,g,nil),h,t(nil,m,t(nil,x,nil))))). % x % m % h % g % e % b % % Yes % ?- dibuja(t(t(nil,a,nil),b,t(nil,c,nil))). % c % b % a % Yes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 9: Definir el predicado % pon_hoja(Arbol,N,Nuevo_arbol) % que se verifique si Nuevo_arbol es el diccionario binario Arbol donde % hemos a\~nadido N como hoja. Por ejemplo, % ?- dibuja(t(t(nil,b,t(nil,c,nil)),e,t(nil,h,t(nil,m,t(nil,x,nil))))). % x % m % h % e % c % b % % Yes % % ?- pon_hoja(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil)))),a,_A), % dibuja(_A). % x % m % h % e % c % b % a % % Yes % ?- pon_hoja(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil)))),i,_A), % dibuja(_A). % x % m % i % h % e % c % b % % Yes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 10: Definir el predicado % quita_hoja(Arbol,N,Nuevo_arbol) % que se verifique si Nuevo_arbol es Arbol donde hemos quitado la % hoja N. Por ejemplo, % ?- dibuja(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil))))). % x % m % h % e % c % b % Yes % ?- quita_hoja(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil)))), % c, % _A), % dibuja(_A). % x % m % h % e % b % Yes % ?- quita_hoja(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil)))), % x, % _A), % dibuja(_A). % m % h % e % c % b % Yes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 11: Definir el predicado % quita_nodo(Arbol,N,Nuevo_arbol) % que se verifique si Nuevo_arbol es Arbol donde hemos quitado el % nodo N. Por ejemplo, % ?- dibuja(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil))))). % x % m % h % e % c % b % Yes % ?- quita_nodo(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil)))), % b, % _A), % dibuja(_A). % % x % m % h % e % c % Yes % ?- quita_nodo(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil)))), % e, % _A), % dibuja(_A). % x % m % h % c % b % Yes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 12: Definir el predicado % pon_raiz(Arbol,N,Nuevo_arbol) % que se verifique si Nuevo_arbol es Arbol donde hemos a\~nadido el nodo N como % raiz. Por ejemplo, % ?- dibuja(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil))))). % x % m % h % e % c % b % Yes % ?- pon_raiz(t(t(nil,b,t(nil,c,nil)), % e, % t(nil,h,t(nil,m,t(nil,x,nil)))), % f, % _A), % dibuja(_A). % x % m % h % f % e % c % b % % Yes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 13: Definir el predicado % pon_nodo(Arbol,N,Nuevo_arbol) % que se verifique si Nuevo_arbol es Arbol donde hemos a\~nadido el % nodo N a cualquier nivel. Por ejemplo, % ?- dibuja(t(t(nil,a,nil),d,t(nil,h,nil))). % h % d % a % % Yes % ?- pon_nodo(t(t(nil,a,nil),d,t(nil,h,nil)),b,A). % % A = t(t(nil, a, nil), b, t(nil, d, t(nil, h, nil))) ; % A = t(t(t(nil, a, nil), b, nil), d, t(nil, h, nil)) ; % A = t(t(nil, a, t(nil, b, nil)), d, t(nil, h, nil)) ; % No % % (1) h (2) h (3) h % d d d % b b b % a a a % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ejercicio 14: Llamaremos diccionario binario numerico completo de nivel % N (N>=0) al \'arbol diccionario binario enraizado en 2^N donde los nodos % son los n\'umeros 1,2,...,2^(N+1)-1. Por ejemplo: % De nivel 1: 2 De nivel 2: 4 % 1 3 2 6 % 1 3 5 7 % Definir la relacion dbnc(N,Diccionario) que reciba como dato de % entrada el nivel N y devuelva el Diccionario correspondiente con la % notaci\'on anterior. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Un dbnc de nivel N tiene 2^(N+1)-1 elementos, luego un dbnc de nivel % 12 tiene 8191 elementos (del 1 al 8191). Vamos a archivar esos n\'umeros % como lista y como diccionario y vamos a comparar el numero de % inferencias necesarias para averiguar si el n\'umero 8191 est\'a o no en % la base de datos. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%