Final 30/7/2015 (Algoritmos II)

De Cuba-Wiki

Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik


Ejercicio 1

Dado un sistemas de TADs TAD' que difiere de los tads comunes en que tiene solo axiomas y operaciones, y la igualdad se da por equivalencia de axiomas, es decir, se puede ir de t1 a tn aplicando los axiomas.

  • a) Qué problema grave de los TADs comunes evita esta especificación?
  • b) Qué dificultad tiene escribir el tad conjunto con esta especificación?

Ejercicio 2

Demostrar porque se puede hacer inducción sobre los TADS (explicale a un matemático).

Ejercicio 3

Relación invariante de representación y complejidad algorítmica. Relación función de abstracción con la demostración de que tu diseño es correcto.

Ejercicio 4

Era el de closerToAvg de otros parciales, conjunto de racionales, discutir 4 variantes sobre estructuras vistas en clase.

Ejercicio 5

Dados N elementos, cada uno con clave primaria y secundaria, m << n, m ‪#‎claves‬ secundarias. Dar 2 formas eficientes de ordenarlos. (Primero por primarias, luego por secundarias.)