Cambios

Saltar a: navegación, buscar

Final del 21/02/13 (Algoritmos III)

1552 bytes añadidos, 05:28 23 feb 2013
Página creada con «{{Back|Algoritmos y Estructuras de Datos III}} == Ejercicio 1 == Dado un conjunto Sn {a1, a2, ... ,an} de naturales, se quiere saber cual es el largo de la secuencia creci...»
{{Back|Algoritmos y Estructuras de Datos III}}

== Ejercicio 1 ==
Dado un conjunto Sn {a1, a2, ... ,an} de naturales, se quiere saber
cual es el largo de la secuencia creciente más larga. Desarrollar un algoritmo utilizando programación dinámica. Cuál es su complejidad?
Cómo hay que modificar al algoritmo si queremos que además devuelva la secuencia?

== Ejercicio 2 ==
Sea G un grafo y T un AGM de G.
a) Probar que si e arista de G no pertenece a G, entonces e es una de las aristas más pesadas del circuito al que pertenece.
b) Probar que si e es puente en G pertenece a T
c) Si T es AGM de G y e no pertenece a T, es T un AGM de G\{e} ? Todo árbol mínimo de G\{e} es AGM de T?

== Ejercicio 3 ==
Sea G conexo y completo Kn con n>=3 con pesos en los ejes y no dirigido. Decir si es cierto lo siguiente y justificar la respuesta:
a) Si un cto hamiltoniano mínimo de G contiene a un camino hamiltoniano mínimo. Es el camino igual al cto pero sin su arista más pesada?
b) Algún cto hamiltoniano mínimo contiene a un camino mínimo hamiltoniano?
c) Todo cto hamiltoniano mínimo contiene a un camino hamiltoniano mínimo?
d) Repetir a, b, c pero sabiendo que los pesos de los ejes cumplen con la desigualdad triangular

== Ejercicio 4 ==
Que obtenemos si cortamos en la iteración k al algotirmo de dijkstra?

== Ejercicio 5 ==
a) Enunciar el teorema de Cook y dar su importancia.
b) Si P = NP, podemos decir que P = Np-Hard?
c) Cuál es la ventaja de saber si un problema es Np-completo o np-hard en la práctica?

[[Category:Finales]]
Usuario anónimo

Menú de navegación