Diferencia entre revisiones de «Final 13/12/2016 (Algoritmos II)»
m (Arregla formateo) |
m (Agrega un math en el ejercicio 2) |
||
| (No se muestran 3 ediciones intermedias del mismo usuario) | |||
| Línea 3: | Línea 3: | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
Se pide construir una doble cola de prioridad que satisfaga: | Se pide construir una doble cola de prioridad que satisfaga: | ||
a) min y max en O(1) | |||
a) min y max en <math>O(1)</math> | |||
b) desencolar min y max en log(n) | b) desencolar min y max en log(n) | ||
c) borrar min, borrar max en log(n) | c) borrar min, borrar max en log(n) | ||
d) ingresar m elementos en O( min{ n + m, m log(n) }) | |||
d) ingresar m elementos en <math>O( min\{ n + m, m *log(n) \})</math> | |||
== Ejercicio 2 == | == Ejercicio 2 == | ||
Explicar la interfaz y estructura de representación de un modulo que implemente el TAD conjunto ordenado. Proveer las funciones necesarias para garantizar todas las cosas necesarias en tiempo eficiente. Insertar, buscar y borrar en O(log(n)). Recorrer de forma iterativa todo en tiempo lineal. No olvidar conceptos de aliasing y de argumentos. | Explicar la interfaz y estructura de representación de un modulo que implemente el TAD conjunto ordenado. Proveer las funciones necesarias para garantizar todas las cosas necesarias en tiempo eficiente. Insertar, buscar y borrar en <math>O(log(n))</math>. Recorrer de forma iterativa todo en tiempo lineal. No olvidar conceptos de aliasing y de argumentos. | ||
== Ejercicio 3 == | == Ejercicio 3 == | ||
Analizar los siguientes peores casos. Si se puede utilizar el teorema maestro, utilizarlo. Justificar. | Analizar los siguientes peores casos. Si se puede utilizar el teorema maestro, utilizarlo. Justificar. | ||
b) T(N)= 16 T(N/4) + (N^2)/log(N) | a) <math>T(N)= 4 T(N/2) + 3 N^2</math> | ||
b) <math>T(N)= 16 T(N/4) + (N^2)/log(N)</math> | |||
c) T(N)= 2^N T(N/8) + 1 | c) <math>T(N)= 2^N T(N/8) + 1</math> | ||
d) T(N)= 3 T(N/2) + N^2 log(n) | d) <math>T(N)= 3 T(N/2) + N^2 log(n)</math> | ||
e) T(N) = 16 T(N/2) + F(N) log(n) | e) <math>T(N) = 16 T(N/2) + F(N) log(n)</math> | ||
donde F(N)= N^3 (si n par) N^2 (sino) | donde <math>F(N)= N^3</math> (si n par) <math>N^2</math> (sino) | ||
f) T(N) = 3 T(N/2) + F(N) | f) <math>T(N) = 3 T(N/2) + F(N)</math> | ||
donde F(N)= N^3 (si n par) N^2 (sino) | donde <math>F(N)= N^3</math> (si n par) <math>N^2</math> (sino) | ||
== Ejercicio 4 == | == Ejercicio 4 == | ||
Revisión actual - 18:11 19 sep 2017
Ejercicio 1
Se pide construir una doble cola de prioridad que satisfaga:
a) min y max en
b) desencolar min y max en log(n)
c) borrar min, borrar max en log(n)
d) ingresar m elementos en
Ejercicio 2
Explicar la interfaz y estructura de representación de un modulo que implemente el TAD conjunto ordenado. Proveer las funciones necesarias para garantizar todas las cosas necesarias en tiempo eficiente. Insertar, buscar y borrar en . Recorrer de forma iterativa todo en tiempo lineal. No olvidar conceptos de aliasing y de argumentos.
Ejercicio 3
Analizar los siguientes peores casos. Si se puede utilizar el teorema maestro, utilizarlo. Justificar.
a)
b)
c)
d)
e) donde (si n par) (sino)
f) donde (si n par) (sino)
Ejercicio 4
Se brinda un TAD Conjunto especificado con los siguientes cambios significativos:
Obs: secu()
Igualdad Observacional:
c =obs c' <=> secu(c) =obs secu(c')
Otras Operaciones:
oneOff(c) = prim(secu(c))
Axiomas:
esPermutacion(c,secu(c))= true // axiomatizacion de Secu() es
A) Explicar si está o no bien especificado, y si es correcto respecto a la especificación de la cátedra.
B) suponer correcto. ¿Qué aspectos te parecen mejores o peores?
C) Justificar si puede demostrar esto:
Ag(n, Ag(n_1, ... ( Ag(n_k, vacío())...)) =obs Ag(m, Ag(m_1, ... ( Ag(m_k, vacío())...)) <=> Add(n, Ag(n_1, ... ( Add(n_k, vacío())...)) =obs Add(m, Add(m_1, ... ( Add(m_k, vacío())...))
Donde Add es el generador que reemplaza el comportamiento de Ag en la nueva especificación.
D)
DameUno(Ag(n, Ag(n_1, ... ( Ag(n_k, vacío())...))) =obs oneOff(Add(n, Ag(n_1, ... ( Add(n_k, vacío())...)))
