Teoría de la Computación
Calendario
Cada semana: una sesión de teoría (2 h) y un laboratorio (2 h). Los temas marcados con ✂️ pueden pasar a lectura autónoma si se pierden clases.
Lenguajes regularesLenguajes libres de contextoComputabilidadComplejidad
- 01
Lenguajes y autómatas finitos
Lenguajes regulares- Teoría
- Presentación · Cadenas, lenguajes y problemas de decisión · Autómatas finitos deterministas · Construcción del producto
- Laboratorio
- Un simulador de DFA
- 02
No determinismo
Lenguajes regulares- Teoría
- No determinismo: NFA y transiciones ε · Construcción de subconjuntos · Propiedades de cierre
- Laboratorio
- De NFA a DFA
- 03
Expresiones regulares
Lenguajes regulares- Teoría
- Expresiones regulares · De expresión regular a NFA · De DFA a expresión regular: el teorema de Kleene
- Laboratorio
- Un grep pequeño
- 04
- Teoría
- Lenguajes no regulares: el lema de bombeo · Myhill-Nerode y minimización de DFA · Una cota inferior de memoria en streaming
- Laboratorio
- Práctica 1 · Opcional: minimizar un DFA
- 05
Gramáticas libres de contexto
Lenguajes libres de contexto- Teoría
- Gramáticas libres de contexto, derivaciones y ambigüedad · Forma normal de Chomsky y el algoritmo CYK
- Laboratorio
- Un parser con CYK
- 06
- Teoría
- Autómatas de pila · Equivalencia con las gramáticas · Lema de bombeo para lenguajes libres de contexto · Cómo trabaja un parser real
- Laboratorio
- Práctica 2 · Opcional: un simulador de PDA
- 07
Máquinas de Turing
Computabilidad- Teoría
- Máquinas de Turing: definición, configuraciones y ejemplos · Variantes de la máquina · Tesis de Church-Turing
- Laboratorio
- Un simulador de máquinas de Turing
- 08
- 09
Lo decidible y lo indecidible
Computabilidad- Teoría
- Lenguajes decidibles: problemas sobre autómatas y gramáticas · Máquina universal · Diagonalización · El problema de la parada
- Laboratorio
- ¿Son equivalentes dos DFA?
- 10
Reducciones
Computabilidad- Teoría
- Reducciones · Teorema de Rice · Historias de cómputo · Problema de correspondencia de Post · Problemas indecidibles sobre gramáticas
- Laboratorio
- Buscar una solución de PCP
- 11
- Teoría
- Autorreferencia: el teorema de recursión y los quines · Incompletitud de Gödel · Complejidad de Kolmogorov
- Laboratorio
- Práctica 3 · Opcional: un quine en C++
- 12
Tiempo: P y NP
Complejidad- Teoría
- Complejidad en tiempo · La clase P sobre máquinas de Turing · NP: verificadores y máquinas no deterministas
- Laboratorio
- Escribir verificadores
- 13
NP-completitud, demostrada
Complejidad- Teoría
- El teorema de Cook-Levin, demostrado · NP-completitud: de SAT a 3-SAT y más allá · coNP
- Laboratorio
- Cook-Levin ejecutado: de una máquina a una fórmula
- 14
Espacio
Complejidad- Teoría
- Complejidad en espacio · Teorema de Savitch · PSPACE · PSPACE-completitud: TQBF y juegos · L y NL
- Laboratorio
- Práctica 4 · Opcional: quién gana en geografía generalizada
- 15
- Teoría
- Teoremas de jerarquía · Oráculos y los límites de la diagonalización · Computación probabilística: BPP · Qué sigue abierto · Repaso
- Laboratorio
- Verificar un producto de matrices al azar
- 16