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.

Profesor: Sergio Rajsbaum

Semestre 2009-2

Semestre 2006-2

Semestre 2005-2

Semestre 1999-2


Contenido de esta página






Objetivo

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



Temario

  1. Introducción y conceptos básicos
    1. Problemas, algoritmos, complejidad. Motivación
    2. Notacion asintótica, codificación, modelos de cómputo
  2. La Teoría de NP-completez
    1. Máquinas de Turing y la clase P
    2. La clase NP
    3. Relación entre P y NP, transformaciones polinomiales
    4. Definición de NP-completez
    5. Teorema de Cook
  3. Demostraciones de Problemas NP-completos
    1. Problemas básicos: 3SAT, Apareamientos, Cubierta de vértices, circuito hamiltoniano, clan, partición
    2. Técnicas: restricción, reemplazo local, diseño de componentes
  4. Temas selectos (dependiendo del tiempo que quede)
    1. Problemas no computables y máquinas de Turing universales
    2. Usando NP-completez para analizar problemas
    3. Enfrentando problemas NP-completos
    4. Otras clases de complejidad
    5. Otros modelos de cómputo: DNA, paralelos, distribuidos, cuánticos, etc.

Regresar a Contenido



Bibliografía

Textos

  1. Michael Garey , David Johnson , "Computers and Intractability- a guide to the theory of NP-completeness", Freeman and Company, 1979
  2. Michael Sipser , Introduction to the Theory of Computation , PWS Publishing Company, 1997. 2nd Ed 2005.
  3. Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach", online draft, Textbook by Cambridge University Press, 2009.
  4. Dexter C. Kozen, "Theory of Computation," Springer, 2006.
Complementarios
  1. 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
  2. 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"
  3. 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"
  4. Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  5. Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
  6. Dexter C. Kozen, Automata and Computability, Springer, 1997.
  7. 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
  8. Nigel Cutland, Computability: An Introduction to Recursive Function Theory,  Cambridge University Press, 1980.

Blogs

Películas

Lecturas

Otras referencias


Regresar a Contenido



Ligas a sitios de interés y material de apoyo


Artículos de interés

Regresar a Contenido



Cursos relacionados

Regresar a Contenido



Herramientas

Regresar a Contenido



Forma de trabajo

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