Departamento de Ingeniería Matemática
Complejidad computacional
Código: Ma50b
Esta es la páagina del curso Ma50b, un curso ofrecido por el Departamento de Ingeniería
Matemática de la Facultad de Ciencias
Físicas y Matemáticas de la Universidad de
Chile.
Equipo docente
Cátedra: |
Marcos Kiwi |
Blanco Encalada 2120, 5to Piso, Of. 620, |
Auxiliar: |
Philippe Camacho |
Horario
3,0 hrs. |
Cátedras |
1.2, 4.4 y 5.2 |
1,5 hrs. |
Auxiliares |
4.5 |
4,5 hrs. |
Trabajo personal |
|
10 Unidades.
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.
Fechas relevantes
- Calendarios
- Control 1: Por fijar
- Control 2: Por fijar
- Control 3: Por fijar
Anuncios, controles y pautas
A continuación se encuentran los enunciados, pautas y tareas
de los controles y exámenes de las veces anteriores en que el
Profesor de cátedra ha dictado Ma50b
A continuacián se encuentra el material distribuido en el curso:
Material de interés
- Archivos de JFlap
- Apuntes:
- 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
Existe una gran cantidad de información en la www acerca de teoría
de la complejidad computacional.
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:
- 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:
- Claudio Gutierrez, PUC, Complejidad computacional, 2001 (?).
- Alejandro Hevia, U. Chile,
Fundamentos de la Ciencia de
la Computación.
- 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)
2008
2004
- 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.
Última modificación: 12 de Mayo de 2008.