1151061 Complejidad Computacional
Trimestre 2017 Invierno
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 16 de enero a viernes 31 de marzo de 2017.
Grupo: CSI81 (martes de
14:30 a 17:30).
Asesorías: lunes a viernes
de 11:30 a 13:00 en la oficina H-264.
Salón: E309.
Cupo: 50 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á al menos una exposición en clase y tareas. No habrá examen
terminal. 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.
17/01:
Inicio
del
curso.
Presentación
del
curso
y
de
las
reglas
de
evaluación.
Problemas,
instancias, algoritmos y complejidad.
24/01: Problemas de decisión: las
clases P y NP.
31/01:
Reducciones polinomiales y completitud NP.
07/02: El teorema de Cook.
14/02:
Problemas NP completos.
21/02: Problemas NP completos.
28/02:
Algunas técnicas para demostrar completitud NP.
07/03: Problemas NP duros y la
jerarquía polinomial. NP-Completeness
Columns. Escojan una columna y dos problemas de allí (eviten
estos).
14/03:
Aplicaciones de complejidad al análisis de problemas.
21/03: Día
feriado. Problemas elegidos
y día de exposición.
28/03:
No hubo clase. Usen el tiempo para
preparar su exposición y reporte.
04/04: Exposiciones: comenzaremos a
las 13:00 y terminaremos a las 16:00 en el E309. Todos
deben estar desde las 13:00.
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.