Diferencia entre revisiones de «Final del 22/12/14 (Algoritmos III)»
Sin resumen de edición |
|||
| Línea 1: | Línea 1: | ||
Este final oral fue combinado de lo que | 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 == | == Preguntas sobre complejidad == | ||
Qué es NP | Qué es NP. | ||
Qué significa que un problema sea NP | Qué significa que un problema sea NP. | ||
Qué es un problema P | Qué es un problema P. | ||
Qué signifca que un problema sea NP-C, cómo se verifica esto | 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) | 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 == | == 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) | 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 | Qué tipo de problema es coloreo. | ||
== Circuitos Eulerianos y Hamiltonianos == | == Circuitos Eulerianos y Hamiltonianos == | ||
Qué tipo de problemas son | Qué tipo de problemas son. | ||
Cómo se verifican | Cómo se verifican. | ||
Qué tipo de propiedades hay para ambos (Teorema de Euler, Dirac, Ore, etc) | Qué tipo de propiedades hay para ambos (Teorema de Euler, Dirac, Ore, etc). | ||
== Preguntas sobre flujo == | == 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é 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 | Qué algoritmos conocemos. | ||
Cómo funcionan | Cómo funcionan. | ||
Corte mínimo y flujo máximo | Corte mínimo y flujo máximo. | ||
Camino de aumento | 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) | 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 | Cuándo termina el algoritmo. | ||
A qué clase de complejidad pertenece | A qué clase de complejidad pertenece. | ||
== Cuales problemas conocemos que sean P == | == Cuales problemas conocemos que sean P == | ||
Camino mínimo | Camino mínimo. | ||
AGM | AGM. | ||
Matching máximo | Matching máximo. | ||
== Algoritmos de AGM == | == Algoritmos de AGM == | ||
Para qué sirve y cómo funciona prim/kruskal | Para qué sirve y cómo funciona prim/kruskal. | ||
Qué es un AGM | Qué es un AGM. | ||
Por qué prim genera un árbol generador MÍNIMO? | Por qué prim genera un árbol generador MÍNIMO?. | ||
Por qué prim genera un árbol | Por qué prim genera un árbol. | ||
== Algoritmos de Camino minimo == | == Algoritmos de Camino minimo == | ||
Dijkstra, Ford, Floyd, Dantzig (para qué sirven, diferencias y dar el invariante en la k-ésima interación) | Dijkstra, Ford, Floyd, Dantzig (para qué sirven, diferencias y dar el invariante en la k-ésima interación) | ||
Contar cómo funciona dijkstra | Contar cómo funciona dijkstra. | ||
A qué clase de complejidad pertenece | A qué clase de complejidad pertenece. | ||
== Algoritmo para matching máximo == | == Algoritmo para matching máximo == | ||
Clase de complejidad (P) y cómo se prueba. | Clase de complejidad (P) y cómo se prueba. | ||
Nodos saturados, caminos de aumento | Nodos saturados, caminos de aumento. | ||
Cúando termina el algoritmo | Cúando termina el algoritmo. | ||
Nota: Si mencionas algo extra te hacen indagar sobre ello, es a propio riesgo. | Nota: Si mencionas algo extra te hacen indagar sobre ello, es a propio riesgo. | ||
Revisión del 03:55 24 dic 2014
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
