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
- Las Preguntas de repaso al final de cada guía semanal.
- Los ejercicios al final de cada capítulo de los apuntes.
- Escribir cada demostración sin mirar los apuntes, y después compararla paso a paso.
- Ante una reducción, escribir primero de qué problema a cuál va y por qué, antes de construir nada.
- Comprobar las construcciones hechas a mano con los simuladores que escribieron en los laboratorios.
- Rehacer los laboratorios y las prácticas sin mirar la solución.
Exámenes de práctica
- Parcial de práctica: semanas 1 a 7.
- Final de práctica: todo el curso, con énfasis en las semanas 9 a 15, y una lista de lo que deberían poder hacer al terminar el curso.
Resuélvanlos en papel y con el reloj corriendo, antes de mirar los apuntes. Las soluciones las entrega el docente.