Final del 22/12/14 (Algoritmos III)

Este final oral fue combinado de lo que pregunto Paula y por otro lado Marenco, siguieron mas o menos el mismo patron ambos. Empezaron con preguntas de teoria de la complejidad y luego flujo, continuo preguntando sobre que tipos de problemas se conocen que sean resolubles polinomialmente y mientras vas respondiendo va preguntandote sobre como se resuelven y que tipo de algoritmos se conocen para resolverlos.

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, circuito euleriano, hamiltoniano, etc)

Coloreo

Cotas para coloreo, cuáles hay y por qué son malas, demostrar la cota superior "grado máximo + 1" (hacer el algoritmo secuencial de coloreo y acotar por el grado +1 de cada nodo) Qué tipo de problema es coloreo

Circuitos Eulerianos y Hamiltonianos

Qué tipo de problemas son Cómo se verifican Qué tipo de propiedades hay para ambos (Teorema de Euler, Dirac, Ore, etc)

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 Qué algoritmos conocemos Cómo funcionan Corte mínimo y flujo máximo Camino de aumento 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) Cuándo termina el algoritmo A qué clase de complejidad pertenece

Cuales problemas conocemos que sean P

Camino minimo AGM Matching máximo

Algoritmos de AGM

Para que sirve y como funciona prim/kruskal Qué es un AGM Porque prim genera un arbol generador MINIMO? Porque prim genera un arbol

Algoritmos de Camino minimo

Dijkstra, Ford, Floyd, Dantzig (para qué sirven, diferencias y dar el invariante en la k-ésima interación) Contar como funciona dijkstra A qué clase de complejidad pertenece

Algoritmo para matching máximo

Clase de complejidad (P) y cómo se prueba. Nodos saturados, caminos de aumento Cúando termina el algoritmo

Nota: Si mencionas algo extra te hacen indagar sobre ello, es a propio riesgo.

Contribuido por Mariano Rean y Petr Romachov