Diferencia entre revisiones de «Final 1C/2011 (Algoritmos II)»
m (→Ejercicio 3) |
(Sin diferencias)
|
Revisión del 16:18 10 sep 2013
Ejercicio 1
Verdadero o Falso, justifique o de un contraejemplo:
- a. Si f es O(g) y g es Omega(f), f es Tita(g)?
- b. Si f es O(n), entonces para cualquier entrada f es Omega(n)
- c. Si f es Omega(n), entonces para cualquier entrada f es Tita(n)
- d.
Ejercicio 2
Sea S una secuencia de inserciones sobre un Arbol binario de Busqueda, donde S = { s1, s2, s3, s4, s5, s6, s7} donde s1 <= s2 <= s3 ... <= s7, describir las permutaciones de S que formen lo siguiente
- a. Un arbol de altura minima
- b. Un arbol de altura máxima
Ejercicio 3
Dada la siguiente especificación sobre una cena con participantes, encuentre los errores y corrijalos (axiomatice o describa como arreglar el error)
Tad Persona
generadores
nueva edad x dni -> persona
observadores
. = . persona x persona -> bool
Tad Cena
generadores
crear conj(personas) -> cena
llega_invitado persona x plato x cena -> cena
observadores
invitados cena -> conj(personas)
que_plato_trajo? persona p x cena c -> plato ( p pertenece invitados(c) )
suma_de_edades cena -> nat
Tad Regalo es Nat
Ejercicio 4
Se quiere implementar un diccionario sobre una novedosa estructura x, se quiere dividir el trabajo entre 3 personas de la siguiente manera:
A) Escribe la interfaz B) Escribe algoritmos de inserción y borrado C) Escribe algoritmos de busqueda
Que le daria como minimo de la siguiente lista a cada uno como para que puedan hacer su trabajo, justificar y sea conciso.
TAD Dicc
TAD X
invariante de representacion de dicc sobre x
invariante de repr de x
funcion de abs de x
funcion de abs de diccionario sobre x
interfaz de x
Ejercicio 5
Se quiere implementar conjunto y diccionario cuyas operaciones tipicas sean en orden logaritmico (insertar, borrar, buscar o sus equivalentes). De los siguientes diseños, diga cual usaria y porque, si no le convence ninguna proponga una y justifique
- a. Dicc y Conjunto sobre AVL, AVL sobre punteros a nodos
- b. AVL sobre ABB, ABB sobre AB, AB sobre nodos, Dicc y Conj sobre AVL
- c.
- d.