Final 1C/2014 (Algoritmos II)
Final del 22/7/14, aportado por Francisco Noriega
Ejercicio 1
El sistema de especificación TADSOB es como el de los TAD pero no tiene observadores básicos. Cuenta solamente con generadores y operaciones en general. Piense en los TADs básicos que conoce y discuta las limitaciones de los TADSOB.
Ejercicio 2
Se tiene el siguiente TAD:
TAD PLANO
Generadores:
- Vacío -> Plano
- Agregar_segmento: plano x coord x coord. -> Plano
Observadores:
- Hay_punto?: Plano x coord. -> Bool
Otras operaciones:
- Agregar_punto: Plano x coord. -> Plano
Axiomas:
- Hay_punto? (Vacío, c) = false
- Hay_punto? (Agregar_segmento(p,c0,c1),c) = (cuenta matemática apropiada, irrelevante a los fines del ejercicio)
agregar_punto(p,c) = agregar_segmento(p,c,c)
¿Se puede plantear una demostración por inducción estructural de una propiedad sobre el TAD Plano utilizando en su planteo solo Vacio(), Agregar_Punto() y Hay_Punto?()? Justifique.
Ejercicio 3
a. Justifique por qué la función de abstracción no siempre es sobreyectiva sobre el conjunto de términos de un tipo abstracto de datos.
b. ¿Podría el invariante de representación no ser una función total? Justifique.
Ejercicio 4
Se desea un TAD que permita representar conjuntos de números racionales donde a las tradicionales operaciones de Agregar(S,x) y Borrar(S,x), se le agrega 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 Conj/Dicc standards.
Ejercicio 5
¿Cómo ordenaría elementos que nos son dados en ráfagas de tamaño N para incorporar a otros ya ordenados de tamaño M, con M >> N?
