1151061 Complejidad Computacional
Trimestre 2016 Invierno
Instructor: Dr. Francisco Javier Zaragoza Martínez.
Inicio y fin del curso:
lunes 18 de enero a miércoles 6 de abril de 2016.
Grupo: CSI01 (lunes y
miércoles de 11:30 a 13:00).
Asesorías: lunes a viernes
de 9:00 a 10:00 en la oficina H-264.
Salón: E309.
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.
18/01:
Inicio del curso. Presentación del curso y de las reglas de
evaluación.
20/01:
Problemas, instancias, algoritmos y complejidad.
25/01: Problemas, instancias, algoritmos y
complejidad.
27/01: No hubo
clase por causas de fuerza mayor.
01/02:
Problemas, instancias, algoritmos y complejidad.
03/02:
Problemas de decisión: las clases P y NP.
08/02: Inicia la primera fase del XIII Concurso de
programación de la UAM.
08/02: Problemas de decisión: las
clases P y NP.
10/02: No hubo
clase por causas de fuerza mayor.
15/02:
Termina la primera fase del XIII Concurso de
programación de la UAM.
15/02:
Reducciones polinomiales y completitud NP.
17/02:
Reducciones polinomiales y completitud NP.
22/02: El teorema de Cook.
24/02: El teorema de Cook.
29/02:
Problemas NP completos.
02/03:
Problemas NP completos.
07/03: Algunas técnicas para
demostrar completitud NP.
09/03: Algunas técnicas para
demostrar completitud NP. Obituario
de David S. Johnson.
14/03:
Problemas NP duros.
16/03:
Problemas NP duros. NP-Completeness
Columns. Escojan una columna y dos problemas de allí.
21/03: Día
feriado.
23/03: Problemas elegidos y día de exposición.
28/03:
Aplicaciones de complejidad al análisis de problemas.
30/03:
Aplicaciones de complejidad al análisis de problemas.
04/04: Aplicaciones de complejidad al
análisis de problemas.
06/04: Aplicaciones de complejidad al
análisis de problemas. Fin del curso.
12/04: Ya entregué el acta, deben
poder ver su calificación el 13/04 en el sistema.
13/04: Los invito a que se inscriban
en el Taller de análisis y diseño de algoritmos (16P, los martes
de 14:30 a 17:30).
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.