Clase de Repaso
Resolución ejercicios de parcial
Paradigma Lógico
y Objetos
Objetivo

Prolog:





SmallTalk:





Functores
Generate & Test
Reversibilidad
Declaratividad y Modularidad
Herencia, Polimorfismo
Concepto de Objeto, Referencia, Estado
Uso de colecciones
Bloques de código
Con qué contamos?

Ejercicios de la Práctica y Teórica
Dados dos conjuntos D1 y D2 vamos a representar una relación R binaria como una lista
de pares (a, b) con a  D1 y b  D2 (R  D1 × D2).
Ejemplos de relaciones:


R1 = {(1, b), (1, a), (1, c)} con D1 = [1] y D2 = [a, b, c]
R2 = {(1, a), (1, b), (3, a)} con D1 = [1, 2, 3, 4] y D2 = [a, b, c]
donde los conjuntos D1 y D2 serán representados como listas de enteros de prolog.
Se pide implementar los siguientes predicados:
a. Definir el predicado relacion(+D1,+D2,-R) que debe dar verdadero cuando R es una
relación binaria sobre los conjuntos D1 y D2.
b. Definir el predicado funcion(+D,+I,-F) que debe dar verdadero cuando F es una
función con conjunto de partida D y conjunto de llegada I (F : D  I).
c. Definir el predicado biyectiva(+D,+I,-F) que debe dar verdadero cuando F es una
función biyectiva (inyectiva y sobreyectiva) con conjunto de partida D y conjunto de
llegada I.
Tener en cuenta:
 Cuando el parámetro es pasado sin instanciar el predicado debe devolver, a medida que
sean solicitados, todas las relaciones y funciones válidas para los dominios dados.
 Pueden asumir que los parámetros R y F nunca se pasan instanciados.
Estrategía

Para relación
Generar el producto cartesiano D1xD2
 Luego ir obteniendo los subconjuntos


Para función

Quedarnos con las relaciones que son funciones
Solución

relacion(+D,+I,-R)
Genera el
producto
DxI
relacion(D,I,R):generarPares(D,I,L),
obtenerRelacion(L,R).
Genera los
subconjuntos
Parte “fácil”


Tenemos el producto y queremos todos los
subconjuntos
Usamos member como generador
obtenerRelacion(L,R):partes(L,CL),
member(R,CL).
Genera el
conjunto de
todos los
subconjuntos
Obtiene los
subconjuntos
Generación del producto


Idea: generar los pares combinado cada elemento del dominio
con cada elemento de la imagen
Genera las
tuplas de X con
generarPares(+D,+I,-L)
todos los
elementos de Y
generarPares([],_,[]).
generarPares([X|Xs],Y, L):- tuplear(X,Y,L1),
generarPares(Xs,Y,Ls), append(L1,Ls, L).

tuplear(+X,+I,-Ls)
tuplear(_,[],[]).
tuplear(X,[Y|Ys],[(X,Y)|Zs]):tuplear(X,Ys,Zs).
Genera el resto
de las tuplas
Función


Idea: generar Relaciones y filtrar las que son funciones
funcion(+D,+I,-F)
funcion(D,I,F):relacion(D,I,F), testFuncion(F).

testFuncion(+R)
testFuncion([]).
testFuncion([(X,_)|Xs]):not(member((X,_),Xs)),testFuncion(Xs).
Otra definicion

Asumiendo que el dominio debe estar cubierto
funcion2(D,I,F):relacion(D,I,F), testFuncion(F),
testDominio(D,F).
testDominio([],_).
testDominio([X|Xs],F):member((X,_),F),
testDominio(Xs,F).
Inyectiva


Idea: Generar funciones y quedarse con las inyectivas
inyectiva(+D,+I-,F)
inyectiva(D,I,F):-funcion(D,I,F),
testInyectiva(F).

testInyectiva(+F)
testInyectiva([]).
testInyectiva([(_,Y)|Xs]):not(member((_,Y),Xs)),testInyectiva(Xs).
Biyectiva

Quedarse con las inyectivas que también son
sobreyectivas
testSobreyectiva(_,[]).
testSobre(F,[X|Xs]):memberChk((_,X),F),
testSobreyectiva(F,Xs).
Otra biyectiva

Si es inversible
biyectiva2(D,I,F):funcion(D,I,F),
invertir(F,F2),
testFuncion(F2).
invertir([],[]).
invertir([(X,Y)|L],[(Y,X)|L2]):invertir(L,L2).
Vamos a representar a un árbol binario con colores en sus nodos a través de los
siguientes functores:
• hoja(X), que representa a un nodo hoja con valor X.
• bin(Sai, X, Sad), que representa a un nodo distinto de hoja con valor X. Los
subárboles izquierdo y derecho del nodo son Sai y Sad respectivamente.
Los valores que pueden tomar los nodos van a estar representados por los siguientes
functores: rojo, amarillo, verde, azul, negro y naranja.
Por ejemplo, el siguiente es un posible árbol de colores:
miArbol = bin(hoja(verde), rojo,
bin(hoja(negro),azul,hoja(naranja)))
Definir el predicado arbolColoreado(-Arbol), que debe dar verdadero cuando
Arbol es un árbol binario de colores en donde el color de cada nodo debe ser
distinto del color de su correspondiente nodo padre (en el caso que tenga).
Aclaraciones: El predicado genera infinitos árboles. Pueden suponer que tienen un
predicado color(-C) que les instancia un color en C.
En ningún caso se deben devolver soluciones repetidas. No utilizar cut (!) ni predicados
de ‘alto orden’ (como setof). La única excepción es el not, que está permitido.
Estrategía


Generar arboles de todos los colores
Tenemos que ir generando árboles por niveles
Altura 0,1,2,…
 Sino se nos puede desbalancear para un lado…



Para una altura dada tenemos que generar cada
subárboles izquierdos y derechos completos
pero tambíen incompletos (respetando la altura)
Una vez que tenemos un arbol, lo testeamos
Solución
arbolColoreado(Arbol) :arbolColor(Arbol),
esArbolAlt(Arbol).
Generador
Test
arbolColor(Arbol):desde(1,Altura),
Genera un arbol
arbolColorAltura(Altura,Arbol).
de altura Altura
arbolColorAltura(1, hoja(Color)) :- color(Color).
arbolColorAltura(Altura, bin(Color, SI, SD)) :Altura > 1, color(Color), A is Altura - 1,
entre(1,A,AI), entre(1,A,AD), A is max(AI,AD),
arbolColorAltura(AI,SI),
arbolColorAltura(AD,SD).
Cada subarbol debe tener todas
las alturas posibles
Pero el arbol debe ser de altura A
Test
esArbolAlt(hoja(_)).
esArbolAlt(bin(Color, SI, SD)) :esArbolAltColor(Color, SI),
esArbolAltColor(Color, SD).
Mira si cada
subarbol cumple
con la propiedad
La raiz no puede
esArbolAltColor(ColorProhibido, hoja(X)):tener el color del
ColorProhibido \= X.
padre
esArbolAltColor(ColorProhibido, bin(Color, SI,SD)):ColorProhibido \= Color,
esArbolAltColor(Color,SI),
esArbolAltColor(Color,SD).
a. Agregar a la clase Set el metodo:
 satisfiesAll: aSetOfSets
El parametro aSetofSets es un conjunto cuyos elementos son
conjuntos de bloques (instancia de BlockClosure) de un parámetro
que evaluan a Bool.
Este método debe devolver un objeto de la misma clase que el
receptor, tal que sus elementos sean los elementos del conjunto
receptor que satisfacen por lo menos un bloque de todos los
conjuntos perteneciente a aSetOfSets.
Por ejemplo:
s1 := Set new add:[:i| i<4]; add:[:i| i<10];
yourself.
s2 := Set new add:[:i| i even]; yourself.
ss := Set new add:s1; add:s2; yourself.
r := Set new addAll:#(6 12 2); yourself.
r satisfiesAll:ss
devuelve: Set(6 2)
Estrategía

Para cada elemento de la colección

Iteraramos por cada conjunto de bloques


Dado un conjunto vemos si al menos un bloque
satisface la condición para el elemento
Si en todos los conjuntos se dio esta condición ese
elemento debe quedar.
Solución
satisfiesAll: aSetOfSets
|res|
res := self select: [:e |
Por cada elemento…
|conjSat|
conjSat := aSetOfSets select: [:c |
|sat|
sat:= c select: [:t | t value:e].
sat notEmpty.
De cada conjunto
].
bloques me fijo si al
menos uno de los
conjSat size = aSetOfSets size.
bloques se satisface
].
Me quedo con el
con ese elemento
^ res
elemento si todos los
conjuntos cumplieron
con la condición
b. Agregar a la clase Dictionary el método:
 simplify: aBlock
Asumiendo que las claves del diccionario receptor son bloques de un parámetro que
evaluan a Bool, se debe devolver un nuevo diccionario (objeto de la misma clase
que el receptor) tal que cada entrada (Clave,Definición) satisface:
 Clave es un bloque de un parámetro que devuelve verdadero si y solo si el
paramátro satisface todas las claves originales de los elementos de Definición.
 Definición es un subconjunto maximal de las definiciones del diccionario
receptor tal que todos sus elementos retornan el mismo valor al ser evaluados
con aBlock.
Por ejemplo:
d:= Dictionary new at:([:i|i<4]) put:3; at:([:i|i>7])
put:8; at:([:i|i=10]) put:10; yourself.
d simplify:[:i|i even].
devuelve:
Dictionary([:i|i<4]->Set(3)[:i | i>7 & i=10]->Set(8 10))
Ayudas: Se puede asumir que no hay definiciones repetidas en el diccionario
receptor. La clase Dictionary posee el metodo keyAtValue: que retorna la
clave correspondiente a una definición.
Estrategia

Generar el conjunto de valores que quedan luego de
aplicarles a las definiciones el aBlock




En este caso son true y false ([:i|i even])
Para cada valor: agrupar las definiciones que evaluan a
ese valor (luego de aplicarles aBlock)
Por cada grupo armar bloques con la conjunción de las
claves (bloques boleanos) que corresponden a cada
definición del grupo
Poner cada bloque con su grupo en el diccionario
Solución
simplify: aBlock
| valores res|
res := self class new.
Obtengo el conjunto de
todas las definiciones
valores := self keys collect: [:k | self at:k].
Armo un conjunto aplicandole aBlock a cada
definición. Con esto se obtienen todos los
valores posibles
(valores collect:[:v | (aBlock value:v)])
Armo el grupo de definiciones
do: [:v |
que aplicadas comparten un
valor
|grupo bloque|
grupo := valores select: [:g | (aBlock value:g) = v].
bloque:= grupo inject: [:p | true]
Armo un bloque con la
into: [:bb :v | [:p | bb value:p
conjunción de los bloques clave
que se corresponde a cada
& (self keyAtValue:v) value:p] ].
valor en el grupo
res at:bloque put:grupo.
].
^res
Descargar

Document