Diferencia entre revisiones de «Final 30/7/2015 (Algoritmos II)»
(Página creada con «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 pue...») |
m (Agrega categoría Finales) |
||
| (No se muestran 6 ediciones intermedias de 3 usuarios) | |||
| Línea 1: | Línea 1: | ||
1 | {{back|Algoritmos_y_Estructuras_de_Datos_II}} | ||
'''Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik''' | |||
2 | == Ejercicio 1 == | ||
3 | 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é? | |||
4) | # ¿Qué dificultad presenta la especificación del TAD' conjunto en este formalismo? | ||
5 | |||
== 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]] | |||
Revisión actual - 03:56 16 sep 2017
Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik
Ejercicio 1[editar]
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[editar]
Explíquele a un matemático por qué se puede aplicar el principio de inducción estructural sobre cualquier TAD.
Ejercicio 3[editar]
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[editar]
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[editar]
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).
