Complejidad computacional

Código: Ma50b

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

Equipo docente

Horario

Requisitos

Objetivos

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

Fechas relevantes

• Calendarios
• Control 1: Jueves 16 de Abril, 14:30
• Control 2: Jueves 14 de Mayo, 14:30
• Control 3: Jueves 18 de Junio, 14:30

Controles y pautas

Año	Evaluación	Enunciado	Pauta
2002	Control 1	PS	PS
	Control 2	PS	PS
	Control 3	PS	PS
	Examen	PS	PS
2005	Control 1	PDF - PS	PDF - PS
	Control 2	PDF - PS	PDF - PS
	Control 3	PDF - PS	PDF - PS
	Examen	PDF - PS	PDF - PS
2008	Control 1	PDF - PS	PDF - PS
	Control 2	PDF - PS	PDF - PS
	Control 3	PDF - PS	PDF - PS
	Examen	PDF - PS
2009	Control 1	PDF - PS	PDF - PS
	Control 2	PDF - PS	PDF - PS
	Control 3	PDF - PS	PDF - PS
	Examen	PDF - PS

• Bibliografía [.PS, .PDF]

Material de interés

• Archivos de JFlap
• Automata finito no-determinista para búsqueda exacta
• Automata finito no-determinista para búsqueda aproximada
• Automata finito determinista que reconoce números codificados en binario divisibles por 3 (lee de dígito más significativo a menos significativo)
• Máquina de Turing que marca el comienzo de su cienta y desplaza su contenido una celda a la derecha
• Máquina de Turing que hace una copia del contenido inicial de su cinta
• Máquina de Turing que acepta entradas de la forma 0ⁿ1ⁿ
• Máquina de Turing que calcula la multiplicación de dos números en unario (en la entrada 0ⁿ10^m1 entrega como salida 0ⁿ10^m10^nm)
• Máquina de Turing que acepta entradas de la forma 0²ⁿ
• Máquina de Turing que incrementa repetidamente un contador binario
• Apuntes:
• Apuntes para el curso de Fundamentos de la Ciencia de la Computación del Departamento de Ciencias de la Computación, por Gonzalo Navarro. 2006.
• Computational Complexity: A Modern Approach, por Sanjeev Arora y Boaz Barak (Versión web - 2008)
• Computational Complexity: A Conceptual Perspective, por Oded Goldreich (Versión web - 2008)
• Complexity of algorithms, por Peter Gács y Lászlo Lovász, 1999.
• Notación asintótica, por M.K.
• Random Access Machines, por M.K.
• Lecturas sugeridas:
  • On computable numbers, with an application to the Entscheidungsproblem, por Alan Turing, Proceedings of the London Mathematical Society, (Ser. 2, Vol. 42, 1937)
  • Gödel's Proof, por Ernest Nagel y James R. Newman. New York University Press, 1958.
  • Lectura (sugerida): The Complexity of Theorem-Proving Procedures, por Steve Cook. En Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151-158, 1971.
  • Reducibility among Combinatorial Problems, por Richard Karp. En R. E. Miller y J. W. Thatcher, editores, Complexity of computer computation, 85-103. Plenum, 1972.
  • 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.
  • GO is Polynomial-Space Hard, por David Lichtenstein y Michael Sipser. En J. ACM 27(2):393-401, 1980.
  • 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:

• 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:
  • STOC
  • FOCS
  • Complexity
  • STACS
  • ICALP
  • LATIN
  Conferencias en teoría de la computación: Calendario
• Special Interest Group on Algorithms and Computation Theory (SIGACT) de la Association for Computing Machinery (ACM).
• Otros cursos de complejidad computacional:
• Boaz Barak, Princeton, Computational Complexity: 2007, 2009.
• Claudio Gutierrez, PUC, Complejidad computacional, 2001 (?).
• Alejandro Hevia, U. Chile, Fundamentos de la Ciencia de la Computación, 2008.
• Madhu Sudan, MIT, Advanced Complexity Theory (avanzado): 2003, 2005, 2007
• Dan Spielman, MIT, Advanced Complexity Theory, 2001 (avanzado)
• Luca Trevisan, Computational Complexity, U. California, Berkeley (avanzado) 2004 2008
• Luca Trevisan, Computability and Complexity, U. California, Berkeley 2004
• Applets ilustrativas
• Jflap Demmo Applets: Autómatas finito y apiladores, máquinas de Turing, conversión de gramáticas y expresiones regulares.