Final 2/2C/2008 (Algoritmos II)
Ejercicio 1[editar]
Dado un diseño con invariante I1, se consideraba el invariante I2 el cual es mas fuerte que I1 (es decir, I2 implica I1). Mantener el invariante I2 es muy complejo (temporalmente) pero existe una funcion privada Optimizar(), la cual es muy cara, que se puede usar para establecer I2.
Si se usa Optimizar() se pide
- a)que pre y post tiene la funcion Optimizar
- b)que cambia en la interfaz del diseño
- c)como queda el invariante
- d)como queda el abs
- e)como quedan los servicios exportados.
Mini solucion: a) pre I1, post I2. b) cambia algun algoritmo el cual llama a optimizar() en algun caso (por ej cuando algun funcion 'detecta' que la estructura es ineficiente en su estado actual). c) queda igual porque I2 fuerza I1. d) queda igual porque la estructura de representacion no cambia. e) no esta bueno mencionar Optimizar() en los servicios exportados porque atas el tipo diseñado a su estructura interna (la cual es privada y misteriosa).
Ejercicio 2[editar]
Daban SSort, ISort, QSort y MergeSort y tenias que: Complejidad temporal en caso promedio Complejidad temporal en peor caso Si necesita memoria adicional Si el algoritmo acepta, luego de detenerlo, meter nuevos elementos al array y arrancar de nuevo.
Ejercicio 3[editar]
Dar pseudo-codigo de Insercion, Borrado y Busqueda en Hashing Dinamico Extensible.
Ejercicio 4[editar]
Daban 5 errores comunes en los TADS y habia que explicar cual era su consecuencia en el diseño. No recuerdo todos, pero algunos eran:
- Incongruencia
- Inconsistencia (contradiccion logica)
- Axiomatizacion muy complicada
- Sub Especificacion
- Se usan muchos cuantificadores en la axiomatizacion
Tambien habia que decir cual era el error menos grave.
Ejercicio 5[editar]
Que parte del metodo de folding/unfolding es el que importa al querer hacer mas eficientes los calculos de una funcion?
