Ver el código de «Final 30/7/2015 (Algoritmos II)»

{{back|Algoritmos_y_Estructuras_de_Datos_II}}

'''Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik'''

== 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.
# Este sistema de especificación no tiene uno de los problemas formales más importantes que puede tener un TAD. ¿Cuál? ¿Por qué?
# ¿Qué dificultad presenta la especificación del TAD' conjunto en este formalismo?

== Ejercicio 2 ==
Explíquele a un matemático por qué se puede aplicar el principio de inducción estructural sobre cualquier TAD.

== Ejercicio 3 ==
Explique la relación entre invariante de representación y complejidad algorítmica, y entre función de abstracción y la demostración de que el diseño es correcto con respecto a la especificación.

== Ejercicio 4 ==
Se desea implementar un TAD que permita representar un conjunto de números racionales, donde a las tradicionales operaciones de Agregar(S,x) y Borrar(S,x) se agrega la siguiente: CLOSERTOAVG(S), que toma como input un conjunto S y devuelve el valor contenido en S más cercano al promedio de los valores contenidos en S.
Discutir la implementación de este TAD utilizando variantes de al menos 4 estructuras de datos vistas en clase para representar conjuntos/diccionarios standard.

== Ejercicio 5 ==
Se cuenta con n elementos que contienen una clave primaria y una secundaria. Hay m<<n claves secundarias distintas. Proponga dos formas eficientes y distintas que permitan ordenar los n elementos, en base a las dos claves (primero la primaria, luego la secundaria).

[[Categoría: Finales]]