Final del 19/02/15 (Algoritmos III)

Plantilla:Back El final fue parte oral y parte ejercicios.

Preguntas sobre complejidad

Qué es NP. Qué significa que un problema sea NP. Qué es un problema P. Qué signifca que un problema sea NP-C, cómo se verifica esto. Ejemplos de problemas NP-C, también me empezó a nombrar problemas y preguntaba a qué clase pertenecían (por ejemplo coloreo de vertices, circuito euleriano, hamiltoniano, etc).

Luego pregunto sobre los ejercicios estos que eran de un final del 2010

Ejercicio Complejidad Oral

a) ¿Qué se puede decir de $\Pi _{1}$ sabiendo que existe una reducción polinomial de $\Pi _{1}$ a $\Pi _{2}$ y que $\Pi _{2}\in P$?

b) ¿Qué se puede decir de $\Pi _{1}$ sabiendo que existe una reducción polinomial de $\Pi _{1}$ a $\Pi _{2}$ y que $\Pi _{2}\in NP$ ?

c) ¿Qué se puede decir de $\Pi _{1}$ sabiendo que existe una reducción polinomial de $\Pi _{1}$ a $\Pi _{2}$ y que $\Pi _{2}\in NP-Completo$ ?

d) ¿Qué se puede decir de $\Pi _{2}$ sabiendo que existe una reducción polinomial de $\Pi _{1}$ a $\Pi _{2}$ y que $\Pi _{1}\in NP-Completo$ ?

e) ¿Qué se puede decir de $\Pi _{2}$ sabiendo que existe una reducción polinomial de $\Pi _{1}$ a $\Pi _{2}$ y que $\Pi _{1}\in NP-Completo$ y $\Pi _{2}\in NP$?

Preguntas sobre flujo

Qué es un flujo válido y decir cuál es el valor del flujo en una red que tenía dibujada con un flujo. Dar una iteración de la red residual de Ford Fulkerson (tenía dibujada una red con un flujo y había que armar la red residual, te hace un camino de aumento ahí y hay que mostrar entonces como se mejora el flujo en la red). A qué clase de complejidad pertenece. (P)

Circuitos Hamiltonianos

Qué tipo de problemas son. (NP)

Matching Maximo

Qué tipo de problemas son. (P) Porque se sabe que es P . Teorema Matching Maximo <=> no hay camino en aumento.

Ejercicio 1

a) Si el camino entre i y j tiene más de un camino mínimo ¿Cual elige Floyd?.

b) Adaptarlo para que calcule los caminos mas cortos tal que no pasen por un conjunto de nodos dado.

Ejercicio 2

G=(V,X) es Hamiltoniano entonces para todo $S\in V,S\neq \emptyset$

$W(G-S)\leq |S|$ (W(G) es la cantidad de componentes conexas de G)

a) Dar un ejemplo de que el teorema no es una condición suficiente para asegurar que el grafo es hamiltoniano.

b) Mostrar, usando el teorema, que el grafo de la figura no es hamiltoniano.

Archivo:Grafo.png

Grafo ej. 2