Créditos: 9
Objetivos:
Que
el estudiante conozca que tipo de limitaciones intrínsecas
fundamentales hay (en espacio, tiempo, aleatoriedad, etc.) en diversos problemas computacionales.
Que
el estudiante conozca diversos métodos para estudiar la dificultad
intrínseca de diversos problemas computacionales.
Dar los
fundamentos, ejemplos y aplicaciones de la complejidad computacional.
Temario:
- Introducción: Modelos computacionales, Máquinas de Turing, clases
computacionales.
- Complejidad en el tiempo. Clases P y NP.
Problemas NP-Completos.
- Complejidad en el espacio. Clases
PSPACE y NPSPACE. Teorema de Savitch. Clases L y NL. Problemas PSPACE
completos y NL completos.
- Teoremas de jerarquías en tiempo y
en espacio.
-
Temas más
avanzados. Límites del método de diagonalización, algoritmos
aproximados, algoritmos probabilísticos, sistemas de pruebas
interactivas, aplicaciones a la criptografía.
Modalidad del curso y
procedimiento de evaluación.
Se realizarán clases
presenciales para profundizar los temas que los estudiantes deberán
tener leídos (con material previalmente entregado) y de resolución
y discusión de problemas. Se espera que las clases sean
interactivas, con activa participación estudiantil, y basado en las
dudas que puedan surgir en la lectura previa o en los ejercicios
propuestos.
Los estudiantes deberán realizar dos trabajos obligatorios
eliminatorios.
La evaluación final será mediante una única
prueba escrita entre quienes hayan aprobado los obligatorios.
