Final del 01/03/18 (Algoritmos III)

Final de Paula Zabala.

Fue un final oral, hizo preguntas sobre toda la materia. No preguntó por demostraciones formales, sino las ideas principales.

Lo que sigue es un recopilado de preguntas (y algunas respuestas) de varios alumnos que rindieron, para dar una idea de hacia donde apunta, pero no es una lista exhaustiva así que cuidado: estudien toda la materia.

- ¿Qué es la clase P? ¿Qué es la clase NP?

- ¿Cómo probar que un problema de decisión está en NP? (primero expliqué la definición de NP con una MTND, después por qué eso es equivalente a dar un certificado verificable en tiempo polinomial para una instancia con respuesta SÍ)

- ¿Cómo haría para probar que coloreo está en NP? (doy un coloreo válido, chequeo que no haya vértices adyacentes con el mismo color ni que use más de k colores)

- ¿Qué significa que un problema П esté en NP-C? (que está en NP y es "tanto o más difícil" que cualquier problema en NP, entonces si tengo un algoritmo polinomial para resolver П tengo uno para cualquier otro problema de NP. eso es porque puedo reducir polinomialmente cualquier otro problema de NP a П. Ahí hablé un poco de que SAT es el primer problema que se demostró que es NP completo y la demo dice que se puede llevar cualquier MTND que resuelva un problema genérico a SAT)

- ¿Cómo haría para probar que un problema П en NP está en NP-C sin tener que probar que cualquier problema genérico se reduce a П? (ahí se usa la relación de transitividad de ≤p: si tengo un problema Г que ya sé que es NP-C, probar que Г ≤p П implica que para cualquier otro problema Ф de NP, Ф ≤p П)

- ¿Qué es un flujo en una red? (agarro un grafo dirigido con un nodo fuente s y un nodo sumidero t, le asigno una capacidad mayor a 0 a cada arco, un flujo es una función X -> R>=0 que respeta las capacidades y que el flujo que sale de un vértice es igual al que entra, salvo para s y t. Después dije que el valor del flujo es lo que sale de s menos lo que entra a s)

- ¿Cómo encontrar un flujo máximo? (método de Ford-Fulkerson, empezar con un flujo cualquiera F, buscar un camino de aumento en la red residual, i.e. un camino dirigido P de s a t, definir un flujo F' en la red residual que tenga como valor capacidad(P) y aumentar F con F')

- Nombrar problemas que estén en P, y problemas NP-Completos

- Mencionar las técnicas algoritmicas vistas (Golosa, Dinamica, Backtracking .. ) Explicar alguna

- ¿Cuándo podemos aplicar dinámica? Explicar el principio de optimalidad, dar algún ejemplo

- Explicar AGM. Explicar cómo y por qué funciona Kruskal. ¿Que tipo de algoritmo es?

- Explicar algoritmo de Floyd. Diferencias con Dantzig. ¿Cuando usarias uno o el otro?

- ¿Qué significa que un algoritmo sea pseudopolinomial?

- En general, explicar todos los algoritmos vistos en la materia, podría preguntarte cualquiera (Por ejemplo: Prim, Kruskal, Dijkstra, Floyd, Dantzig, Matching, Ford-Fulkerson, Edmonds-Karp, etc.. cualquiera visto)

- ¿Qué pasa si ya terminé todas las iteraciones de un algoritmo matricial para camino mínimo, agrego un nodo, y quiero saber el camino mínimo de todos pero con el nuevo nodo? ¿Qué podría hacer?

- Probar que viajante de comercio es NP.

- Explicar flujo. Algoritmos, red residual.