Final 15/02/2015 (Algoritmos II)

Charlie

Ejercicio 1

El sistema de especificación TAD' es muy similar a los TADs que se utilizan en la materia, pero su única igualdad entre instancias se define así: dos instancias son iguales si y solo si aplicando axiomas se puede llegar de una a la otra.

1. Este sistema de especificación no tiene uno de los problemas formales más importantes que puede tener un TAD. ¿Cuál? ¿Por qué?
2. ¿Qué dificultad presenta la especificación del TAD' conjunto en este formalismo?

Ejercicio 2

Explicar por qué la función de abstracción no es sobreyectiva sobre el conjunto de términos. ¿Hay algún conjunto para el que sí lo sea?

Ejercicio 3 (no textual)

Escribir el algoritmo que convierte un arreglo a un heap, justificar su complejidad y por qué lo usaría de estructura soporte.

Ejercicio 4

Vincular la forma general de los algoritmos que utilizan la técnica de divide and conquer con la forma en la que se obtiene la ecuación de recurrencia que caracteriza la complejidad de un algoritmo recursivo y con los casos del teorema maestro.

Ejercicio 5 (no textual)

Enumerar y describir los tipos de recursión que se pueden eliminar con las técnicas vistas en la materia. Dar una esquematización (descripción general) de como aplicaría cada una. Enuncia, si recuerda, alguna recursión que no pueda ser eliminada con las técnicas vistas.