Teoría de la Computación — Programa del curso

Docente: Gerson Garrido

1. Descripción

En Análisis y Diseño de Algoritmos ustedes aprendieron a resolver problemas y terminaron con una sospecha: hay problemas para los que nadie conoce un algoritmo rápido. Este curso va al fondo de esa pregunta. ¿Qué es exactamente una computadora, vista como objeto matemático? ¿Qué problemas no puede resolver ningún programa, por más tiempo que tenga? Y de los que sí se pueden resolver, ¿cuáles exigen demasiado tiempo o demasiada memoria?

Se avanza de la máquina más simple a la más general. Cada modelo se define con precisión, se programa y se le busca el límite: un lenguaje que no puede reconocer, con su demostración. En teoría se construyen las máquinas y se demuestran los teoremas. En el laboratorio se programan en C++ las mismas construcciones, hasta que pasen el juez del curso: lo que en la pizarra es “existe un autómata” en el laboratorio es un programa que lo produce. Se organiza en cuatro partes:

  1. Lenguajes regulares — autómatas finitos, expresiones regulares y lo que no pueden hacer.
  2. Lenguajes libres de contexto — gramáticas, parsing y autómatas de pila.
  3. Computabilidad — máquinas de Turing, problemas indecidibles y reducciones.
  4. Complejidad — tiempo y espacio, NP-completitud demostrada, PSPACE y lo que sigue abierto.

Los apuntes son el texto del curso, y cada capítulo abre con una ruta de lectura: qué leer antes de clase, qué se explica en clase y qué repasar después. El libro de Michael Sipser es la referencia, citada por sección en cada guía semanal, y las notas de Jeff Erickson son la lectura gratuita de apoyo. Los términos técnicos siguen la guía de estilo, y el glosario reúne los principales.

2. Carga horaria

Componente Horas/semana Formato
Teoría 4 h Dos sesiones de 2 h (Sesión A y Sesión B)
Laboratorio 2 h Una sesión

3. Resultados de aprendizaje

Al finalizar el curso, el estudiante será capaz de:

  1. Diseñar un autómata finito, una expresión regular o una gramática para un lenguaje dado, y demostrar que reconoce exactamente ese lenguaje.
  2. Convertir entre DFA, NFA y expresiones regulares, y minimizar un DFA, a mano y con un programa.
  3. Demostrar que un lenguaje no es regular o no es libre de contexto, con el lema de bombeo o con cadenas distinguibles.
  4. Decidir si una cadena pertenece al lenguaje de una gramática con el algoritmo CYK, y relacionar gramáticas con autómatas de pila.
  5. Describir una máquina de Turing en sus tres niveles de detalle y explicar qué afirma la tesis de Church-Turing.
  6. Demostrar que un problema es indecidible o no reconocible, por diagonalización o con una reducción en la dirección correcta.
  7. Ubicar un problema en P, NP, coNP o PSPACE, y demostrar que es completo para su clase con una reducción en tiempo polinomial.
  8. Explicar la demostración del teorema de Cook-Levin y lo que implican los teoremas de jerarquía.
  9. Implementar en C++ las construcciones del curso: simuladores de cada modelo, conversiones entre modelos y reducciones que se pueden ejecutar.
  10. Explicar qué preguntas del área siguen abiertas y qué cambiaría con cada respuesta.

4. Bibliografía

Texto del curso: los apuntes, un capítulo por semana. No se requiere comprar ningún libro.

Referencia: Michael Sipser, Introduction to the Theory of Computation, 3.ª edición, Cengage, 2013. Las guías semanales citan sus secciones.

Lectura gratuita de apoyo: Jeff Erickson, Models of Computation, notas que acompañan su libro Algorithms, para las partes 1 a 3. Para la parte 4, Boaz Barak, Introduction to Theoretical Computer Science, gratuito en línea.

5. Calendario

Este es el calendario oficial del curso. Cada semana enlaza a su guía con objetivos, temas y actividades de laboratorio. Los temas marcados con ✂️ se pueden comprimir o pasar a lectura autónoma si se pierden clases por feriados. Las semanas 8 y 16 son de exámenes y no tienen clases regulares. En las semanas con práctica, la práctica ocupa la sesión de laboratorio y el problema de esa semana queda como ejercicio opcional.

Sem. Sesión A (2 h) Sesión B (2 h) Laboratorio (2 h) Práctica o examen
1 Presentación · Cadenas, lenguajes y problemas de decisión Autómatas finitos deterministas · Construcción del producto Un simulador de DFA
2 No determinismo: NFA y transiciones ε Construcción de subconjuntos · Propiedades de cierre De NFA a DFA
3 Expresiones regulares · De expresión regular a NFA De DFA a expresión regular: el teorema de Kleene Un grep pequeño
4 Lenguajes no regulares: el lema de bombeo Myhill-Nerode y minimización de DFA · ✂️ Una cota inferior de memoria en streaming Práctica 1 · Opcional: minimizar un DFA Práctica 1
5 Gramáticas libres de contexto, derivaciones y ambigüedad Forma normal de Chomsky y el algoritmo CYK Un parser con CYK
6 Autómatas de pila · Equivalencia con las gramáticas Lema de bombeo para lenguajes libres de contexto · ✂️ Cómo trabaja un parser real Práctica 2 · Opcional: un simulador de PDA Práctica 2
7 Máquinas de Turing: definición, configuraciones y ejemplos Variantes de la máquina · Tesis de Church-Turing Un simulador de máquinas de Turing
8 Examen parcial (semanas 1 a 7)
9 Lenguajes decidibles: problemas sobre autómatas y gramáticas Máquina universal · Diagonalización · El problema de la parada ¿Son equivalentes dos DFA?
10 Reducciones · Teorema de Rice Historias de cómputo · Problema de correspondencia de Post · Problemas indecidibles sobre gramáticas Buscar una solución de PCP
11 Autorreferencia: el teorema de recursión y los quines Incompletitud de Gödel · ✂️ Complejidad de Kolmogorov Práctica 3 · Opcional: un quine en C++ Práctica 3
12 Complejidad en tiempo · La clase P sobre máquinas de Turing NP: verificadores y máquinas no deterministas Escribir verificadores
13 El teorema de Cook-Levin, demostrado NP-completitud: de SAT a 3-SAT y más allá · coNP Cook-Levin ejecutado: de una máquina a una fórmula
14 Complejidad en espacio · Teorema de Savitch · PSPACE PSPACE-completitud: TQBF y juegos · L y NL Práctica 4 · Opcional: quién gana en geografía generalizada Práctica 4
15 Teoremas de jerarquía · ✂️ Oráculos y los límites de la diagonalización Computación probabilística: BPP · Qué sigue abierto · Repaso Verificar un producto de matrices al azar
16 Examen final (todo el curso)

6. Prácticas

Hay cuatro prácticas, en las semanas 4, 6, 11 y 14. Cada una ocupa la sesión de laboratorio de su semana y combina una demostración o una construcción escrita con un problema en C++. El formato y las reglas están en practicas/README.md.

Los laboratorios sirven para practicar: el juez da la respuesta de inmediato, y preparan las prácticas y los exámenes.

7. Políticas

  • Trabajo: Individual. Se puede discutir ideas, pero cada estudiante escribe su propio código y sus demostraciones, y debe poder explicarlos.

Herramientas permitidas

En este curso no se usa IA generativa en ningún trabajo: laboratorios, prácticas ni exámenes. Las demás herramientas se permiten en laboratorios y prácticas, dentro del entorno del curso.

Herramienta ¿Se permite?
Mensajes del compilador, gdb, valgrind y sanitizers Sí
Documentación oficial (cppreference, manuales del entorno) y búsqueda en la web Sí, para consultar el lenguaje y la biblioteca. Copiar una solución ajena es plagio
Autocompletado del editor que no genera soluciones enteras (nombres, firmas, paréntesis) Sí
Correctores de ortografía, traductores y herramientas de accesibilidad Sí
Formateadores de código y linters Sí
Simuladores de autómatas y de máquinas de Turing, para comprobar una construcción propia Sí. Diseñar la construcción con un generador automático no cuenta como propia
IA generativa para pedir explicaciones, sin que escriba código ni demostraciones No
IA generativa que escribe código o demostraciones No

Cómo se declara lo usado: al final de la entrega, una nota breve con la documentación, las páginas consultadas y el simulador usado, si lo hubo, salvo las del compilador y el editor. Cualquier entrega puede llevar una explicación oral: quien entrega debe poder explicar cualquier parte de su código y de su demostración.

8. Entorno de trabajo

Todo se hace en un mismo entorno, con el compilador de C++, gdb, valgrind, make, Git, el juez del curso y un solucionador SAT ya instalados. Se abre con GitHub Codespaces o con Docker. Instrucciones en labs/README.md.