Final del 21/02/13 (Algoritmos 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?