Edición de «Final 1C/2011 (Algoritmos II)»

{{Back|Algoritmos y Estructuras de Datos II}}
== Ejercicio 1 ==

Verdadero o Falso, justifique o dé un contraejemplo:

* a. Si f es O(g) y g es Ω(f), f es Θ(g)? 
* b. Si f es O(n), entonces para cualquier entrada f es Ω(n)
* c. Si f es Ω(n), entonces para cualquier entrada f es Θ(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.

[[Category:Finales]]