Final 1C/2014 (Algoritmos II)

Plantilla:Back Final del 6/8/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 × 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

Invariante de representación

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?