Diferencia entre revisiones de «Final 30/7/2015 (Algoritmos II)»
(Cambio por el contenido textual del examen) |
m (Agrega categoría Finales) |
||
| (No se muestran 2 ediciones intermedias de 2 usuarios) | |||
| Línea 1: | Línea 1: | ||
{{back|Algoritmos_y_Estructuras_de_Datos_II}} | |||
'''Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik''' | '''Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik''' | ||
| Línea 17: | Línea 19: | ||
== Ejercicio 5 == | == Ejercicio 5 == | ||
Se cuenta con n elementos que contienen una clave primaria y una secundaria. Hay m<<n claves 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). | 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]] | |||
Revisión actual - 03:56 16 sep 2017
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).
