Segundo Parcial 1er Cuat 2008 (Paradigmas)

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

Ejercicio 1 - Programación Lógica (35 puntos)[editar]

Implementar los siguientes predicados respetando la instanciación pedida. No utilizar cut (!) ni predicados de alto orden (como setof). La única excepción es el not, que está permitido.

En este ejercicio trabajaremos con grafos no orientados. Un grafo no orientado es un conjunto de nodos y un conjunto de ejes sin una dirección específica. Cada eje está representado por un par de nodos y, como se puede viajar en cualquiera de los dos sentidos, el eje (a, b) y el eje (b, a) son el mismo.

No sabemos cuál es la representación interna de un grafo, pero contamos con un predicado esNodo(+G,-X) que dado un grafo G dice si X es nodo de G. También tenemos otro predicado esEje(+G,-X,-Y) que dice si en G hay un eje de X a Y. Notar que podemos usar esNodo para enumerar los nodos del grafo y esEje para enumerar los ejes. Instanciando apropiadamente, también podemos usar esEje para obtener todos los ejes que tienen a un nodo particular. Cuando esEje lista todos los ejes, cada eje lo lista una sola vez en una orientación arbitraria de las dos posibles, pero si se pregunta por cualquiera de las dos, responderá que sí. Suponer que dos nodos son el mismo sii unifican.

Ayuda: para algunos ítems conviene pensar primero en cómo programar el predicado opuesto al que se pide.

a) (12 puntos) Implementar el predicado esCaminoSimple(+G,+D,+H,-L) que dice si L es un camino simple en el grafo G que empieza en D y termina en H. Un camino simple lo representaremos por una lista de nodos distintos, tal que para cada par de nodos consecutivos en L existe un eje en G que los conecta. Notar que el primer elemento de L debe ser D y el último H. Cuando L está sin instanciar, el predicado debe ir devolviendo todos los caminos simples desde D a H sin repetidos (es decir, hay que tener cuidado con los ciclos y evitar que el predicado se cuelgue).

b) (12 puntos) Un camino L en un grafo G es Hamiltoniano sii L es un camino simple que contiene a todos los nodos G. Implementar el predicado esCaminoHamiltoniano(+G,-L) que dice si L es un camino Hamiltoniano en G. Recordar que no se pueden usar predicados de alto orden, salvo el not, y en especial no se puede utilizar setof.

c) (5 puntos) Implementar el predicado esConexo(+G) que dado un grafo dice si éste es conexo. Un grafo G es conexo sii no existe un par de nodos en G tal que no hay un camino simple que los una. Notar que con esta definici´on un grafo de un nodo (y sin ejes) es conexo.

d) (6 puntos) Implementar el predicado esEstrella(+G) que dado un grafo dice si es un grafo estrella. Un grafo es estrella sii es conexo y hay un nodo común a todos sus ejes.

Respuesta

c)

noEsConexo(G) :- esNodo(G,A), esNodo(G,B), not(esCaminoSimple(G,A,B,_)).

d)

esEstrella(G) :- esConexo(G), esNodo(G,M), todosCon(G,M).
todosCon(G,M) :- not(hayUnoQueNoIncide(G,M)).
hayUnoQueNoIncide(G,M) :- esEje(G,A,B), A \= M, B\=M.


Ejercicio 2 - Resolución Lógica (15 puntos)[editar]

Sean las siguientes cláusulas (en CNF), en donde suma, y par son predicados, suc es una función y cero una constante:

1. {¬suma(x, y, z), suma(x, suc(y), suc(z))}

2. {suma(x, cero, x)}

3. {¬suma(x, x, y), par(y)}

Demostrar utilizando resolución que suponiendo (1), (2), (3) se puede demostrar par(suc(suc(cero))). Si es posible, aplicar resolución SLD, y sino utilizar resolución general. Mostrar en cada aplicación de la regla de resolución la sustitución utilizada.

Respuesta

1. {¬suma(x, y, z), suma(x, suc(y), suc(z))}

2. {suma(x, cero, x)}

3. {¬suma(x, x, y), par(y)}

y el goal negado: 4. {¬par(s(s(0)))}

Se puede usar resolución SLD ya que son todas cláusulas de Horn.

4 con 3 5. {¬suma(w, w, s(s(0)))}

5 con 1 6. {¬suma(s(w'), w', s(0)) }

6 con 2: {cuadradito}

Ejercicio 3 - Smalltalk - Herencia (5 puntos)[editar]

Supongamos que A, B y C son clases tales que A es padre de B, y B de C. Cada una de ellas tiene los siguientes mensajes:

class A
name 
 ˆ"A" 
do
 ˆTranscript show (self name)

class B
name
 ^"B"
ask
 ^super name

class C
 name
  ^self ask

Dar la secuencia de llamados que se produce cuando se ejecuta (C new) do, indicando en cada caso el método invocado y la clase a la que pertenece.

Respuesta

Como la clase C no implementa el método do lo busca en su superclase. Como la clase B tampoco lo implementa, lo busca en la clase A. Ahi lo encuentra y ejecuta

ˆTranscript show (self name)

Como el self se resuelve dinámicamente, busca el método name en la clase C, lo encuentra y ejecuta

^self ask

Como C no implementa ask, lo busca en B, lo encuentra y ejecuta

^super name

Aqui, super en la clase B es una referencia estática a la clase A, por lo tanto ejecuta name en A, devolviendo

 ˆ"A" 

ahi el llamado do toma de vuelta el control y ejecuta

ˆTranscript show ("A")

Ejercicio 4 - Smalltalk - Colecciones (25 puntos)[editar]

a) (13 puntos) Dada una colección de elementos ordenados, vamos a definir la operación de mezcla de la siguiente manera: se divide la colección en dos mitades, dejando en la mitad de la derecha un elemento más si el total es impar. Luego se genera una nueva colección ordenada tomando alternadamente un elemento de cada mitad, comenzando por la mitad de la derecha. Se pide extender la clase OrderedCollection con un mensaje shuffle: n. Dicho mensaje debe tomar como parámetro un natural n y realizar n veces la operación de mezcla antes mencionada, devolviendo una colección del mismo tipo que el receptor. Por ejemplo:

#(1 2 3 4 5 6 7) shuffle: 1 devuelve #(4 1 5 2 6 3 7)
#(1 2 3 4 5 6 7) shuffle: 2 devuelve #(2 4 6 1 3 5 7)

b) (12 puntos) Extender la clase OrderedCollection con un mensaje deal: aBlock in: n, que recibe un bloque de código de dos argumentos y un entero, y devuelve una nueva colección ordenada que contiene n colecciones c1, . . . , cn. Todas las colecciones deben ser del mismo tipo que la colección receptora. El mensaje debe “repartir” los elementos de la colección receptora entre c1, . . . , cn. La forma de repartirlos es la siguiente: los elementos de la colección receptora se deben distribuir circularmente entre c1, . . . , cn (como si se repartiera un mazo de cartas), comenzando desde el primero y hasta haberlos repartido todos. Luego se debe reemplazar cada elemento e de cada colección ci por el resultado de evaluar aBlock con e e i. No se debe modificar la colección receptora. Por ejemplo:

OrderedCollection(‘a’ ‘b’ ‘c’ ‘d’ ‘e’ ‘f’ ‘g’) deal: [:e :i | e printString, "->", i printString] in: 2

devuelve

OrderedCollection(OrderedCollection("a->1" "c->1" "e->1" "g->1") OrderedCollection("b->2" "d->2" "f->2"))


Respuesta

a)

OrderedCollection:: shuffle: n
| ret |
ret := self.
n timesRepeat: [ret := ret mezcla.].
^ret.
OrderedCollection:: mezcla
| i1 medio i2 ret |
i1 := 1.
medio := (self size / 2) ceiling. i2 := medio.
ret := self class new.
[i2 <= (self size)] whileTrue: [
 ret add: (self at: i2). i2 := i2 + 1.
 i1 < medio ifTrue: [ret add: (self at: i1). i1 := i1 + 1.].
].
^ret.

b)

deal:bl in:n
|res| res := self class new.
1 to n do: [:ni | |tmp| tmp := self class new.
  ni to: (self size) by:n do [:ei |
    tmp add: (bl value: (self at: (ei-1)) value: ni).
  ].
  res add: tmp.
 ].
 ^res.


Ejercicio 5 - Subtipado (20 puntos)[editar]

Supondremos como tipos sólo las funciones, los registros y los nativos bool <: nat <: int <: float, sin considerar top ni bottom. El <: está considerado no estricto.

a) (6 puntos) Demostrar que T <: S si y sólo si existe un A tal que S -> T <: A -> A.

Respuesta

Probamos la ida (=>). Sea T <: S. Buscamos un A tal que S -> T <: A -> A. Esto ocurre sii A <: S y T <: A. En otras palabras podemos decir T <: A <: S. Como el <: está considerado no estricto, en particular A puede ser tanto T como S.

Probamos la vuelta (<=). Sea S -> T <: A -> A. Esto ocurre sólo si A <: S y T <: A, es decir T <: A <: S. Concluimos que T <: S.

b) (8 puntos) Encontrar dos tipos S y T distintos tales que la cantidad de subtipos de S sea igual a la cantidad de subtipos de T, y que lo mismo suceda con los supertipos de cada uno. Ambas cantidades deben ser finitas. Pista: pensar qué sucede con la cardinalidad de los supertipos y los subtipos de A -> A.

Respuesta

Consideramos las funciones sup(T) y sub(T) que representan la cantidad de supertipos y subtipos de T respectivamente. Si T = A -> A

sup(A->A) = sup(A) * sub(A)
sub(A->A) = sub(A) * sup(A)
sup(bool) = 4 (bool, nat, int y float)
sub(bool) = 1 (bool)
sup(float) = 1 (float)
sub(float) = 4 (float, int,nat y bool)

Entonces si consideramos T1 = bool -> bool y T2 = float -> float

sup(float -> float) = sup(bool -> bool)

y sub(float -> float) = sub(bool -> bool)

c) (6 puntos) Supongamos que solo podemos construir tipos con bool y funciones (sin registros). Demostrar que no existen S y T construidos de esa manera tales que haya infinitos tipos X que cumplan S <: X <: T.

Respuesta

Vamos a usar una especie de induccion rara en la cantidad de tipos flecha anidados en el tipo de S.

Caso base:

No hay ninguna flecha, entonces S = bool. Como S <: T, T no puede ser otra cosa que bool (no hay reglas que relacionen bool con ->). Entonces bool <: X <: bool, X no puede ser otra cosa que bool.

Paso inductivo:

S es tipo . Por la misma razón del paso anterior, T tiene que ser . Aplicando S-Arrow tenemos que . Y los X del medio, de la forma tienen que cumplir .

Pero por hipótesis inductiva hay y finitos, y como la suma (finita) de conjuntos finitos es finito, X no puede ser infinito.