Final 1C/2014 (Algoritmos II)

Plantilla:Back Final del 22/7/14 y del 6/8/14. Tomado por Feuer y Chapa

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 × coord × coord. → Plano

Observadores:

• Hay_punto?: Plano × coord. → Bool

Otras operaciones:

• Agregar_punto: Plano × 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

22/7/14

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.

6/8/14

Para qué sirve el invariante de representación, dar ejemplos de como se relaciona con la complejidad.

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?