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 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 <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)
 
b) <math>T(N)= 16 T(N/4) + (N^2)/log(N)</math>


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


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


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


f) <math>T(N) = 3 T(N/2) + F(N)</math>
f) T(N) = 3 T(N/2) + F(N)
donde <math>F(N)= N^3</math> (si n par) <math>N^2</math> (sino)
donde F(N)= N^3 (si n par) N^2 (sino)


== Ejercicio 4 ==
== Ejercicio 4 ==
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)»