Edición de «Final 13/12/2016 (Algoritmos II)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
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)
a) min y max en <math>O(1)</math>
b) desencolar min y max en log(n)
 
c) borrar min, borrar max en log(n)
b) desencolar min y max en log(n)
d) ingresar m elementos en O( min{ n + m, m 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 <math>O(log(n))</math>. 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 O(log(n)). 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
a) <math>T(N)= 4 T(N/2) + 3 N^2</math>
b) T(N)= 16 T(N/4) + (N^2)/log(N)
 
c) T(N)= 2^N T(N/8) + 1
b) <math>T(N)= 16 T(N/4) + (N^2)/log(N)</math>
d) T(N)= 3 T(N/2) + N^2 log(n)
 
e) T(N) = 16 T(N/2) + F(N) log(n)
c) <math>T(N)= 2^N T(N/8) + 1</math>
donde F(N)= N^3 (si n par) N^2 (sino)
 
f) T(N) = 3 T(N/2) + F(N)
d) <math>T(N)= 3 T(N/2) + N^2 log(n)</math>
donde F(N)= N^3 (si n par) N^2 (sino)
 
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 47: Línea 35:




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 58: Línea 46:
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)
D) DameUno(Ag(n, Ag(n_1, ... ( Ag(n_k, vacío())...))) =obs oneOff(Add(n, Ag(n_1, ... ( Add(n_k, vacío())...)))
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]]
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Final_13/12/2016_(Algoritmos_II)»