Final del 22/12/14 (Algoritmos III)
Plantilla:Back Este final oral fue combinado de lo que preguntó Paula y por otro lado Marenco, siguieron más o menos el mismo patrón ambos. Empezaron con preguntas de teoría de la complejidad y luego flujo, continuó preguntando sobre qué tipos de problemas se conocen que sean resolubles polinomialmente y mientras vas respondiendo va preguntándote sobre cómo se resuelven y qué tipo de algoritmos se conocen para resolverlos.
Preguntas sobre complejidad[editar]
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[editar]
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[editar]
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[editar]
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[editar]
Camino mínimo. AGM. Matching máximo.
Algoritmos de AGM[editar]
Para qué sirve y cómo funciona prim/kruskal. Qué es un AGM. Por qué prim genera un árbol generador MÍNIMO?. Por qué prim genera un árbol.
Algoritmos de Camino minimo[editar]
Dijkstra, Ford, Floyd, Dantzig (para qué sirven, diferencias y dar el invariante en la k-ésima interación) Contar cómo funciona dijkstra. A qué clase de complejidad pertenece.
Algoritmo para matching máximo[editar]
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
