Final 1C/2006 (Algoritmos II)

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

Esteban Feuerstein y Ricardo Rodríguez

Ejercicio 1[editar]

a) Especificar (dar observadores, generadores, axiomas, igualdad observacional, etc.) el TAD diccionario de frases, compuesto de k palabras como máximo. Cada palabra es una cadena de caracteres.

b) Proponer una estructura de representación tal que la complejidad temporal sea independiente de la cantidad de frases.

c) Describir como implementar la operación listar-palabras con la estructura de b. Analizar la complejidad. Podría hacerse mas eficiente con otra estructura?

Ejercicio 2[editar]

Sea la siguiente función de Quatrinacci:

f(1) = 1
f(2) = 3
f(3) = 5
f(n) = 3 f(n-1) + 2 f(n-2) - f(n-3)

a) Escribir la función recursiva.

b) Encuentre usando técnicas de generalización una función recursiva equivalente que sea lineal a la cola. Pruebe que son equivalentes.

c) Obtener el iterativo.

Ejercicio 3[editar]

Dado un conjunto de puntos de 1 recta dar un algoritmo para determinar los 2 puntos mas cercanos que tenga complejidad . Proponer un algoritmo D&C y estimar su complejidad. El algoritmo dado no puede ordenar el input y luego recorrer buscando la mínima distancia entre adyacentes. Hint: asumir dada una rutina que en tiempo lineal encuentra el elemento mediano de un conjunto. Si los puntos fueran en el plano y la distancia fuera la euclídea, cómo extendería el resultado anterior?

Ejercicio 4[editar]

Discutir la posibilidad de implementar cola de prioridades con arrays, ABBs, AVLs y Árboles B.