Prácticas
Hay cuatro prácticas, cada una en la sesión de laboratorio de su semana.
| Práctica | Semana | Temas |
|---|---|---|
| 1 | 4 | DFA, NFA, construcción de subconjuntos, propiedades de cierre y expresiones regulares (semanas 1 a 3) |
| 2 | 6 | Lema de bombeo, Myhill-Nerode, minimización, gramáticas, forma normal de Chomsky y CYK (semanas 4 y 5) |
| 3 | 11 | Autómatas de pila, máquinas de Turing, decidibilidad, diagonalización y reducciones (semanas 6, 7, 9 y 10) |
| 4 | 14 | P, NP, verificadores, Cook-Levin y NP-completitud (semanas 12 y 13) |
Cómo funciona
- Ocupa la sesión de laboratorio de esa semana, y dura 2 horas. El problema de laboratorio de esa semana queda como ejercicio opcional.
- Tiene dos partes: una parte escrita, con una construcción y una demostración, y un problema en C++ resuelto en el entorno del curso.
- Trabajo: individual.
- El problema trae casos públicos:
make testcorre el juez con ellos. La revisión corre además casos privados, con otros datos y con el límite de tiempo del enunciado. - El código debe compilar sin advertencias con
-Wall -Wextra -std=c++20. - Herramientas: la lista de lo permitido y cómo declararlo está en el programa del curso.
Qué se pide en la parte escrita
- Una construcción se entrega completa: el diagrama o la tabla, y dos frases que digan por qué acepta lo que debe y por qué rechaza lo demás.
- Una demostración de imposibilidad (no regular, no libre de contexto, indecidible) nombra su técnica y muestra cada elección: la cadena, la división, la dirección de la reducción.
- Una reducción dice de qué problema a cuál va, qué construye y por qué las dos direcciones se cumplen.
Explicación oral
Puede haber una defensa oral breve: quien entrega debe poder explicar cualquier parte de su código y de su demostración.