Semana 16 — Examen final
Esta semana no hay clases regulares ni laboratorio.
Temas del examen
Todo el curso, con énfasis en las semanas 9 a 15:
- Lenguajes decidibles y reconocibles. Diagonalización y el problema de la parada.
- Reducciones, reducción por función y teorema de Rice. PCP y los problemas indecidibles sobre gramáticas.
- Teorema de recursión, incompletitud y complejidad de Kolmogorov.
- Tiempo: P, NP con verificadores y con máquinas no deterministas, coNP.
- Teorema de Cook-Levin y NP-completitud.
- Espacio: Savitch, PSPACE, TQBF y juegos, L y NL.
- Teoremas de jerarquía y BPP.
- De las semanas 1 a 7: saber ubicar un lenguaje en el mapa completo y justificarlo.
Cómo prepararse
- Revisar el formato y los consejos de
exams/README.md. - Rehacer las preguntas de repaso de las guías 9 a 15.
- Dibujar de memoria el mapa de clases, con un lenguaje que separe cada nivel y la técnica que lo demuestra.
- Para cada reducción de los apuntes, escribir primero de qué problema a cuál va y por qué en esa dirección.
- Rehacer las prácticas 3 y 4 sin mirar la solución.