Final del 02/03/10 (Algoritmos III)

Ejercicio 1

Dado un conjunto de n elementos naturales S = {a1,…, an} y un natural k queremos saber si existe un subconjunto de S cuyos elementos suman k. Diseñar un algoritmo de programación dinámica para resolver este problema. Mostrar la correctitud y determinar la complejidad del algoritmo propuesto.

Ejercicio 2

Decidir si las siguientes frases son Verdaderas o Falsas. Justificar:

(a) G conexo, tiene un único AG sí y solo sí G es un árbol.

(b) Si la arista e es una arista puente de G, entonces e pertenece a todo AG.

(c) Sea G un grafo con pesos en sus aristas. G tiene un único AGM sí y solo sí G es un árbol.

(d) Si G tiene más de un AGM entonces toda arista que pertenece a algún AGM y no pertenece a algún otro AGM, está incluida en un circuito en el cual tiene peso mínimo.

Ejercicio 3

Analizar el siguiente algoritmo para colorear los ejes de un grafo G:

  Dado un grafo G
     Poner k = 0
     Mientras X no sea vacío hacer
        • k = k + 1
        • encontrar un matching máximo M de G
        • para todo e en M poner f(e) = k
        • G = G \ M
  End

a) Demostrar que el algoritmo da un coloreo válido de los ejes de G.

b) Decir si el algoritmo calcula siempre el índice cromático de G correctamente.

c) Sabiendo que existen algoritmos polinomiales de orden O(n3) para determinar un matching máximo determinar la complejidad del algoritmo.

d) ¿Se podría reemplazar encontrar un matching máximo por encontrar un matching maximal?

Ejercicio 4

Sea G un grafo y v un vértice no aislado de G. Demostrar que existe un matching de cardinal máximo en G tal que v es un extremo de un eje perteneciente al matching.

Ejercicio 5

a) ¿Qué es una máquina de Turing no determinística?

b) Enunciar el teorema de Cook y explicar su importancia en la teoría de la complejidad de algoritmos.

c) ¿Es cierto que si se probara que P = NP entonces quedaría probado que todo problema NP-hard está en P?

d) ¿Cuál es la importancia desde el punto de vista práctico (o sea cuando se necesita resolver un problema real) de saber que un problema es NP-Completo o NP-hard?