Diferencia entre revisiones de «Final 1C/2014 (Algoritmos II)»
Sin resumen de edición |
Sin resumen de edición |
||
Línea 1: | Línea 1: | ||
{{Back|Algoritmos y Estructuras de Datos II}} | {{Back|Algoritmos y Estructuras de Datos II}} | ||
Final del 6/8/14 | Final del 6/8/14 | ||
== Ejercicio 1 == | == Ejercicio 1 == |
Revisión del 22:55 6 ago 2014
Plantilla:Back Final del 6/8/14
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?