Recuperatorio Segundo Parcial 2do Cuat 2007 (Paradigmas)

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

Ejercicio 1: Resolución[editar]

Item A[editar]

Pasar las siguientes formulas en logica de primer orden a forma clausal:

Respuesta

Punto 1

Punto 2

Punto 3

Item B[editar]

A partir de las clausulas definidas en el punto anterior, ¿puede demostrarse usando resolucion SLD? Si se puede, hacerlo. Si no, demostrarlo usando el metodo de resolucion general.

Respuesta

No se puede usar resolución SLD dado que las cláusulas no son de Horn (la primera ya tiene más de un término positivo). Procedemos a usar resolución general.

Negamos el goal

Resolvemos

  1. 5 con 2:
  2. 7 con 3:
  3. 8 con 1:
  4. 9 con 6:

Ejercicio 2: Programación Lógica[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]

Definir el predicado pesoMaximo(+Lista, -Peso) que dada una lista Lista heterogenea que puede contener numeros enteros o listas, debe ser verdadero cuando Peso sea el peso del elemento mas pesado de la lista. Para ello se tendra en cuenta que el peso esta representado:

  1. en los numeros, por su valor absoluto.
  2. en las listas, por la suma de los pesos de sus elementos.
?- pesoMaximo([5, [2,3], 8, [4,8,9], [5,4,[1,11]], -2], P). 
P = 21 ; 
No 

La lista vacia tiene peso 0, y no tiene elemento mas pesado (ni peso maximo).

Respuesta

peso([], 0).
peso([X|XS], P) :- peso(X, XP), peso(XS, XSP), P is XP+XSP.
peso(X, Y) :- number(X), X < 0, Y is -X.
peso(X, X) :- number(X), X >= 0.

listaDePesos([], []).
listaDePesos([X|XS], [Y|YS]) :- peso(X, Y), listaDePesos(XS, YS).

pesoMaximo(L, P) :- listaDePesos(L, LP), list_to_set(LP, S), max_list(S, P).

Item B[editar]

Definir el predicado elementoMasPesado(+Lista, -Elemento) que dada una lista como la del punto anterior y un elemento de la misma, tenga exito cuando Elemento sea el elemento mas pesado de la lista.

?- elementoMasPesado([5, [2,3], 8, [4,8,9], [5,4,[1,11]], -2], E). 
E = [4, 8, 9] ; 
E = [5, 4, [1, 11]] ; 
No 

Respuesta

elementoMasPesado(L, E) :- member(E, L), pesoMaximo(L, PM), peso(E, PM).

Item C[editar]

Escribir el predicado listaQueSuma(+Suma,+Longitud,-Lista), que tenga exito cuando Lista sea una lista de numeros naturales de longitud Longitud cuyos elementos sumen Suma. Se considera definido entre(+X,+Y,-Z) visto en clase.

Respuesta

entre(A, B, A) :- number(A), number(B), B >= A.
entre(A, B, X) :- AA is A+1, B >= AA, entre(AA, B, X).

listaQueSuma(S, LO, LI) :- length(LI, LO), miembrosHasta(LI, S), sumlist(LI, S).

miembrosHasta([], N) :- number(N).
miembrosHasta([X|XS], N) :- entre(0, N, X), miembrosHasta(XS, N).

Respuesta alternativa

entre(A, B, A) :- number(A), number(B), B >= A.
entre(A, B, X) :- AA is A+1, B >= AA, entre(AA, B, X).

listaQueSuma(0, 0, []).
listaQueSuma(S, Long, [E|ES]):- Long >0, entre(0,S,E), R is S-E, Long2 is Long-1,   listaQueSuma(R, Long2, ES).

Item D[editar]

Dado un tablero de n x n con numeros enteros al margen de cada fila y columna, se debe completar el tablero con numeros del 1 al 5 (pueden ser repetidos), logrando que cada fila y columna sume el valor indicado al margen.

Definir el predicado tableroValido(-Tablero, +SumasPorFila, +SumasPorColumna) que resuelva el problema planteado anteriormente (el tablero puede venir total o parcialmente instanciado, o sin instanciar).

El tablero se representa con una lista de filas (que a su vez son listas de numeros), y las anotaciones en los margenes se representan con listas de numeros.

En el ejemplo de arriba (ver parcial original), Tablero = [[1,3,1],[4,3,2],[3,3,5]], SumasPorFila = [5,9,11], SumasPorColumna = [8,9,8].

Se asume definido el predicado trasponer(+Filas,-Columnas) que tiene exito cuando Filas es una lista de filas de igual longitud y Columnas es la lista de columnas correspondiente (o de filas de la matriz traspuesta, si se ve la lista de filas como una matriz).

Respuesta

tableroValido(T, F, C) :-
    length(F, N),
    length(C, N),
    dimensionesOk(T, N),
    filasSuman(T, F),
    columnasSuman(T, C),
    rangoOk(T).

rangoOk([]).
rangoOk([F|FS]) :-
    rangoFilaEntre(F, 1, 5),
    rangoOk(FS).

rangoFilaEntre([], _, _).
rangoFilaEntre([N|NS], A, B) :-
    entre(A, B, N),
    rangoFilaEntre(NS, A, B).

dimensionesOk(T, N) :-
    % que el tablero tenga la cantidad de filas correspondientes
    length(T, N),
    % que el tablero tenga la cantidad de columnas correspondientes
    filasDeLongitud(T, N).

filasDeLongitud([], _).
filasDeLongitud([F|FS], N) :-
    length(F, N),
    filasDeLongitud(FS, N).

filasSuman([], []).
filasSuman([F1|FS], [N|NS]) :-
    length(F1, LO),
    listaQueSuma(N, LO, F1),
    filasSuman(FS, NS).

columnasSuman(T, C) :-
    columnas(T, COLS),
    filasSuman(COLS, C).

columnas(T, C) :-
    columnasAux(T, C, 0).

columnasAux(T, [], I) :- length(T, I).
columnasAux(T, [C|CS], I) :-
    length(T, L),
    I < L,
    nCol(T, I, C),
    I2 is I + 1,
    columnasAux(T, CS, I2).

nCol([], _, []).
nCol([F|FS], I, [C|CS]) :-
    nth0(I, F, C),
    nCol(FS, I, CS).

Me colgué y no usé trasponer, bueno, mejor así se ve como podria estar implementado. Creo que el análogo vendría a ser columnas.

Respuesta (mas corta)

filasValidas([],[],_).
filasValidas([X|XS],[S|SS], L) :- listaQueSuma(S,L,X), filasValidas(XS,SS,L).

tableroValido(Tablero,SumaFila,SumaCol) :- length(SumaCol, FLen), filasValidas(Tablero, SumaFila,FLen), trasponer(Tablero, TT),  length(SumaFila,CLen), filasValidas(TT, SumaCol,CLen).

y aca va una implementacion de trasponer para probar:

heads([],[]).
heads([[Y|_]|XS], P) :- heads(XS,R), append([Y],R,P).

tails([],[]).
tails([[_|YS]|XS], P) :- tails(XS,R),  append([YS],R,P).

transpose1([],[]).
transpose1([[]|XS],[]) :- transpose1(XS,[]).
transpose1([X|XS], [T|TS]) :- heads([X|XS], T), tails([X|XS],R), transpose1(R,TS).

Ejercicio 3: Colecciones[editar]

Item A[editar]

Agregar a la clase Collection un metodo con la siguiente interfaz:

valorMinimoDe: unBloque 

donde unBloque es un bloque con un parametro de entrada cuya evaluacion devuelve un numero. El metodo debe evaluar el bloque en todos los elementos de la coleccion receptora, y devolver el minimo de todos los valores obtenidos. Se asume que la coleccion receptora no esta vacia.

Por ejemplo, la evaluacion de la siguiente expresion:

#(’perro’ ’tejon’ ’marron’) valorMinimoDe: [:x | x size] devuelve 5. 

Sugerencia: usar los metodos min: aMagnitude de la clase Magnitude, y fold: aBlock de la clase Collection.

Respuesta 1

valorMinimoDe: bloque
    |convertidos min|
    convertidos := self collect: bloque.
    min := convertidos anyOne.
    convertidos do: [:e | (e < min) ifTrue: [min := e]].
    ^min.

Respuesta 2

valorMinimoDe: bloque
    ^self inject: ([bloque value: (self anyOne)] value)
        into: [:m :e | m min: (bloque value: e)].


Respuesta 3

valorMinimoDe: bloque
    ^(self collect: [:e | bloque value: e]) fold: [:a :b | b min: a]

Item B[editar]

La clase Point se utiliza para representar puntos en el plano. El punto (x, y) se representa en Smalltalk como (x @ y). La clase cuenta, entre otros, con los metodos x e y para acceder a las respectivas componentes, x: e y: para cambiar su valor, y dist: para obtener la distancia (Float) entre el ob jeto receptor y otro punto.

Agregar a la clase Collection el metodo masCercanosA: unPunto, que devuelva una coleccion de la misma clase que la receptora con los puntos que est´en a menor distancia del punto pasado como parametro. Descartar todos los elementos que no sean puntos. Si la coleccion no tiene puntos, devolver una coleccion vacia.

Respuesta

masCercanosA: punto
    |puntos mindist|
    puntos := self select: [:e | e isPoint].
    (puntos isEmpty) ifTrue:[^puntos].
    mindist := puntos valorMinimoDe: [:e | e dist: punto].
    ^puntos select: [:e | (e dist: punto) = mindist].

Nota: Esta respuesta funciona en Squeak, en VisualWorks no funciona el mensaje isPoint, en su lugar usar isKindOf: Point.

Test Case (para Squeak)

| c p1 p2 p3 |
p1 := Point new.
p1 setX:10 setY:20.
p2 := Point new.
p2 setX:-5 setY:1.
p3 := Point new.
p3 setX:5 setY:1.
c := OrderedCollection new.
c add: p1; add: p2; add: p3.
c masCercanosA: [|p| p := Point new. p setX:0 setY:0.p] value.

Test Case (para VisualWorks)

| c p1 p2 p3 |
p1 := Point x:10 y:20.
p2 := Point x:-5 y:1.
p3 := Point x:5 y: 1.
c := OrderedCollection new.
c add: p1; add: p2; add: p3.
c masCercanosA:  (Point x:0 y:0).

Ejercicio 4: Herencia[editar]

Se tiene una clase A y sus dos subclases B y C.

El codigo de cada mensaje de estas clases consta de exactamente 2 sentencias: la primera es “Transcript show ‘L’” donde L es A, B o C segun la clase en la que se encuentra (cada una imprime su propio nombre). La segunda y ultima sentencia de cada mensa je contiene la palabra super o self seguida de un nombre de mensaje.

Para cada una de las siguientes cadenas se pide dar una sentencia inicial y una implementacion de los mensajes dentro de las clases A, B o C de modo que dicha cadena sea la impresa en el Transcript y que la cantidad de mensajes implementados sea minima. La idea es que la ejecucion nunca termine y vaya imprimiendo una cadena infinita en el Transcript. Cada mensa je cuenta 1 vez, sin importar en cuantas clases este implementado.

Si alguna de las cadenas no se puede imprimir, explicar por que.

  1. ABBABBABBABBABBABB...
  2. BAABAABAABAABAABAA...
  3. ABCABCABCABCABCABC...
  4. ACAACACAACACAACACAAC...

Item 1[editar]

Esta cadena debería empezar con un

(B new) msg1

Luego podría definirse en A:

msg1: self msg2

En B:

msg2: self msg3
msg3: self msg1

Item 2[editar]

Esta cadena debería empezar con un

(B new) msg1

Luego podría definirse en A:

msg1: self msg2
msg2: self msg1

En B:

msg1: super msg1

Item 3[editar]

Item 4[editar]

Ejercicio 5: Subtipado[editar]

Indicar y justificar cuantos subtipos tiene cada uno de los siguientes tipos:

Item A[editar]

Respuesta

Tiene tantos subtipos como sub(CoDom) * sup(Dom), en este caso sub(CoDom) es infinito por ser un registro por lo tanto tiene infinitos subtipos.

Item B[editar]

Respuesta

Item C[editar]

Respuesta