Recuperatorio Segundo Parcial 1er Cuat 2006 (Paradigmas)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1: Prolog[editar]

Escribir los siguientes predicados, respetando para cada parametro la instanciacion pedida. En ningun caso se deben devolver soluciones repetidas. No utilizar cut (!) ni predicados de alto orden (como setof). La unica excepcion es el not, que esta permitido.

Item a[editar]

Representaremos a un triangulo de altura n, como una lista de listas de naturales [L1,...,Ln], donde cada lista Li tiene longitud i. Cada lista Li representa un nivel del triangulo. Por ejemplo, la siguiente lista de listas representa un triangulo de altura 3.

L = [[1],[2,2],[3,3,3]];

Diremos que un triangulo es perfecto si cumple con las siguientes restricciones:

  • Cada elemento del triangulo es un numero mayor a 0.
  • Para cada nivel i (salvo el ultimo nivel), cada elemento a(i;j) debe corresponder a la suma de los elementos a(i+1;j) y a(i+1;j+1) del nivel i + 1.

Se pide definir el predicado trianguloPerfecto(+Numero, -Triangulo) que dado un Numero mayor a 0, debe ser verdadero cuando Triangulo representa un triangulo perfecto y el numero maximo de Triangulo es menor o igual a Numero.

?- trianguloPerfecto(4, T).
T = [ [1] ] ;
T = [ [2] ] ;
T = [ [3] ] ;
T = [ [4] ] ;
T = [[2], [1, 1]] ;
T = [[3], [1, 2]] ;
T = [[4], [1, 3]] ;
T = [[3], [2, 1]] ;
T = [[4], [2, 2]] ;
T = [[4], [3, 1]] ;
T = [[4], [2, 2], [1, 1, 1]] ;
No

Respuesta:

%trianguloPerfecto(+Numero, -Triangulo)
trianguloPerfecto(N,T) :- generarTriangulo(N,T), esTrianguloPerfecto(T).

%generarTriangulo(+MaxNum, -Triangulo)
generarTriangulo(N, T) :- between(1,N,F), generarFilas(1,F,N,T).

%generarFilas(+Fila, +CantFilas, +MaxNum, -Triangulo)
generarFilas(F,N,M,[Fila|Base]) :- F < N, F1 is F+1, generarFila(F,M,Fila), generarFilas(F1,N,M,Base).
generarFilas(N,N,M,[Fila]) :- generarFila(N,M,Fila).

%generarFila(+CantElems, +MaxElem, -Fila)
generarFila(0,_,[]).
generarFila(N,M,[X|Xs]) :- N > 0, N1 is N-1, between(1,M,X), generarFila(N1,M,Xs).

%esTrianguloPerfecto(+Triangulo)
esTrianguloPerfecto([_]).
esTrianguloPerfecto([F1|[F2|Fs]]) :- checkFilas(F1,F2), esTrianguloPerfecto([F2|Fs]).

%checkFilas(+FilaArriba, +FilaAbajo)
checkFilas([],_).
checkFilas([X|Xs],[Y1|[Y2|Ys]]) :- plus(Y1,Y2,X), checkFilas(Xs,[Y2|Ys]).

Item b[editar]

Se puede representar a un triangulo perfecto como un arbol binario donde:

  • Los nodos correspondientes al ultimo nivel del triangulo son hojas.
  • Para el resto de los niveles, cada nodo n(i;j) del nivel i tiene como hijos a los nodos n(i+1;j) y n(i+1;j+1) del nivel i + 1 del triangulo. Es decir, cada nodo de estos niveles es la suma de sus dos nodos hijos.

Para representar un arbol binario utilizaremos los siguientes funtores:

  • nil, si es vacio.
  • bin(sai, v, sad), donde v es el valor del nodo, sai es el subarbol izquierdo y sad es el subarbol derecho.

Por ejemplo, el triangulo T = [[4], [2, 2], [1, 1, 1]] estara representado por el arbol binario:

A = bin(4,
          bin(2,
                bin(1, nil, nil),
                bin(1, nil, nil)),
          bin(2,
                bin(1, nil, nil),
                bin(1, nil, nil)))

Definir el predicado arbolPerfectoPrimo(+Numero, -Arbol) que dado un Numero mayor a 0, debe ser verdadero cuando Arbol es un arbol binario que representa un triangulo perfecto, el numero maximo del triangulo perfecto que representa es menor o igual a Numero y ademas, la suma de cada nivel es un numero primo.

?- arbolPerfectoPrimo(4, A).
A = bin(2, nil, nil) ;
A = bin(3, nil, nil) ;
A = bin(2, bin(1, nil, nil), bin(1, nil, nil)) ;
A = bin(3, bin(1, nil, nil), bin(2, nil, nil)) ;
A = bin(3, bin(2, nil, nil), bin(1, nil, nil)) ;
No

Respuesta:

%arbolPerfectoPrimo(+Numero, -Arbol)
arbolPerfectoPrimo(N,A) :- trianguloPerfecto(N,T), esTrianguloPrimo(T), arbolDeTriangulo(T,A).

%arbolDeTriangulo(+Triangulo, -Arbol)
arbolDeTriangulo(T, A) :- arbolDeBaseTriangulo(T,1,A).

%arbolDeBaseTriangulo(+Triangulo, +IndiceEnFila, -Arbol)
arbolDeBaseTriangulo([],_,nil).
arbolDeBaseTriangulo([F|Fs], I, bin(R,Izq,Der)) :- nth1(I,F,R), I1 is I+1, arbolDeBaseTriangulo(Fs,I,Izq), arbolDeBaseTriangulo(Fs,I1,Der).

%esTrianguloPrimo(+Triangulo)
esTrianguloPrimo([]).
esTrianguloPrimo([F|Fs]) :- sumlist(F,S), esPrimo(S), esTrianguloPrimo(Fs).

%esPrimo(+Numero)
esPrimo(N) :- N > 0, divisores(N,1,Divs), length(Divs,2).

%divisores(+Numero, +Min, -Lista)
divisores(N,N,[N]).
divisores(N,D,[D|Xs]) :- D < N, 0 =:= (N mod D), D1 is D+1, divisores(N,D1,Xs).
divisores(N,D,Xs) :- D < N, 0 =\= (N mod D), D1 is D+1, divisores(N,D1,Xs).


Ejercicio 2: Resolucion[editar]

Dadas las siguientes formulas de primer orden:

Demostrar utilizando resolucion general que la curiosidad mato al gato Tuna, es decir, Mato(Curiosidad, Tuna).

Respuesta

Formula 1

Formula 2

Formula 3

Formula 4

Formula 5

Formula 6

Resolvemos usando resolución general

  1. Goal:
  2. 7 con 4:
  3. 8 con 3:
  4. 5 con 6:
  5. 10 con 9:
  6. 11 con 2:
  7. 12 con 1B:
  8. 13 con 1A:

Ejercicio 3: Colecciones[editar]

Agregar en Smalltalk a la clase Dictionary el metodo:

filter:aBlock withUpdate:aBlockCollection

Este metodo debe transformar el diccionario receptor cambiando las definiciones solo de las claves que satisfacen el bloque aBlock (instancia de la clase BlockClosure de un parametro que evalua a Bool).

La transformacion de una definicion se realiza reemplazando la definicion anterior por la aplicacion sucesiva de cada uno de los bloques que pertenecen a la coleccion aBlockCollection (coleccion de instancias de la clase BlockClosure de un parametro).

Ejemplo:

d := (Dictionary new) at:1 put:10; at:2 put:20; at:3 put:30; yourself.
sb:= (Set new) add:[:p | p+1]; add:[:p | p+2]; yourself.
d filter:[:b| b odd] withUpdate:sb devuelve Dictionary (1->13 2->20 3->33)

Ayudas: La clase Dictionary posee los siguientes metodos:

  • keys que retorna el conjunto de claves del diccionario.
  • at:aKey que retorna la definicion que tiene aKey.
  • at:aKey put:aDef que asocia la definicion aDef a la clave aKey.

Respuesta:

filter:aBlock withUpdate:aBlockCollection

	| keysToUpdate |
	keysToUpdate := self keys select: aBlock.
	keysToUpdate do:
		[:eachKey | | valToSet valOrig |
			valOrig := self at: eachKey.
			valToSet := aBlockCollection inject: valOrig into:  [:val :eachBlock | eachBlock value: val].
			self at: eachKey put: valToSet.
		].
	^self.


Ejercicio 4: Herencia[editar]