1158039 Temas Selectos III
Trimestre 2005 Primavera
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: Lunes
25 de abril a viernes 8 de julio.
Grupo: CMC01 (horario a
convenir).
Asesorías: Lunes y
miércoles de 13:00 a 14:30 en la
oficina H-264.
Salones: Varios (a convenir).
Laboratorios: Varios (a
convenir).
Contenido
Cuando nos enfrentamos a un problema computacional una de las primeras
preguntas que nos hacemos es si éste es soluble en tiempo
polinomial o no. Con frecuencia la respuesta es "no" ya que se puede
demostrar que el problema es NP duro. Aquí tenemos las
siguientes tres opciones: Podemos ignorar el problema diciendo que es
muy dificil, o podemos diseñar heurísticos (de
los cuales no sabemos si encontrarán la respuesta o no, o cuanto
tiempo se tardarán), o podemos intentar diseñar
algoritmos que siempre encuentren una buena respuesta (aunque no sea la
mejor) en tiempo polinomial. Este curso es acerca de la tercera
opción, es decir, acerca de técnicas de diseño de
"algoritmos de aproximación" para diferentes problemas que
ocurren con frecuencia. Se requieren conocimientos básicos de
complejidad computacional y de programación lineal. Todos los
materiales del curso estarán en inglés. El siguiente
temario es tentativo y se podrá ir adaptando según las
necesidades del curso:
- Introducción a los algoritmos de aproximación.
- Problemas NP duros.
- Algoritmos de aproximación.
- Garantía de aproximación.
- Dureza de aproximación.
- El problema de cubierta por conjuntos.
- Algoritmo glotón.
- Algoritmo de redondeo.
- Algoritmo dual.
- Algoritmo primal-dual.
- El problema de corte máximo.
- Algoritmo de búsqueda local.
- Algoritmo aleatorio.
- Método de esperanzas condicionales.
- Método de espacio muestral pequeño.
Evaluación
El 100% de la calificación corresponderá con la entrega
de tres proyectos acordados entre el instructor y los estudiantes. Para
obtener S se requiere entregar uno de los proyectos, para obtener B se
requiere entregar dos de los proyectos y para obtener MB se requiere
entregar los tres proyectos.
Bibliografía
- Tind, Proceedings of the ISMP 2003, Springer, 2003.
- Vazirani, Approximation Algorithms, Springer, 2001.
- Hochbaum, Approximation Algorithms for NP-hard Problems, ITP,
1997.
- Otros materiales publicados y en línea.
La versión más reciente de esta página se puede
encontrar en http://ce.azc.uam.mx/profesores/franz/tsm/