Introducción a la Complejidad Computacional: NP-Completez
Semestre 1999-2
Curso impartido en la UNAM en la
Licenciatura en Ciencias de la Computación
de la Facultad de Ciencias
y en el Posgrado
en Ciencia e Ingeniería de la Computación .
Lugar: Lunes y Miércoles de 13 a 14:30, salón
de seminarios 3, Instituto de Matemáticas, UNAM
Lista de Correo:npcompleto@uxmcc2.iimas.unam.mx
. Únicamente para alumnos del curso.
Intoducir al alumno a la Complejidad Computacional,
a través de la teoria de NP-Completez. Dar herramientas para
que el alumno pueda continuar a cursos más avanzados de
Complejidad y
Teoría de Computación. Contribuir a la formación
del alumno en Teoría de Computación y a aumentar
su comprensión de los fundamentos de la Computación.
Regresar a Contenido
- Introducción y conceptos básicos
- Problemas, algoritmos, complejidad. Motivación
- Notacion asintótica, codificación, modelos de
cómputo
- La Teoría de NP-completez
- Máquinas de Turing y la clase P
- La clase NP
- Relación entre P y NP, transformaciones polinomiales
- Definición de NP-completez
- Teorema de Cook
- Demostraciones de Problemas NP-completos
- Problemas básicos: 3SAT, Apareamientos, Cubierta de
vértices, circuito hamiltoniano, clan, partición
- Técnicas: restricción, reemplazo local,
diseño de componentes
- Temas selectos (dependiendo del tiempo que quede)
- Problemas no computables y máquinas de Turing universales
- Usando NP-completez para analizar problemas
- Enfrentando problemas NP-completos
- Otras clases de complejidad
Regresar a Contenido
Textos
- Michael Garey
, David Johnson ,
"Computers and Intractability- a guide to
the theory of NP-completeness", Freeman and Company, 1979
- Michael Sipser ,
Introduction
to the Theory of Computation , PWS
Publishing Company, 1997
Otras referencias
Regresar a Contenido
- Useful Theory
Pages This document lists information on WWW pages of
interest to theoretical computer scientists
- Alan Turing Home Page
by A. Hodges
- The
American
Mathematical Society: Turing Machines
- Virtual Turing
Machine (VTM)
- Theory Net Home
Page
- A
compendium
of NP optimization problems Aproximabilidad de problemas NP,
contiene las mejores aproximaciones para cada problema
- Michael
Garey Home Page
- David S. Johnson
Home Page
- Michael Sipser Home
Page
- TSP-BIB
Home Page Liga muy completa con artículos, programas,
reportes técincos, etc.
- TSPLIB
Biblioteca de instancias para el problema TSP en varias versiones y
variantes
- Problemas
NP Completos SAT, Clique, 3SAT, Garph Colouring, Hamiltonian
Circuit, Knapsack y problemas aparentemente similares en P y NP
- Ligas de Computación
Cuántica
- Notas
de Complejidad Computacional escritas por Laszlo Lovasz Pueden
bajarse en formato Postscript. Muy recomendables
- Notas
de Cursos, Compendios y Artículos de Teoría de la
Computación Repositorio de material de alta calidad
disponible en Web. Los autores son reconocidos investigadores y
profesores
Artículos de interés
- G. Brassard, "A quantum jump in CS", Computer Science Today,
Springer 1995
(LNCS 1000), p.1-14. Los modelos de computacíon cuántica
han venido a sacudir suposiciones
acerca de complejidad que se tomaban como muy razonables, ya que,
en teoría, pueden resolver problemas eficientemente, que con los
modelos
usuales de cómputo hoy en día tomaría tiempo
exponencial
- M. Sipser, "The history and status of the P versus NP question",
24th Annual ACM Symposium on the theory of Computing (STOC), Victoria,
Canada, 1992, p. 603-618. Trata de la pregunta P vs NP
Regresar a Contenido
- Models Of
Computation por John E. Savage, Brown University. Curso
básico de fundamentos de la Computación a nivel
licenciatura
- Complexity
and Computability (Curso de Posgrado), por Steve Linton,Division
of Computer Science, University of St. Andrews, North Haugh, St.
Andrews, Fife, KY16 9SS, SCOTLAND
Regresar a Contenido
- D.Knuth, T.Larrabee, P. Roberts, "Mathematical writing",
Mathematical
Association of America, Notes Number 14, Mathematical Association of
America,
1989. Buen libro que describe la manera en que un científico
computacional debe escribir
- S.Krantz, "A primer of mathematical writing: being a disquisition
on
having your ideas recorded, typeset, published, read &
appreciated",
AMS Press 1997. Referencia excelente sobre escritura en
matemáticas, no solo para ciencia de la computación
Regresar a Contenido
El curso se evaluará mediante tareas y un
examen. Las tareas se asignarán aproximadamente cada dos
semanas. La fecha de entraga de las tareas es estricta. Las
tareas pueden entregarse en equipos de dos o individualmente. El examen
se basará en los problemas de las tareas. Las clases de
ejercicios (ayudantías) no serán constantes, se
anunciarán con anticipación en la clase.
Regresar a Contenido
Profesor:
Ayudantes:
- Miguel Angel Rodríguez
Cubículo 2, Instituto de Matemáticas.
Horario de consultas: Martes y Jueves de 16 a 18 hrs.
email: mars@matem.unam.mx
- Ricardo Marcelín
Cubículo 201, Instituto de Matemáticas.
Horario de consultas: Jueves por las mañanas
email: marcelin@matem.unam.mx
Regresar a Contenido
Las tareas estarán disponibles en formatos html y postscript.
- Tarea 1: Prerequisitos html
Postscript
Asignada: enero 27, Entrega: febrero 3
- Tarea 2: Máquinas de Turing html
Postscript
Asignada: febrero 3, Entrega: febrero 10
- Tarea 3: Complejidad y las clases P y NP html
Postscript
Asignada: febrero 10, Entrega: febrero 17
- Tarea 4: NP-Completez html
Postscript
Asignada: febrero 17, Entrega: febrero 24
- Tarea 5: Clases P, NP, NP-Completos, Teorema de Cook html
Postscript
Asignada: febrero 24, Entrega: marzo 3
- Tarea 6: Problemas NP-Completos, Teorema de Cook html
Postscript
Asignada: marzo 3, Entrega: marzo 17
- Tarea 7: Problemas NP-Completos html
Postscript
Asignada: marzo 22, Entrega: abril 12
- Tarea 8: Complejidad de Espacio html
Postscript
Asignada: abril 19 Entrega: abril 28
Regresar a Contenido
Enviar preguntas o sugerencias a:
Miguel Angel
Rodríguez.
Última modificación: abril 23, 1999