Final 2/2C/2007 (Algoritmos II)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Esteban Feuerstein y Fernando Schapachnik

Ejercicio 1[editar]

Explicar las consecuencias en el desarrollo de un software si se tienen en la especificacion los siguientes errores:

  • Funciones inconsistentes
  • Funciones que violan la congruencia
  • Funciones que cumplen con todo pero tienen nombres de una letra
  • Etc.

Ejercicio 2[editar]

Se representa un diccionario con una estructura X y se quiere realizar el diseño repartiendo las tareas entre tres personas A, B y C de manera que:

  • A tiene q hacer la interfaz
  • B tiene que hacer algoritmo de insercion y borrado
  • C tiene que hacer algoritmo de busqueda

¿Cuales son los elementos minimos que hay que darles?

  • TAD Dicc
  • TAD X
  • Func Abs de Dicc
  • Func Abs de X
  • Interfaz modulo X
  • Invariante de Rep Dicc
  • Invariante de Rep. X
  • Etc.

Ejercicio 3[editar]

Se tiene un algoritmo de sorting que realiza exactamente: comparaciones para todo input.

a) Dar la complejidad según O, θ, y Ω.

b) ¿Conoce algun algoritmo que haga exactamente esa cantidad de pasos? ¿y alguno que cumpla con ?

c) Habia que realizar un diagrama de Venn englobando distintas complejidades como O(1), θ (1), O(n), Ω(1), etc.

Ejercicio 4[editar]

Se tiene un arbol binario y se quiere verificar si esta balanceado como un AVL. Dar un algoritmo para resolver este problema y calcular su complejidad. ¿Podria el algoritmo mejorar la eficiencia de los algoritmos de un diccionario?