Final del 22/12/14 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

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