3.3.3 DMC/Optimización Discreta
Programación entera, flujos en redes, matroides, algoritmos de emparejamiento y teoría de NP-completitud.
Temas:
Core
- Programación lineal entera: ramificación y acotamiento, planos de corte y matrices totalmente unimodulares
- Algoritmos de flujo en redes: caminos más cortos, flujo máximo, flujo de costo mínimo
- Teoría de matroides: conjuntos independientes, algoritmo voraz e intersección de matroides
- Teoría de complejidad: P vs. NP, NP-completitud y reducciones
- Algoritmos de aproximación y esquema de aproximación polinomial (PTAS)
Aprendizaje esperado (Learning Outcomes):
Core:
- Explicar la relación entre las relajaciones de programación lineal y las cotas de programación entera [Familiarizarse]
- Aplicar algoritmos de flujo en redes y de matroides para resolver problemas de optimización combinatoria [Usar]
- Demostrar la NP-completitud de un problema combinatorio mediante reducción polinomial [Evaluar]
Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, basado en el modelo de la Computing Curricula de IEEE-CS/ACM
