Diferencia entre revisiones de «Final del 22/12/14 (Algoritmos III)»

De Cuba-Wiki
(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 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.
{{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 ==
Que es NP  
Qué es NP.
Que significa que un problema sea NP  
Qué significa que un problema sea NP.
Que es un problema P  
Qué es un problema P.
Que signifca que un problema sea NP-C, como 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, cuales hay y porque 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).
Que tipo de problema es coloreo
Qué tipo de problema es coloreo.


== Circuitos Eulerianos y Hamiltonianos ==
== Circuitos Eulerianos y Hamiltonianos ==
Que tipo de problemas son
Qué tipo de problemas son.
Como se verifican
Cómo se verifican.
Que 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.
Que algoritmos conocemos  
Qué algoritmos conocemos.
Como funcionan
Cómo funcionan.
Corte minimo y flujo maximo
Corte mínimo y flujo máximo.
Camino de aumento
Camino de aumento.
Dar una iteracion de la red residual de Ford Fulkerson (tenia 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).  
Cuando 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 minimo
Camino mínimo.
AGM
AGM.
Matching máximo
Matching máximo.


== Algoritmos de AGM ==
== Algoritmos de AGM ==
Para que sirve y como funciona prim/kruskal
Para qué sirve y cómo funciona prim/kruskal.
Qué es un AGM  
Qué es un AGM.
Porque prim genera un arbol generador MINIMO?
Por qué prim genera un árbol generador MÍNIMO?.
Porque prim genera un arbol
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 como 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.




Contribuido por Mariano Leo Rean y Petr Romachov
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