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

De Cuba-Wiki
(Final de Algoritmos del 6/3/08)
 
 
(No se muestran 4 ediciones intermedias de otro 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 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.<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 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 ==
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 ==
Incongruencia
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:
Inconsistencia
* Incongruencia
SobreEspecificacion
* Inconsistencia (contradiccion logica)
SubEspecificacion
* Axiomatizacion muy complicada
* Sub Especificacion
* Se usan muchos cuantificadores en la axiomatizacion


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 actual - 19:38 24 feb 2009

Plantilla:Back

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?

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Final_2/2C/2008_(Algoritmos_II)&oldid=6299»