Recuperatorio Segundo Parcial 2do Cuat 2005 (Paradigmas)

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

Ejercicio 1: Prolog[editar]

Item A[editar]

Definir el predicado particion(+Lista,-Particion), que dado una Lista de elementos, debe dar verdadero cuando Particion es una lista de listas cuyos elementos son subsecuencias de la lista original. Las subsecuencias pueden tener cualquier longitud, excepto 0. Debe cumplirse que si se concatenan todas las subsecuencias en el orden que aparecen en Particion debe obtenerse la lista original. Por ejemplo:

?- particion([1,2,3],P).
P = [[1, 2, 3]] ;
P = [[1], [2, 3]] ;
P = [[1, 2], [3]] ;
P = [[1], [2], [3]] ;
No

Respuesta

particion([], []). 
particion([[X] | YS], [X | ZS]) :- particion(YS, ZS). 
particion([[X1, X2 | XS] | YS], [X1 | ZS]) :- particion([[X2 | XS] | YS], ZS).

Item B[editar]

Se cuenta con el predicado letra(-Letra) que da verdadero cuando Letra es uno de los atomos a, b,... o z. Si Letra no se encuentra instanciado, este predicado devuelve, a medida que sean solicitadas, todas las posibles letras. Por ejemplo:

?- letra(X).
X = a;
X = b;
...
X = z;
No

Se define una codificacion como una traduccion de listas de elementos a letras. Por ejemplo, la codificacion [([1,0],a), ([1,0],a), ([0],b)] sirve para traducir la lista de elementos [1,0,1,0,0] a aab. Una codificacion es valida si cumple las siguientes condiciones:

  • Dos secuencias distintas de elementos no pueden representar a una misma letra. Por ejemplo, la codificacion [([1,0],a), ([0],b), ([1,1],a)] no es valida.
  • Una misma secuencia de elementos no pueda representar a dos letras distintas. Por ejemplo, la codificacion [([1,0],a), ([0],b), ([1,0],c)] no es valida.
  • La codificacion debe ser completa. Si L es una lista de elementos y

c = [(ca1, s1), (ca2, s2), ..., (can, sn)] es un codificacion de L, entonces ca1+ca2+...+can = L.

Nota: Los elementos de las listas no necesariamente tienen que ser numeros. Se pide definir el predicado codificacion(+Lista,-Codificacion), que dado una Lista de elementos, debe dar verdadero cuando Codificacion es una codificacion valida para Lista. Si Codificacion no esta instanciado, debe generar todas las posibles codificaciones validas. Por ejemplo,

?- cod([1,0,1],C).
C = [ ([1, 0, 1], a)];
C = [ ([1, 0, 1], b)];
...
C = [ ([1, 0, 1], z)];
C = [([1], a), ([0, 1], b)];
C = [ ([1], a), ([0, 1], c)];
...
C = [ ([1, 0], z),([1], y)];
C = [ ([1], a), ([0], b), ([1], a)];
...
C = [ ([1], a), ([0], z), ([1], a)];
C = [ ([1], b), ([0], a), ([1], b)];
...
C = [ ([1], z), ([0], y), ([1], z)];
No

Respuesta

distintos([]).
distintos([A|AS]) :- not(member(A,AS)), distintos(AS).

secuencias([],[]).
secuencias([(S,_)|ES],[S|RS]) :- secuencias(ES,RS).

letras([],[]).
letras([(_,A)|ES],[A|RS]) :- letras(ES,RS).

gencodif([],[]).
gencodif([L|LS],[(L,A)|RS]) :- letra(A), gencodif(LS,RS).

codificacion(L,C) :- particion(P,L), gencodif(P,C), secuencias(C,S), distintos(S), letras(C,A), distintos(A).

Item C[editar]

Definir el predicado libreDePrefijos(+Lista,-Codificacion), que dado una Lista de elementos, debe dar verdadero cuando Codificacion cumple los requisitos del ıtem anterior, y ademas las secuencias de elementos que aparecen en la codificacion no son prefijos entre sı. Por ejemplo, la codificacion [([1,0],a), ([0],b), ([1],c)] no es libre de prefijos dado que [1] es prefijo de [1,0].

Respuesta

esPrefijo(L,S) :- append(L,_,S).
checkPrefijos([],_).
checkPrefijos([L|LS],S) :- checkPrefijo(L,S), checkPrefijos(LS,S).
checkPrefijo(L,[]).
checkPrefijo(L,[L|SS]) :- checkPrefijo(L,SS).
checkPrefijo(L,[S|SS]) :- not(L=S), not(esPrefijo(L,S)), checkPrefijo(L,SS).

libreDePrefijos(L,C) :- codificacion(L,C), secuencias(C,S), checkPrefijos(S,S).


Ejercicio 2: Smalltalk[editar]

Ejercicio 3: Smalltalk[editar]