Final 13/12/17 (Algoritmos II)

Final tomado por Carlos Gustavo Lopez Pombo

Ejercicio 1

Demostrar por qué la altura de un árbol de Fibonacci es logarítmica respecto a la cantidad de nodos.

Ejercicio 2

Comparar los algoritmos de ordenamiento que son O(n log n) en aspectos como uso de memoria adicional, hipótesis sobre el input, etc.

Ejercicio 3

Explicar los métodos de resolución de recurrencias vistos en la materia, y compararlos.

Ejercicio 4

Relacionar el invariante de representación con la complejidad temporal y la función de abstracción con la demostración de que un diseño es correcto respecto a su especificación.

Ejercicio 5

Describir detalladamente qué son los observadores básicos y explicar por qué se los usa para definir las otras operaciones, y por qué mantienen las características del lenguaje.