1151061 Complejidad Computacional
Trimestre 2014 Invierno
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 6 de enero a jueves 20 de marzo 2014.
Grupo: CSI81 (jueves de
14:30 a 17:30).
Asesorías: lunes a viernes
de 9:00 a 10:00 en la oficina H-264.
Salón: G206.
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á una exposición en clase y una tarea. 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.
09/01:
Inicio
del
curso.
Presentación
del
curso
y
de
las
reglas
de
evaluación.
Problemas,
instancias, algoritmos y complejidad.
16/01: Problemas de decisión: las
clases P y NP.
23/01:
Reducciones polinomiales y completitud NP.
30/01: El teorema de Cook.
06/02:
Problemas NP completos.
13/02: Problemas NP completos.
20/02:
Problemas NP completos.
27/02: Algunas técnicas para
demostrar completitud NP.
06/03:
Problemas NP duros y la jerarquía polinomial.
13/03: Estaré en un congreso.
20/03:
Aplicaciones de complejidad al análisis de problemas.
25/03: Exposiciones y entrega de
la tarea.
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.