Diferencia entre revisiones de «Final 1C/2011 (Algoritmos II)»
m (→Ejercicio 3) |
|||
(No se muestra una edición intermedia del mismo usuario) | |||
Línea 2: | Línea 2: | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
Verdadero o Falso, justifique o | 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 == | == Ejercicio 2 == | ||
Línea 18: | Línea 17: | ||
== Ejercicio 3 == | == Ejercicio 3 == | ||
Dada la siguiente especificación sobre una cena con participantes, encuentre los errores y | Dada la siguiente especificación sobre una cena con participantes, encuentre los errores y corríjalos (axiomatice o describa como arreglar el error) | ||
Tad Persona | Tad Persona | ||
Línea 24: | Línea 23: | ||
generadores | generadores | ||
nueva edad | nueva edad × dni → persona | ||
observadores | observadores | ||
. = . persona | . = . persona × persona → bool | ||
Línea 35: | Línea 34: | ||
generadores | generadores | ||
crear conj(personas) | crear conj(personas) → cena | ||
llega_invitado persona | llega_invitado persona × plato x × cena → cena | ||
observadores | observadores | ||
invitados cena | invitados cena → conj(personas) | ||
que_plato_trajo? persona p | que_plato_trajo? persona p × cena c → plato { p ∊ invitados(c) } | ||
suma_de_edades cena | suma_de_edades cena → nat | ||
Tad Regalo es Nat | Tad Regalo es Nat |
Revisión actual - 19:42 30 jul 2014
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 corríjalos (axiomatice o describa como arreglar el error)
Tad Persona
generadores
nueva edad × dni → persona
observadores
. = . persona × persona → bool
Tad Cena
generadores
crear conj(personas) → cena
llega_invitado persona × plato x × cena → cena
observadores
invitados cena → conj(personas)
que_plato_trajo? persona p × cena c → plato { p ∊ 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.