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

De Cuba-Wiki
Sin resumen de edición
m (Reformatea los ejercicios así se vuelven subtítulos)
Línea 1: Línea 1:
1) Se pide construir una doble cola de prioridad que satisfaga:
== Ejercicio 1 ==
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)
Línea 5: Línea 6:
  d) ingresar m elementos en O( min{ n + m, m log(n) })
  d) ingresar m elementos en O( min{ n + m, m log(n) })


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 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.


3) Analizar los siguientes peores casos. Si se puede utilizar el teorema maestro, utilizarlo. Justificar.
== 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
  a) T(N)= 4 T(N/2) + 3 N^2
  b) T(N)= 16 T(N/4) + (N^2)/log(N)
  b) T(N)= 16 T(N/4) + (N^2)/log(N)
Línea 17: Línea 20:
donde F(N)= N^3 (si n par) N^2 (sino)
donde F(N)= N^3 (si n par) N^2 (sino)


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

Revisión del 03:29 16 sep 2017

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())...)))

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Final_13/12/2016_(Algoritmos_II)&oldid=11451»