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

De Cuba-Wiki
m (Agrega categoría Finales)
m (Agrega un math en el ejercicio 2)
 
(No se muestran 5 ediciones intermedias del mismo usuario)
Línea 1: Línea 1:
{{back|Algoritmos_y_Estructuras_de_Datos_II}}
== 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)
 
b) desencolar min y max en log(n)
a) min y max en <math>O(1)</math>
c) borrar min, borrar max en log(n)
 
d) ingresar m elementos en O( min{ n + m, m log(n) })
b) desencolar min y max en log(n)
 
c) borrar min, borrar max en 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.
a) T(N)= 4 T(N/2) + 3 N^2
 
b) T(N)= 16 T(N/4) + (N^2)/log(N)
a) <math>T(N)= 4 T(N/2) + 3 N^2</math>
c) T(N)= 2^N T(N/8) + 1
 
d) T(N)= 3 T(N/2) + N^2 log(n)
b) <math>T(N)= 16 T(N/4) + (N^2)/log(N)</math>
e) T(N) = 16 T(N/2) + F(N) log(n)
 
donde F(N)= N^3 (si n par) N^2 (sino)
c) <math>T(N)= 2^N T(N/8) + 1</math>
f) T(N) = 3 T(N/2) + F(N)
 
donde F(N)= N^3 (si n par) N^2 (sino)
d) <math>T(N)= 3 T(N/2) + N^2 log(n)</math>
 
e) <math>T(N) = 16 T(N/2) + F(N) log(n)</math>
donde <math>F(N)= N^3</math> (si n par) <math>N^2</math> (sino)
 
f) <math>T(N) = 3 T(N/2) + F(N)</math>
donde <math>F(N)= N^3</math> (si n par) <math>N^2</math> (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 35: Línea 47:




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 46: Línea 58:
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 actual - 18:11 19 sep 2017

Plantilla:Back

Ejercicio 1[editar]

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[editar]

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[editar]

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[editar]

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