1108023 Temas selectos de Optimización I
Trimestre 2013 Primavera
Instructores: Dr. Crevel
Bautista Santiago y Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 22 de abril a martes 9 de julio de 2013.
Grupos: CPMOPT01 (martes y
jueves de 9:15 a 11:30).
Asesorías: En la oficinas
H-293 y H-264.
Salón: E312.
Cupo: 10 alumnos.
Contenido
Se cubrirá el contenido aprobado del curso (el cual se detalla
abajo). Los temas serán cubiertos por los diferentes instructores.
- Problemas e instancias [FZ].
- Medidas de complejidad computacional [FZ].
- Problemas de decisión y las clases P, NP y NP completo [CB].
- Reducciones polinomiales [CB].
- Otras clases de complejidad para problemas de decisión [CB].
- Problemas de optimización y la clase NPO [FZ].
- Reducciones entre problemas de optimización [FZ].
- Otras clases de complejidad para problemas de optimización
[FZ].
- Problemas abiertos en complejidad computacional [CB/FZ].
Al finalizar el curso el alumno será capaz de reconocer la
complejidad computacional de diversos problemas de optimización
combinatoria y de usar este conocimiento para decidir la forma en
que intentará resolver los problemas que aparezcan en su proyecto
de investigación.
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 exposiciones que
mostramos abajo es tentativo e irá apareciendo paulatinamente.
- 23/04:
Presentación del curso y de las reglas de evaluación. Problemas
e instancias [FZ].
- 25/04: Medidas
de complejidad computacional [FZ].
- 30/04: Problemas de decisión y las clases P, NP y NP completo
[CB].
- 02/05: Problemas de decisión y las clases P, NP y NP completo
[CB].
- 07/05: No habrá
clase por causas de fuerza mayor.
- 09/05: Problemas
de decisión y las clases P, NP y NP completo [CB].
- 14/05: Reducciones polinomiales [CB].
- 16/05: Reducciones
polinomiales [CB].
- 21/05: Otras clases de
complejidad para problemas de decisión [CB].
- 23/05: Otras
clases de complejidad para problemas de decisión [CB].
- 28/05: Exposiciones de los alumnos.
- 30/05:
Exposiciones de los alumnos.
- 04/06: Problemas de optimización y
la clase NPO [FZ].
- 06/06: Algoritmo
de aproximación con garantía logarítmica para cubierta
por conjuntos [FZ].
- 11/06: Asistan a esta plática.
Inviten a sus compañeros y profesores.
- 13/06: Algoritmos de aproximación con garantías logarítmica y
constante para cubierta
por vértices [FZ].
- 18/06: Esquema
de aproximación completamente polinomial para el problema
de la mochila [FZ]. Tarea (para el
09/07).
- 20/06: Esquema
de aproximación asintótico y polinomial para el problema
de empacado [FZ].
- 25/06: Algoritmo de aproximación basado en programación lineal
para cubierta
por conjuntos [FZ].
- 27/06: Algoritmo de aproximación primal-dual para cubierta
por conjuntos [FZ].
- 02/07:
Algoritmos aleatorios de aproximación para corte
máximo [FZ].
- 04/07:
Algoritmos aleatorios de aproximación para satisfacibilidad
[FZ].
- 09/07: Exposiciones de los alumnos [FZ].
Bibliografía
- Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity:
A Modern Approach, Cambridge.
- Cook, Stephen (1983), "An overview of computational
complexity", Commun. ACM (ACM) 26 (6): 400-408.
- Cook, Stephen (April 2000), The P versus NP Problem, Clay
Mathematics Institute, retrieved 2006-10-18.
- Fortnow, Lance; Homer, Steven (2003), "A Short History of
Computational Complexity", Bulletin of the EATCS 80: 95-133.
- Garey, Michael R.; Johnson, David S. (1979), Computers and
Intractability: A Guide to the Theory of NP-Completeness, W. H.
Freeman
- Karp, Richard (1972), "Reducibility Among Combinatorial
Problems", in R. E. Miller and J. W. Thatcher (editors),
Complexity of Computer Computations, New York: Plenum, 85-103.
- Karp, Richard, "Combinatorics, Complexity, and Randomness",
1985 Turing Award Lecture.
- King, James (2004), A survey of 3SUM-hard problems.