Diferencia entre revisiones de «Final del 22/12/14 (Algoritmos III)»
(Final oral 22/12/2014) |
mSin resumen de edición |
||
| (No se muestran 9 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é 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) | 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. | ||
Contribuido por Mariano | Contribuido por Mariano Rean y Petr Romachov | ||
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
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
