Exámenes

Examen Cuándo Temas
Parcial Semana 8 Semanas 1–7: DFA, NFA, expresiones regulares, lema de bombeo, Myhill-Nerode, minimización, gramáticas, CYK, autómatas de pila y máquinas de Turing
Final Semana 16 Todo el curso, con énfasis en las semanas 9–15: decidibilidad, reducciones, Rice, autorreferencia, P y NP, Cook-Levin, PSPACE, jerarquías y BPP

Formato sugerido

  • Construir: un DFA, un NFA, una expresión regular, una gramática o una máquina de Turing para un lenguaje dado.
  • Convertir a mano: un NFA a DFA, una expresión regular a NFA, una gramática a forma normal de Chomsky, o minimizar un DFA.
  • Simular a mano: una máquina con una cadena corta, escribiendo sus configuraciones, o la tabla de CYK.
  • Demostrar que no se puede: que un lenguaje no es regular o no es libre de contexto.
  • Clasificar: decir si un lenguaje es regular, libre de contexto, decidible, reconocible o ninguno, y justificarlo.
  • Reducir: demostrar que un problema es indecidible, o que es NP-completo o PSPACE-completo, con la reducción en la dirección correcta.
  • Verdadero o falso, con justificación: afirmaciones sobre cierre, inclusiones entre clases y qué implicaría cada respuesta a una pregunta abierta.

Cómo estudiar

  1. Las Preguntas de repaso al final de cada guía semanal.
  2. Los ejercicios al final de cada capítulo de los apuntes.
  3. Escribir cada demostración sin mirar los apuntes, y después compararla paso a paso.
  4. Ante una reducción, escribir primero de qué problema a cuál va y por qué, antes de construir nada.
  5. Comprobar las construcciones hechas a mano con los simuladores que escribieron en los laboratorios.
  6. Rehacer los laboratorios y las prácticas sin mirar la solución.

Exámenes de práctica

Resuélvanlos en papel y con el reloj corriendo, antes de mirar los apuntes. Las soluciones las entrega el docente.