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 test corre 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.