| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| {{back|Algoritmos_y_Estructuras_de_Datos_II}}
| | 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. |
| '''Esteban Feuerstein, Flavia Bonomo y Fernando Schapachnik'''
| | 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 1 ==
| | 2) Demostrar porque se puede hacer inducción sobre los TADS (explicale a un matemático). |
| 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.
| | 3) Relación invariante de representación y complejidad algorítmica. |
| # Este sistema de especificación no tiene uno de los problemas formales más importantes que puede tener un TAD. ¿Cuál? ¿Por qué?
| | Relación función de abstracción con la demostración de que tu diseño es correcto. |
| # ¿Qué dificultad presenta la especificación del TAD' conjunto en este formalismo?
| | 4) Era el de closerToAvg de otros parciales, conjunto de racionales, discutir 4 variantes sobre estructuras vistas en clase. |
| | | 5) Dados N elementos, cada uno con clave primaria y secundaria, m << n, m #claves secundarias. |
| == Ejercicio 2 ==
| | Dar 2 formas eficientes de ordenarlos. (Primero por primarias, luego por secundarias.) |
| 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]]
| |
