1151061 Complejidad Computacional
Trimestre 2015 Primavera
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 4 de mayo a viernes 17 de julio de 2015.
Grupo: CSI01 (martes y
jueves de 10:00 a 11:30).
Asesorías: lunes a viernes
de 9:00 a 10:00 en la oficina H-264.
Salón: E306.
Cupo: 30 alumnos.
Contenido
Se cubrirá el contenido
oficial del curso (el cual se detalla abajo). Es posible que
el temario se cubra en un orden distinto al allí mencionado.
- Problemas, instancias, algoritmos y complejidad.
- Problemas de decisión: las clases P y NP.
- Reducciones polinomiales y completitud NP.
- El teorema de Cook.
- Problemas NP completos.
- Algunas técnicas para demostrar completitud NP.
- Problemas NP duros.
- La jerarquía polinomial.
- Aplicaciones de complejidad al análisis de problemas.
Evaluación
Habrá exámenes, exposiciones en clase y tareas. No habrá examen
global. 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.
Recuerden que, de acuerdo al Reglamento de
Alumnos de la UAM, es falta de los alumnos en contra de la
Institución el suplantar o permitir ser suplantado en la realización
de actividades académicas (Artículo 9) y se impondrá desde
amonestación escrita hasta suspensión por dos trimestres (Artículo
13).
Calendario
El calendario de clases, de entrega de tareas y de evaluaciones que
muestro abajo es tentativo e irá apareciendo paulatinamente.
05/05:
Día feriado.
07/05:
Inicio del curso. Presentación del curso y de las reglas de
evaluación.
12/05: Problemas,
instancias, algoritmos y complejidad.
14/05: Problemas, instancias,
algoritmos y complejidad.
19/05:
Problemas de decisión: las clases P y NP.
21/05:
Problemas de decisión: las clases P y NP.
26/05: No hubo
clase por causas de fuerza mayor.
28/05: No hubo
clase por causas de fuerza mayor.
02/06:
Reducciones polinomiales y completitud NP.
04/06:
Reducciones polinomiales y completitud NP.
09/06: El teorema de Cook.
11/06: El teorema de Cook.
16/06:
Problemas NP completos.
18/06:
Problemas NP completos.
23/06: Algunas técnicas para
demostrar completitud NP.
25/06: Algunas técnicas para
demostrar completitud NP.
30/06:
Problemas NP duros .
02/07:
Problemas NP duros.
07/07: La jerarquía polinomial.
09/07: Aplicaciones de complejidad al
análisis de problemas.
14/07:
Conjunto dominante [César Hernández], 3-coloración de gráficas
[Leopoldo Picasso], árboles de Steiner [César Córdova].
16/07:
Camino más largo [Franck Cortés], faltan los otros dos (los seis
deben estar presentes en todas las presentaciones).
21/07: Fin del curso.
Bibliografía
- Arora y Barak. Computational
complexity: A modern approach. Cambridge University Press.
- Garey y Johnson. Computers and intractability: A guide to the
theory of NP-completeness. W. H. Freeman.
- Papadimitriou.
Computational complexity. Addison-Wesley.