Final 2/2C/2009 (Algoritmos II)

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

Para considerarse aprobado deben estar bien al menos 3 ejercicios.

Ejercicio 1[editar]

  • Escribir (en castellano) la propiedad que hace que un ABB sea AVL (o sea, el invariante).
  • Proponer un algoritmo que verifique en tiempo lineal si un ABB cumple el invariante de AVL.
  • Presentar un ejemplo de árbol AVL en el cual el borrado de un elemento dé lugar a más de una rotación.

Ejercicio 2[editar]

Responda justificando.

  • ¿Cuándo decimos que una función no es congruente con la igualdad observacional?
  1. Cuando diferencia más instancias que los observadores básicos.
  2. Cuando es redundante con respecto a los observadores básicos.
  3. Ambas.
  4. Ninguna.
  • ¿Cuál es la diferencia entre tipo y género (por ejemplo, entre NAT y nat)?
  • ¿Qué criterio utilizaría para definir si una operación puede ser generador o ser otra operación?

Ejercicio 3[editar]

Considere el TAD MinColaDePrioridad enriquecido con la operación DisminuirPrioridad(p,x) que, dado un elemento de clave p, le disminuye la prioridad a p en x unidades.

  • Discutir las modificaciones a realizar a las representaciones clásicas de colas de prioridad para incorporar eficientemente la operación DisminuirPrioridad(p,x) y describir brevemente el algoritmo para esa operación, y su complejidad.
  • ¿Y si además se quiere incorporar la operación AumentarPrioridad(p,x)?

Ejercicio 4[editar]

Responda justificando.

  • ¿Tiene sentido programar una implementación del invariante de representación?
  • ¿Y la función de abstracción?
  • ¿Puede el invariante ser restricción de una función auxiliar? ¿Debe serlo?
  • Dé dos ejemplos de relaciones entre invariante de representación y complejidad de los algoritmos.

Ejercicio 5[editar]

Dada la siguiente frase construida sobre el alfabeto {,A,B,D,L,E,O,R,Z}:

DABALE ARROZ A LA ZORRA EL ABAD DEL ARROZAL
  • Construir un código de Huffman para los caracteres de la frase (dar el árbol o la tabla de códigos).
  • ¿Cuántos bits se ganan en la codificación de la frase con respecto a la utilización de un código de longitud fija?
  • Discutir aspectos relacionados con la implementación del algoritmo de Huffman (¿qué estructuras de datos usaría para hacerlo en forma eficiente? ¿qué complejidad resultaría su algoritmo?).