Complejidad computacional

Código: MA50B

• Equipo docente (nombres, oficinas, e-mails, etc.)
• Estudiantes
• Horario y salas de clases
• Requisitos
• Objetivos
• Material de interés
• Complejidad computacional y la www

Equipo docente

Estudiantes

Horario

Requisitos

Optimización Combinatorial (MA47A) o Algoritmos y Estructuras de Datos (CC30A).

Objetivos

El objetivo principal del curso es analizar cuales son las limitaciones y capacidades de los procedimientos algorítmicos.

Material de interés

• Anuncios
• Controles y tareas
• Apuntes y lecturas

Anuncios

• Bibliografía.
• Potenciales problemas Control 1:
  • Sipser: 1.34, 1.35, 1.39, 1.42, 1.43, 1.44, 2.26, 2.27, 2.28, 3.10, 3.17.
  • Hopcroft: 3.19, 4.6, 4.19, 6.4(a), 6.8, 7.10, 7.11.
  • Savage: 3.30, 4.58, 4.59, 4.61

Controles y tareas

• Control 1: Enunciado, Pauta
• Control 2: Enunciado, Pauta
• Tarea 1: Tarea 1.
• Control 3: Enunciado, Pauta
• Examen: Enunciado, Pauta

Apuntes y lecturas

• Apuntes: Complexity of algorithms, por Peter Gács y Lászlo Lovász, 1999.
• Apuntes: Notación asintótica, por M.K.
• Lectura (sugerida): Gödel's Proof, por Ernest Nagel y James R. Newman. New York University Press, 1958.
• Lectura (sugerida): The History and Status of the P versus NP Question, por Michael Sipser. En Proceedings of the 24th Annual ACM Symp. on Theory of Computer Science, 603-618, 1992.
• Apuntes: Random Access Machines, por M.K.
• Lectura (sugerida): GO is Polynomial-Space Hard, por David Lichtenstein y Michael Sipser. En J. ACM 27(2):393-401, 1980.
• Lectura (sugerida): E-mail and the unexpected power of interaction, por Lazló Babai. En Proceedings of the IEEE Conference in Computational Complexity, 30-44, 1990.

Complejidad computacional y la www

Algunos puntos de partida para comenzar la busqueda de información que puede ser relevante para este curso son:

• Mathematics --- un buen punto de partida para encontrar información relacionada con matemáticas.
• Computer Science --- un buen punto de partida para encontrar información relacionada con computación
• Algunos grupos de investigación en complejidad computacional:
  • Carnegie Mellon
  • MIT
  • Standford
• Directorio de investigadores en informática teórica
• Principales conferencias en el área que tendrán lugar este año:
  • STOC
  • FOCS
  • Complexity
  • STACS
  • ICALP
  • MFCS
  Conferencias en Teoría de la computación: Calendario
• Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory
• Otros cursos de complejidad computacional
  • Claudio Gutierrez, PUC, Complejidad computacional, 2001 (?).
  • Gonzalo Navarro, U. Chile, Fundamentos de la Ciencia de la Computación, 2002.
  • Madhu Sudan, MIT, Advanced Complexity Theory , 2002 (avanzado)
• Applets ilustrativas
  • Jflap Demmo Applets: Autómatas finito y apiladores, máquinas de Turing, conversión de gramáticas y expresiones regulares.
  • Autómata finito determinista
  • Autómata finito nodeterminista