Final 2/2C/2007 (Algoritmos II)
Plantilla:Back 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: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n * (n-1) / 2} 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle O(n^3)} ?
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?