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: |
José Soto |
Estudiantes
Aquí se colocará la lista de estudiantes inscritos.
Horario
3,0 hrs. |
Cátedras |
2.2, 3.2 y 4.2 |
1,5 hrs. |
Auxiliares |
4.4 |
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: Sábado 16 de Abril
- Control 2: Sábado 14 de Mayo
- Control 3: Sábado 18 de Junio
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 colocarán los enunciados, pautas y
estadísticas de notas de los controles del curso:
- Control 1:
[Postcript, PDF],
[Postcript, PDF]
- Control 2: Enunciado
[Postcript, PDF],
[Postcript, PDF]
- Control 3: Enunciado
[Postcript, PDF],
[Postcript, PDF]
- Examen: Enunciado
[Postcript, PDF],
[Postcript, PDF]
A continuacián se encuentra el material distribuido en el curso:
Material de interés
- Apuntes: Complexity of algorithms, por
Peter Gács y Lászlo Lovász, 1999.
- Apuntes:
Notación asintótica, por M.K.
- Apuntes:
Random Access Machines, por M.K.
- Lectura (sugerida): On computable numbers, with an application
to the Entscheidungsproblem,
por Alan Turing, Proceedings of the London Mathematical Society,
(Ser. 2, Vol. 42, 1937)
- Lectura (sugerida): 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.
- Lectura (sugerida): Reducibility among
Combinatorial Problems, por Richard Karp.
En R. E. Miller y J. W. Thatcher, editores,
Complexity of computer computation, 85-103. Plenum, 1972.
- 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.
- 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
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 que tendrán lugar
este año:
- STOC
- FOCS
- Complexity
- STACS
- ICALP
- MFCS
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 (?).
- Departamento de Ciencias de la Computación, U. Chile,
Fundamentos de la Ciencia de
la Computación.
- Madhu Sudan, MIT,
Advanced
Complexity Theory, 2003 (avanzado)
- Dan Spielman, MIT,
Advanced
Complexity Theory, 2001 (avanzado)
- 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 Julio de 2005.