ComplejidadComp Complejidad Computacional

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.