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 mínimo AGM Matching máximo

Algoritmos de AGM

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

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