Edición de «Final del 19/02/15 (Algoritmos III)»

{{Back|Algoritmos y Estructuras de Datos III}}
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 5 ==
a) ¿Qué se puede decir de <math>\Pi_1</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_2 \in P </math>?

b) ¿Qué se puede decir de <math>\Pi_1</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_2 \in NP</math> ?

c) ¿Qué se puede decir de <math>\Pi_1</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_2 \in NP-Completo </math> ?

d) ¿Qué se puede decir de <math>\Pi_2</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_1 \in NP-Completo</math> ?

e) ¿Qué se puede decir de <math>\Pi_2</math> sabiendo que existe una reducción polinomial de <math>\Pi_1</math> a <math>\Pi_2</math> y que <math>\Pi_1 \in NP-Completo</math> y <math>\Pi_2 \in NP</math>?

[[Category:Finales]]

== 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 <math>S \in V, S \neq \emptyset</math> 

<math>W(G-S) \leq |S|</math> (''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.


[[Image:Grafo.png|thumb|Grafo ej. 2]]