Diferencia entre revisiones de «Final 13/12/2016 (Algoritmos II)»

De Cuba-Wiki
m (Agrega el template back)
m (Arregla formateo)
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 O(1)
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 O( min{ n + m, m log(n) })


== Ejercicio 2 ==
== Ejercicio 2 ==
Línea 13: Línea 13:
== 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.
a) T(N)= 4 T(N/2) + 3 N^2
a) T(N)= 4 T(N/2) + 3 N^2
b) T(N)= 16 T(N/4) + (N^2)/log(N)
 
c) T(N)= 2^N T(N/8) + 1
b) T(N)= 16 T(N/4) + (N^2)/log(N)
d) T(N)= 3 T(N/2) + N^2 log(n)
 
e) T(N) = 16 T(N/2) + F(N) log(n)
c) T(N)= 2^N T(N/8) + 1
 
d) T(N)= 3 T(N/2) + N^2 log(n)
 
e) T(N) = 16 T(N/2) + F(N) log(n)
donde F(N)= N^3 (si n par) N^2 (sino)
donde F(N)= N^3 (si n par) N^2 (sino)
f) T(N) = 3 T(N/2) + F(N)
 
f) T(N) = 3 T(N/2) + F(N)
donde F(N)= N^3 (si n par) N^2 (sino)
donde F(N)= N^3 (si n par) N^2 (sino)


== Ejercicio 4 ==
== Ejercicio 4 ==
Se brinda un TAD Conjunto especificado con los siguientes cambios significativos:
Se brinda un TAD Conjunto especificado con los siguientes cambios significativos:
Obs:
Obs:
   secu()
   secu()


Igualdad Observacional:
Igualdad Observacional:
  c =obs c' <=> secu(c) =obs secu(c')
c =obs c' <=> secu(c) =obs secu(c')
   
   
Otras Operaciones:
Otras Operaciones:
Línea 37: Línea 42:




A) Explicar si está o no bien especificado, y si es correcto respecto a la especificación de la cátedra.
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?
B) suponer correcto. ¿Qué aspectos te parecen mejores o peores?


C) Justificar si puede demostrar esto:
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())...))
  Ag(n, Ag(n_1, ... ( Ag(n_k, vacío())...)) =obs Ag(m, Ag(m_1, ... ( Ag(m_k, vacío())...))
  <=>  
  <=>  
Línea 48: Línea 53:
Donde Add es el generador que reemplaza el comportamiento de Ag en la nueva especificación.
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())...)))
D)
DameUno(Ag(n, Ag(n_1, ... ( Ag(n_k, vacío())...))) =obs oneOff(Add(n, Ag(n_1, ... ( Add(n_k, vacío())...)))


[[Categoría: Finales]]
[[Categoría: Finales]]

Revisión del 17:53 19 sep 2017

Plantilla:Back

Ejercicio 1

Se pide construir una doble cola de prioridad que satisfaga: a) min y max en O(1) b) desencolar min y max en log(n) c) borrar min, borrar max en log(n) d) ingresar m elementos en O( min{ n + m, m log(n) })

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.

Ejercicio 3

Analizar los siguientes peores casos. Si se puede utilizar el teorema maestro, utilizarlo. Justificar. a) T(N)= 4 T(N/2) + 3 N^2

b) T(N)= 16 T(N/4) + (N^2)/log(N)

c) T(N)= 2^N T(N/8) + 1

d) T(N)= 3 T(N/2) + N^2 log(n)

e) T(N) = 16 T(N/2) + F(N) log(n) donde F(N)= N^3 (si n par) N^2 (sino)

f) T(N) = 3 T(N/2) + F(N) donde F(N)= N^3 (si n par) N^2 (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())...)))