Download 2º Certamen ILI-253 Lenguajes de Programación

Nombre:
2º Certamen ILI-253
Lenguajes de Programación
Paralelo:
Nota:
Juan Pablo Menichetti – Jorge Mujica
10 de Junio del 2004
Tiempo: 120 Minutos. Responda con lápiz indeleble para acceder a recorrecciones. Utilice solo las hojas
incluidas en este documento. Preguntas incorrectas no descuentan puntos.
I – Preguntas Teóricas (45 ptos)
A - Matriz de Lenguajes (9 puntos, 3 puntos c/paradigma)
Respecto a su definición pura, marque con una cruz las características requeridas por cada uno de los tres
paradigmas de programación:
Existencia de herencia
Definición de estructuras de control de flujo
Eliminación del efecto lateral
Énfasis en los algoritmos
Énfasis en los resultados
Un programa debe entregar siempre el mismo
resultado bajo la misma entrada
a) Orientación
a objetos
X
X
b) Funcional
c) Lógica
X
X
X
X
X
X
X
X
B - Preguntas de alternativas (24 puntos, 3 puntos c/u)
1.
a)
b)
c)
d)
Prolog es un lenguaje declarativo porque
Permite declarar cláusulas lógicas
Pone énfasis en la declaración de metas, no de algoritmos
El programador no requiere conocer el flujo de ejecución
El flujo de búsqueda está encapsulado y no se puede intervenir
i, ii y iii
i y iii
Solo i
Todas
a)
b)
c)
d)
Respecto a la orientación a objetos, se puede decir que no es una
característica de esta:
La definición de clases
La herencia
El polimorfismo
El efecto lateral
a)
b)
c)
d)
Respecto a la orientación a objetos en Scheme y Prolog se puede decir que
Scheme implementa encapsulamiento en la forma de (let ...)
Scheme permite simular la herencia utilizando funciones lambdas anidadas.
Prolog define comportamiento polimórfico por su debilidad de tipado.
No tiene sentido hablar de herencia en Prolog por que no existe el concepto de asignación.
a)
b)
c)
d)
El operador de “calce” en Prolog:
Genera siempre instanciación de variables en el operando izquierdo
Solo puede generar la instanciación de variables en el operando izquierdo
Puede generar la instanciación de variables tanto en el operando izquierdo como en el derecho
Genera siempre instanciación de variables en el operando derecho
i.
ii.
iii.
iv.
2.
3.
4.
1
A
5
C
2
D
6
B
3
A
7
D
4
C
8
B
1
Nombre:
5.
i.
ii.
iii.
iv.
v.
a)
b)
c)
d)
6.
a)
b)
c)
d)
7.
a)
b)
c)
d)
8.
Paralelo:
Scheme no es un lenguaje funcional puro porque:
Permite definir funciones como parámetros de funciones
Las funciones lambda generan efecto lateral
Los let generan efecto lateral
Utiliza el concepto de variable
Permite le inclusión de lógica imperativa a través de la función begin
i, iv y v
i, ii, iv y v
iv y v
i, iii, iv, v
Se entiende por backtracking:
Una búsqueda en profundidad en un árbol binario
Una búsqueda que elimina ramas infactibles en un árbol de soluciones
Una técnica de programación que puede predecir resultados óptimos de manera eficiente.
Una heurística que parte de una solución inicial que disminuye el tamaño del problema y luego
soluciona, recursivamente, el nuevo problema disminuido.
Respecto al operador “cut” en Prolog podemos decir que:
Permite implementar un operador de negación
Limita el espacio de búsqueda de soluciones
Implica conocer el orden de evaluación de las reglas
Todas las anteriores
Se entiende por transparencia referencial al hecho de que:
Dos variables con igual nombre comparten una misma referencia, en forma transparente al
programador.
b) La evaluación de una función retorna siempre el mismo resultado
c) Una función hace referencias internas a otras funciones en forma transparente al programador
d) Al momento de entrar a una función let donde se usa una variable determinada, cualquier
referencia global a una misma variable (igual nombre) se posterga en forma transparente.
a)
C – Análisis de Prolog (12 puntos, 3 puntos c/u)
Indique la respuesta entregada por Prolog dados los siguientes hechos y reglas (el orden de salida es
relevante):
asesinato(lago).
asesinato(plaza).
lugar(pedro, plaza).
lugar(juan, plaza).
lugar(maria, lago).
lugar(patricia, casa).
consciente(pedro).
sospechoso(X) :- asesinato(Y), lugar(X,Y).
culpable(X) :- sospechoso(X), consciente(X).
Consulta
Respuesta
lugar(X, plaza).
X = pedro ;
X = juan ;
No
sospechoso(X),!.
X = maria ;
No
Culpable(X).
X = pedro ;
No
Sospechoso(X), !, consciente(X).
No
2
Nombre:
Paralelo:
II - Preguntas de desarrollo (55 ptos)
A - Programación en Scheme (30 puntos)
Una posible representación de matrices bidimensionales es utilizar el concepto recursivo de “matrizsubmatriz”. En Scheme podemos implementar este concepto a través de listas como se detalla a
continuación:
Si M es una matriz nula, se representa por una lista nula. En caso contrario, M se define como una lista de
cuatro elementos:
1. El elemento de la diagonal
2. Una lista representando los elementos de la primera fila sin contar la diagonal. Esta lista es nula
en el caso de una matriz 1x1.
3. Una lista representando los elementos de la primera columna sin contar la diagonal. Esta lista es
nula en el caso de una matriz 1x1.
4. Una submatriz S, que será una matriz nula en el caso que M sea una matriz 1x1.
Ejemplos:
(5)
1 2 3 4 


 5 8 9 10 
 6 11 13 14 


 7 12 15 16 


1 0


0 1
1 2 3


 2 2 4
 3 4 3


(5 () () ())
(1 (2 3 4) (5 6 7) (8 (9 10) (11 12) (13 (14) (15) (16 () () ()))))
(1 (0) (0) (1 () () ()))
(1 (2 3) (2 3) (2 (4) (4) (3 () () ())))
Dada la definición anterior, y asumiendo matrices cuadradas y solo con valores numéricos,
implemente:
a) Una función en Scheme que entregue la matriz transpuesta de una matriz dada. (15 ptos)
b) Una función en Scheme que entregue la suma de los elementos de la diagonal de una matriz
utilizando solo recursión de cola. (15 ptos)
3
Nombre:
Paralelo:
Solución II-A
a)
(define traspuesta
(lambda (x)
(if
(null? x)
'()
(list
(car x)
(caddr x)
(cadr x)
(traspuesta (cadddr x))
)
)
)
)
b)
(define suma-diag
(lambda (x)
(let s-d ((ls x) (s 0))
(if
(null? ls)
s
(s-d (cadddr ls) (+ s (car ls)))
)
)
)
)
4
Nombre:
Paralelo:
B.- Programación en Prolog (25 puntos)
Una lista palíndrome es aquella lista no vacía que se puede leer de igual forma tanto de izquierda a
derecha como de derecha a izquierda. Por ejemplo,
A = [1,2,3,2,1]
a) Implemente el predicado inverse(X,R) el cual asigna a R la lista X invertida. (15 ptos)
b) Implemente el predicado palindrome(X) el cual utiliza a inverse(X,R) para determinar
si la lista X (no vacía) posee dicha particularidad. (10 ptos)
Puede implementar hechos y reglas auxiliares adicionales si lo considera necesario.
5
Nombre:
Paralelo:
Solución II-B
inverso([], []).
inverso([X | L], L1) :inverso(L, L2),
conc(L2, [X], L1).
palindrome(L)
:-
inverso(L, L).
6