Diferencia entre revisiones de «Final 2/2C/2008 (Algoritmos II)»

De Cuba-Wiki
(Final de Algoritmos del 6/3/08)
 
(No se muestra una edición intermedia del mismo usuario)
Línea 1: Línea 1:
1- Dados dos invariantes I1 e I2, siendo I2 mas fuerte que I1, se pedia:
{{Back|Algoritmos y Estructuras de Datos II}}
Como quedaria el abs si reemplazo a I1 por I2, etc. No recuerdo mas, pero era demasiado dificil de imaginar que querian que pongas aca.


2- Daban SSort, ISort, QSort y MergeSort y tenias que:
== Ejercicio 1 ==
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.<br>
Si se usa Optizar() se pedia
* a)que pre y post tiene la funcion Optimizar
* b)que cambia en la interfaz del diseño
* c)como queda el abs
* d)como queda el invariante
* e)como quedan los servicios exportados.<br><br>
 
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 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 ==
Daban SSort, ISort, QSort y MergeSort y tenias que:
Complejidad temporal en caso promedio
Complejidad temporal en caso promedio
Complejidad temporal en peor caso
Complejidad temporal en peor caso
Línea 8: Línea 19:
Si el algoritmo acepta, luego de detenerlo, meter nuevos elementos al array y arrancar de nuevo.
Si el algoritmo acepta, luego de detenerlo, meter nuevos elementos al array y arrancar de nuevo.


3- Dar pseudo-codigo de Insercion, Borrado y Busqueda en Hashing Dinamico Extensible.
== Ejercicio 3 ==
Dar pseudo-codigo de Insercion, Borrado y Busqueda en Hashing Dinamico Extensible.


4- 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:
== Ejercicio 4 ==
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
Incongruencia
Inconsistencia
Inconsistencia
Línea 18: Línea 31:
Tambien habia que decir cual era el error menos grave.
Tambien habia que decir cual era el error menos grave.


5- Que parte del metodo de folding/unfolding es el que importa al querer hacer mas eficientes los calculos de una funcion?
== Ejercicio 5 ==
Que parte del metodo de folding/unfolding es el que importa al querer hacer mas eficientes los calculos de una funcion?
 
[[Category:Finales]]

Revisión del 06:00 31 mar 2008

Plantilla:Back

Ejercicio 1

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 Optizar() se pedia

  • a)que pre y post tiene la funcion Optimizar
  • b)que cambia en la interfaz del diseño
  • c)como queda el abs
  • d)como queda el invariante
  • 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 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

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

Dar pseudo-codigo de Insercion, Borrado y Busqueda en Hashing Dinamico Extensible.

Ejercicio 4

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 SobreEspecificacion SubEspecificacion

Tambien habia que decir cual era el error menos grave.

Ejercicio 5

Que parte del metodo de folding/unfolding es el que importa al querer hacer mas eficientes los calculos de una funcion?