Lenguajes regularesLenguajes libres de contextoComputabilidadComplejidad
  1. 01
    Teoría
    Presentación · Cadenas, lenguajes y problemas de decisión · Autómatas finitos deterministas · Construcción del producto
    Laboratorio
    Un simulador de DFA
  2. 02

    No determinismo

    Lenguajes regulares
    Teoría
    No determinismo: NFA y transiciones ε · Construcción de subconjuntos · Propiedades de cierre
    Laboratorio
    De NFA a DFA
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 08

    Examen parcial

    Computabilidad
    Teoría
    Laboratorio
  9. 09
    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. 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. 11

    Autorreferencia

    Computabilidad✂️
    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. 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. 13
    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. 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. 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. 16

    Examen final

    Complejidad
    Teoría
    Laboratorio