Edición de «Final del 22/12/14 (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
| Revisión actual | Tu texto | ||
| Línea 1: | Línea 1: | ||
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. | |||
Este final oral fue combinado de lo que | |||
== 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. | ||
