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

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 cómo 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