1158063 Programación matemática
1151032 Temas selectos de Ingeniería en Computación
I
Trimestre 2012 Otoño
Instructores: Dra. Laura
Elena Chávez Lomelí, Dr. Rafael López Bracho,
Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso:
lunes 10 de septiembre a jueves 29 de noviembre de 2012.
Grupos: CPMOPT01 y CSI02
(lunes, miércoles y viernes de 11:30 a 13:00).
Asesorías: En la
oficinas H-150, H-251 y H-264.
Salón: G206.
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.
- Introducción a la optimización [RL].
- Introducción a la modelación [FZ].
- Programación no lineal [LC].
- Programación lineal [RL].
- Programación entera [RL].
- Optimización en redes [LC].
- Programación dinámica [FZ].
Evaluación
Habrá seis evaluaciones. Cada evaluación valdrá
20 puntos (tema 2) o 16 puntos (temas 3 a 7). 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.
- 10/09:
Presentación del curso y de las reglas de
evaluación. Introducción a la optimización
[RL].
- 12/09:
Introducción a la modelación: Variables,
función objetivo y restricciones [FZ].
- 14/09:
Introducción a la modelación: Dos formulaciones
del problema del agente viajero [FZ].
- 17/09: Introducción a la modelación: Otras
formulaciones del problema del agente viajero [FZ]. Evaluación del tema 2.
- 19/09: Introducción a la modelación:
Formulaciones para problemas de cartero [FZ].
- 21/09: Introducción a la modelación:
Formulaciones para problemas de cartero [FZ].
- 24/09:
Programación no lineal [LC].
- 26/09:
Programación no lineal [LC].
- 28/09: Programación no lineal
[LC].
- 01/10: Programación lineal [RL].
- 03/10:
Programación lineal [RL].
- 05/10: Programación lineal [RL].
- 08/10: Programación
lineal [RL].
- 10/10:
Programación lineal [RL]. Evaluación del
tema 4.
- 12/10:
Día feriado.
- 15/10: Programación entera [RL].
- 17/10:
Programación entera [RL].
- 19/10: Programación entera
[RL].
- 22/10: Programación entera
[RL].
- 24/10:
Programación entera [RL].
- 26/10:
Programación entera [RL]. Evaluación del
tema 5.
- 29/10: Optimización en redes [LC].
- 31/10: Optimización en redes [LC].
- 02/11: Día feriado.
- 05/11:
Optimización en redes [LC].
- 07/11:
Optimización en redes [LC].
- 09/11:
Optimización en redes [LC].
- 12/11: No habrá clase.
- 14/11: Programación dinámica: Recursión,
memoización y programación dinámica [FZ].
- 16/11: Asistir al Taller
de teoría de la computación a la UNAM.
- 19/11:
Programación dinámica: Subsecuencia creciente
(común) más larga [FZ].
- 21/11:
Programación dinámica: Producto encadenado de
matrices [FZ].
- 23/11:
Programación dinámica: Problema del agente viajero
[FZ]. Evaluación del tema 6.
- 26/11: No habrá clase.
- 28/11: Fin del curso.
Bibliografía
- Peter J. Cameron. (1995). Combinatorics: Topics, Techniques,
Algorithms. Ed. Cambridge University Press.
- Chen, D. S., Batson, R. G. y Dang, Y., Applied Integer
Programming: Modeling and Solution, Wiley, Hoboken, New Jersey,
2010.
- Joseph G. Ecker, Michael Kupferschmid. (2004). Introduction to
Operations Research. Ed. Krieger Publishing Company.Graduate
Texts in Mathematics. Modern Graph Theory. Ed. Springer.
- Michael Jünger, Thomas M. Liebling, Denis Naddef, George
L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni
Rinaldi, Laurence A. Wolsey. (Editores). (2010). 50 Years of
Integer Programming 1958-2008. Ed. Springer.
- Jiří Matoušek, Jaroslav Nes̆etřil. (2008). An
Invitation to Discrete Mathematics. Ed. Oxford University Press,
USA.
- Murty, K.G., Optimization for Decision Making: Linear and
Quadratic Models, Springer, New York, 2010.
- Papadimitriou, C. H. y K. Steiglitz, Combinatorial
Optimization: Algorithms and Complexity, Prentice Hall,
Englewood Cliffs, New Jersey, 1982.