Departamento de Ingeniería Matemática
Complejidad computacional
Código: Ma5201
Esta es la páagina del curso Ma5201, 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. 516 |
Auxiliar: |
Sebastián Pérez |
Horario
3,0 hrs. |
Cátedras |
2.5, 4.5 |
1,5 hrs. |
Auxiliares |
1.4 |
5,5 hrs. |
Trabajo personal |
|
10 Unidades.
Requisitos
Algoritmos Combinatoriales (Ma3705).
Objetivos
El objetivo principal del curso es analizar cuales son las limitaciones
y capacidades de los procedimientos algorítmicos.
Fechas relevantes
- Calendarios
- Control 1: 23 de Abril
- Control 2: 04 de Junio
- Control 3: 18 de Agosto
Controles y pautas
Material de interés
- 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.
- The Status of the P Versus NP Problem, por Lance Fortnow.
En Communications of the ACM 52(9):78-86, 2009.
- 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:
- Principales conferencias en el área:
- STOC
- FOCS
- Complexity
- STACS
- ICALP
- LATIN
- Special Interest Group on Algorithms and Computation Theory (SIGACT) de la Association for Computing Machinery (ACM).
- Otros cursos de complejidad computacional:
- En castellano
- En inglés
- Jin-Yi Cai, An Introduction to the Theory of Computation, U. of Wisconsin,
2015
- Russell Impagliazzo, U. California, San Diego,
2016
- Sofia Raskhodnikova, U. Pennsilvania, Introduction to the Theory of Computation:2016
- Luca Trevisan, Computability and Complexity, U. California, Berkeley,
2015
- David Steurer, Introduction to the theory of Computing, U. California, Berkeley
2013
- Ryan Williams, Automata and Complexity Theory, Standford U.,
2015
- David Zuckerman, Theory of Computation, U. Texas
2014
- Applets ilustrativas
- Jflap Applet: Autómatas finito y apiladores, máquinas de Turing, conversión de gramáticas y expresiones regulares.
Esta página dejó de ser mantenida el 02 de Septiembre del 2016.