Diferencia entre revisiones de «Final del 22/12/14 (Algoritmos III)»
mSin resumen de edición |
|||
| (No se muestran 7 ediciones intermedias de otro usuario) | |||
| Línea 1: | Línea 1: | ||
Este final oral fue combinado de lo que | {{Back|Algoritmos y Estructuras de Datos III}} | ||
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, | 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 == | == 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 == | == 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. | |||
Cómo funcionan. | |||
Corte | Corte mínimo y flujo máximo. | ||
Camino de aumento | Camino de aumento. | ||
Dar una | 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 | A qué clase de complejidad pertenece. | ||
== Cuales problemas conocemos que sean P == | == Cuales problemas conocemos que sean P == | ||
Camino | Camino mínimo. | ||
AGM | AGM. | ||
Matching máximo | Matching máximo. | ||
== Algoritmos de AGM == | == Algoritmos de AGM == | ||
Para | 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. | |||
== 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 | 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 actual - 23:52 27 jul 2015
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[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
