Diferencia entre revisiones de «Final 30/7/2015 (Algoritmos II)»
Sin resumen de edición |
(Cambio por el contenido textual del examen) |
||
| Línea 1: | Línea 1: | ||
'''Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik''' | '''Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik''' | ||
== Ejercicio 1 == | == 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 == | == Ejercicio 2 == | ||
Explíquele a un matemático por qué se puede aplicar el principio de inducción estructural sobre cualquier TAD. | |||
== Ejercicio 3 == | == 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 == | == 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 == | == 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). | |||
Revisión del 16:39 1 ago 2015
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 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).
