Introducción a la Complejidad Computacional
Este curso ha sido impartido en la UNAM
en diversas ocasiones, tanto 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 . El
temario ha ido variando y evolucionando con los años, así
como la bibliografía, que se ha ido actualizando. La
información de esta página es solamente un panorama
general de la intención del curso.
Intoducir al alumno a la Complejidad Computacional,
desde la teoría básica de NP-Completez, hasta temas
más avanzados, dependiendo del foro en el cual se imparta. Dar
herramientas para
que el alumno pueda continuar a cursos más avanzados de
Complejidad y
Teoría de Computación. El objetivo principal es
contribuir a profundizar la formación
del alumno en Computación y en especial en Teoría,
aumentando así
su comprensión de los fundamentos de la Computación que
le serán de utilidad tanto para otras materias teóricas
como para el resto de su formació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
- Otros modelos de cómputo: DNA, paralelos, distribuidos,
cuánticos, etc.
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. 2nd Ed 2005.
- Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern
Approach", online
draft, Textbook by Cambridge University Press, 2009.
- Dexter C. Kozen,
"Theory
of
Computation," Springer, 2006.
Complementarios
- Richard J. Lipton, The P=NP
Question and Gödels Lost Letter, Springer, 2010. "Every
chapter in the book starts with an introduction of a mathematician or
computer scientist, then mentions a personal anecdote or tidbit (that
you will not find anywhere else), then goes on to describe some
fundamental work of the person. This is then followed by Prof. Lipton's
own thoughts and insights into the problem, or some variant of it, some
new results and ideas, and finally the chapter concludes with open
problems. The book really is a gem!" - Amazon. Based on Lipton's Blog
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory,
Languages, and Computation, Addison
Wesley, 2006 (3rd Edition). "The classic textbook on automata and
language theory"
- Christos H. Papadimitriou, Computational
Complexity, Addison
Wesley, 1993. "one of the most widely used textbooks in the field
(together with Sipser's book, which is mor accesible), by one of the
most important computer scientists"
- Sanjeev Arora, Boaz Barak, Computational
Complexity:
A Modern Approach, Cambridge University Press, 2009.
- Oded Goldreich, Computational
Complexity: A Conceptual
Perspective, Cambridge University Press, 2008.
- Dexter C. Kozen, Automata and
Computability, Springer, 1997.
- Hartley Rogers, Theory of
Recursive Functions and Effective Computability, The MIT Press,
1987. "The definitive book on computabilty and recursive function
theory. If you are an undergraduate and are interested in computability
theory, I recommend Nigel's Cutland's book on the subject" - Amazon
- Nigel Cutland, Computability:
An Introduction to Recursive Function Theory, Cambridge
University Press, 1980.
Blogs
Películas
Lecturas
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
Última modificación: febrero 1
, 2005