1158070 Optimización en redes
1151032 Temas selectos de Ingeniería en Computación I
Trimestre 2013 Invierno
Instructores: Dra. Laura
Elena Chávez Lomelí, Dr. Rafael López Bracho, Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 14 de enero a martes 2 de abril de 2013.
Grupos: CPMOPT01 y CSI01
(lunes, miércoles y viernes de 10:00 a 11:30).
Asesorías: En la oficinas
H-150, H-251 y H-264.
Salón: E312.
Cupo: 10 alumnos.
Contenido
Se cubrirá el contenido oficial del curso (el cual se detalla
abajo). Los temas serán cubiertos por los diferentes instructores.
- Gráficas, digráficas y redes [FZ].
- Problemas de ruta más corta [FZ].
- Problemas de flujo máximo [RL].
- Problemas de flujo de costo mínimo [RL].
- Problemas de acoplamientos [LC].
- Problemas de ruteo [FZ].
Evaluación
Habrá cinco evaluaciones. Cada evaluación valdrá 20 puntos. Se
requiere obtener
- al menos 60 puntos para acreditar con S,
- al menos 73 puntos para acreditar con B y
- al menos 87 puntos para acreditar con MB.
Calendario
El calendario de clases, de entrega de tareas y de evaluaciones que
mostramos abajo es tentativo e irá apareciendo paulatinamente.
- 14/01:
Presentación del curso y de las reglas de evaluación. Gráficas,
digráficas y redes [FZ].
- 16/01: Problemas
de ruta más corta [FZ]: Costos unitarios.
- 18/01: Problemas
de ruta más corta [FZ]: Costos no negativos.
- 21/01: Problemas de ruta más corta [FZ]: Costos arbitrarios
sin ciclos negativos.
- 23/01: Problemas de ruta más corta [FZ]: Costos arbitrarios.
- 25/01: No hubo clase por causas de fuerza mayor. Evaluación de los temas 1 y 2.
- 28/01: Problemas
de flujo máximo [RL].
- 30/01: Problemas
de flujo máximo [RL].
- 01/02: Problemas de flujo máximo
[RL].
- 04/02: No hubo clase por causas de fuerza mayor.
- 06/02: Problemas de
flujo de costo mínimo [RL].
- 08/02: Problemas de flujo de costo mínimo [RL].
- 11/02: Problemas de flujo
de costo mínimo [RL].
- 13/02: Problemas
de flujo de costo mínimo [RL].
- 15/02: Problemas
de flujo de costo mínimo [RL].
- 18/02: Problemas de acoplamientos [LC].
- 20/02: Problemas
de acoplamientos [LC].
- 22/02: Problemas de acoplamientos
[LC].
- 25/02: Problemas de acoplamientos
[LC].
- 27/02: Problemas
de acoplamientos [LC].
- 01/03: Problemas
de acoplamientos [LC].
- 04/03: Día feriado.
- 06/03: Coloquio.
- 08/03: Coloquio.
- 11/03: Problemas
de acoplamientos [LC].
- 13/03: Problemas
de acoplamientos [LC].
- 15/03: Problemas
de acoplamientos [LC].
- 18/03: Problemas de ruteo [FZ]: Problemas de cartero en
gráficas no dirigidas.
- 20/03: Problemas de ruteo [FZ]: Problemas de cartero en
gráficas dirigidas
- 22/03: No habrá clase por causas de
fuerza mayor.
- 25/03: Problemas
de ruteo [FZ]: Problemas de cartero en gráficas con viento.
- 27/03: Problemas
de ruteo [FZ]: Problemas de cartero en gráficas mixtas. Evaluación del tema 6.
- 29/03: Día
feriado.
- 01/04: Fin del curso.
Bibliografía
- Ford Jr. L. R., Fulkerson D. R. (2010). Flows in Networks. Ed.
Princeton University Press.
- Hernández Ayuso M. C. (2005). Introducción a la teoría de
redes. Ed. Sociedad Matemática Mexicana.
- Ahuja R. K., Magnanti T. L., Orlin J. B. (1993). Network
Flows: Theory, Algorithms, and Applications. Ed. Prentice Hall.
- Bertsekas D. P. (1991). Linear Network Optimization:
Algorithms and Codes. Ed. The MIT Press.
- Vazirani V. V. (2010). Approximation Algorithms. Ed. Springer
Berlin Heidelberg.
- Hochbaum D. (Editor). (1996). Approximation Algorithms for
NP-Hard Problems. Ed. Course Technology.
Problemas de flujo
- Bertsekas D.P. (1998). Network Optimization: Continuous and
Discrete Models, Athena Scientific.
- Cook, W. J., Cunningham, W. H., Pulleyblank, W. R. y
Schrijver, A., Combinatorial Optimization, Wiley, New York,
1998.
- Rockafellar, R. T., Network Flows and Monotropic Optimization,
Wiley, New York, 1984.
Problemas de ruta más corta
- Cook W. J, Cunningham W. H., Pulleyblank W. R., Schrijver A.
(1998). Combinatorial Optimization [Chapter 2]. Wiley.
- Cormen T. H., Leiserson C. E., Rivest R. L. (1999).
Introduction to Algorithms [Chapters 23, 25, 26]. McGrawHill.
- Korte B., Vygen J. (2006). Combinatorial Optimization: Theory
and Algorithms [Chapter 7]. Springer.
- Motwani R., Raghavan P. (2006). Randomized Algorithms [Chapter
10]. Cambridge.
- Schrijver A. (2003). Combinatorial Optimization [Chapters 6,
7, 8]. Springer.
Problemas de ruteo
- Cheriyan J., Ravi R. Lecture
Notes on Approximation Algorithms for Network Problems
[Chapters 6, 7].
- Dror M. (2000). Arc Routing: Theory, Solutions, and
Applications. Springer.