Teoría de la Computación 2025
Este es un curso introductorio a la teoría de la computación, la cual se ocupa de determinar cuáles problemas pueden ser resueltos computacionalmente y con qué eficiencia, así como de entender el límite entre los problemas computables y los no-computables, y clasificarlos de acuerdo a su simpleza o dificultad.
El curso inicia con el estudio de distintos modelos de cómputo, como los autómatas finitos (que son los más sencillos), y sus diferentes tipos y aplicaciones; las máquinas de Turing (que son las computadoras usuales de hoy en día) y las computadoras cuánticas (cuyo funcionamiento no es digital). Una vez formulado un modelo de computación, nos interesa conocer la cantidad de recursos computacionales que es necesario utilizar para resolver un problema. El primero de estos recursos es el tiempo: cuántos pasos o cuántas acciones debemos realizar para resolver el problema. También son importantes el espacio ocupado, la necesidad de utilizar una fuente de números aleatorios, la posibilidad de resolver subproblemas en paralelo, entre otros.
La formalización de un modelo computacional como objeto matemático permite expresar de manera precisa preguntas sobre problemas o algoritmos. En particular, si L es un problema. ¿Puede L ser resuelto por un algoritmo? ¿Puede ser L resuelto de manera eficiente? ¿Cómo podemos construir un algoritmo eficiente para L? ¿Es L un problema para el cual no existe un algoritmo que lo resuelva? Contestaremos a algunas de estas preguntas, mientras que otras se verán en los cursos de Lógica Matemática y en Análisis de Algoritmos.
Prerrequisitos
Se recomienda que los estudiantes antes del curso estén habituados con los siguientes temas:
- Álgebra lineal (matricial).
- Matemática discreta (conteo, permutaciones, divisibilidad, congruencias).
- Grafos (representaciones, propiedades, algoritmos).
- Cálculo (funciones, límites, derivadas).
- Estructuras y algoritmos (pilas y colas, árboles, grafos).
Bastará con haber cursado una materia de cálculo y una de mátemática discreta. En el caso de programación, conviene conocer muy bien los temas de estructuas de datos y algoritmos.
El curso tiene una carga fuerte en el tema de matemática y estructuras abstractas. Cuando sea conveniente, dedicaremos una parte del curso a cubrir algunos prerrequisitos necesarios en los temas.
Programa del curso
Horario
- Lunes de 17:20 a 19:45 CIT-414, y Miércoles de 19:00 a 20:35 CIT-414.
Office Hours
- Martes o jueves, 19:00 a 19:45.
Material del curso
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 01 | 02.07.2025 | Introducción al curso. Aspectos generales de la teoría de la computación. Aula 01 |
Hopcroft, Sección 1.1 |
| 02 | 07.07.2025 | Autómatas finitos deterministas (AFD). Función de transición. Aula 02a Aula 02b |
Hopcroft, Secciones 2.1, 2.2 |
| 03 | 09.07.2025 | Expresiones regulares o regexp. Aula 03 |
Hopcroft, Sección 3.1 |
| 03 | 09.07.2025 | Árboles sintácticos de regexp. Notación infix, prefix y postfix. Aula 04a |
Hopcroft, Sección 3.1 |
| L1 | 14.07.2025 | Lab 01. |
Lab 01 Entrega: 21 de julio |
| 04 | 16.07.2025 | Función de transición extendida. Configuraciones y derivaciones. Aula 04b |
Hopcroft, Sección 2.2 |
| 05 | 21.07.2025 | Autómatas finitos no deterministas (AFN). Aula 05 |
Hopcroft, Sección 2.3 |
| 06 | 21.07.2025 | Conversión de AFN a AFD: Construcción de subconjuntos. | Hopcroft-Ullman, Sección 2.5 |
| 07 | 23.07.2025 | Épsilon-transiciones. Conversión de ε-AFN a AFD. | Hopcroft-Ullman, Sección 2.5 |
| L2 | 28.07.2025 | Lab 02. |
Lab 02 Entrega: 4 de agosto |
| 08 | 28.07.2025 | Conversión de regexp a AFN: Algoritmo de Thompson. Aula 06a | Hopcroft-Ullman, Sección 3.2 |
| 09 | 30.07.2025 | Conversión de regexp a AFN: Método de Glushkov. Aula 06b | Hopcroft-Ullman, Sección 3.2 |
| 10 | 30.07.2025 | Conversión de AFN a regexp: Algoritmo de reducción. Aula 07a | Hopcroft-Ullman, Sección 3.2 |
| 11 | 04.08.2025 | Conversión de AFN a regexp: Método de Arden. Aula 07b | Hopcroft-Ullman, Sección 3.4 |
| L3 | 04.08.2025 | Lab 03. |
Lab 03 Entrega: 11 de agosto |
| 12 | 06.08.2025 | Propiedades de cerradura. Producto de autómatas. Aula 08 | Hopcroft-Ullman, Sección 4.2 |
| 13 | 11.08.2025 | Propiedades de decisión. Aula 09 |
Hopcroft-Ullman, Sección 4.3 |
| 14 | 13.08.2025 | Equivalencia y minimización de autómatas. Aula 10 |
Hopcroft-Ullman, Sección 4.4 |
| L4 | 18.08.2025 | Lab 04. |
Lab 04 Entrega: 25 de agosto |
| 15 | 20.08.2025 | Pumping Lemma para lenguajes regulares. Ejemplos de lenguajes no regulares. Aula 11 | Hopcroft-Ullman, Sección 4.1 Pumping Lemma for RL |
| 16 | 20.08.2025 | Gramáticas libres de contexto (CFG). Notación Backus-Naur. Aula 12 | Hopcroft-Ullman, Sección 5.1 |
| 17 | 27.08.2025 | Ejemplos de CFGs. Comentarios sobre gramáticas sensibles al contexto. | Hopcroft-Ullman, Sección 5.2 |
| 18 | 01.09.2025 | Parsing trees. Derivaciones a la izquierda y a la derecha. Aula 13 | Hopcroft-Ullman, Sección 5.3 |
| 19 | 01.09.2025 | Ambigüedad. Remoción de la ambigüedad. Aula 14 |
Hopcroft-Ullman, Sección 5.4 |
| 20 | 03.09.2025 | Algoritmo de simplificación de gramáticas CFG. Aula 15 |
Ejemplo 1 Ejemplo 2 |
| 21 | 08.09.2025 | Revisión del primer proyecto. |
|
| 22 | 10.09.2025 | Formas normales. Forma Normal de Chomsky Aula 16 |
Hopcroft-Ullman, Sección 5.3 |
| L5 | 10.09.2025 | Lab 05. |
Lab 05 Entrega: 24 de septiembre |
| 23 | 24.09.2025 | Autómatas de pila (PDA). Aula 17 Aula 18 |
Hopcroft-Ullman, Secciones 6.1 y 6.2 |
| 24 | 29.09.2025 | Ejemplos. Equivalencia entre PDA y CFG. Aula 19 |
Hopcroft-Ullman, Sección 6.3 |
| L6 | 29.09.2025 | Lab 06. |
Lab 06 Entrega: 6 de octubre |
| 25 | 01.10.2025 | Pumping Lemma para lenguajes libres de contexto. Aula 20 |
Hopcroft-Ullman, Sección 6.3 |
| 26 | 06.10.2025 | Introducción al análisis de algoritmos. Notación asintótica. Aula 21 | |
| L7 | 08.10.2025 | Lab 07. |
Lab 07 Entrega: 8 de octubre |
| 27 | 13.10.2025 | Máquinas de Turing. |
|
| 28 | 15.10.2025 | Ejemplos de máquinas de Turing. |
|
| 29 | 22.10.2025 | Revisión del segundo proyecto. |
|
| 30 | 27.10.2025 | Más ejemplos de máquinas de Turing. |
|
| L8 | 27.10.2025 | Lab 08. |
Lab 08 Entrega: 3 de noviembre |
| 30 | 29.10.2025 | Extensiones de máquinas de Turing. |
|
| 31 | 03.11.2025 | Complejidad computacional. P vs. NP. |
|
| 32 | 05.11.2025 | Máquinas de Turing universales. Otros modelos de computación. | |
| 33 | 17.11.2025 | Presentación de Proyectos Finales. |
Lecturas complementarias
(Autores: T. Gálvez, B. Pojoy, P. Mejía y A. Reyes-Figueroa, 2022).
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 01 | 23.07.2025 | Lectura 1 - Expresiones regulares y AFNs. | Lectura 1 |
| 02 | 23.07.2025 | Lectura 2 - Conversión de AFNs as AFDs. | Lectura 2 |
| 03 | 20.08.2025 | Lectura 3 - Algoritmo de minimización de AFDs. | Lectura 3 |
| 04 | 29.10.2025 | Lectura 4 - Máquinas de Turing. | Lectura 4 |
Proyectos
En el curso se desarrollarán tres proyectos.
Primer Proyecto
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 12.08.2025 | Proyecto 1 - Algoritmos sobre AFDs, AFNs y regexp. | Proyecto 1 Fecha de Entrega: 08-12 septiembre. |
| 2 | 08.09.2025 | Presentación y revisión del proyecto. | |
| 3 | 12.09.2025 | Entrega del reporte final. |
Segundo Proyecto
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 10.09.2025 | Proyecto 2 - Algoritmo CYK para gramáticas. | Proyecto 2 Fecha de Entrega: 22 de octubre. |
| 2 | 22.10.2025 | Presentación y revisión del proyecto. | |
| 3 | 24.10.2025 | Entrega del reporte final. |
Tercer Proyecto
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 27.10.2025 | Proyecto 3 - Máquinas de Turing. | Proyecto 3 Fecha de Entrega: 21 de noviembre. |
| 2 | 17-21.11.2025 | Presentación y revisión del proyecto. | |
| 3 | 21.11.2025 | Entrega del reporte final. |
Referencias
Textos:
-
J. Hopcroft, R. Motwani, J. Ullman (2006). Automata Theory, Languages and Computation.
-
J. Hopcroft, R. Motwani, J. Ullman (2007). Teoría de autómatas, lenguajes y computación.
Referencias adicionales:
-
H. Lewis, C. Papadimitriou (1998). Elements of the Theory of Computation.
-
J. G. Brookshear (1988). Theory of Computation: Formal Languages, Automata, and Complexity.
-
J. G. Brookshear (1993). Teoría de la Computación, Lenguajes Formales, Autómatas y Complejidad.
-
R. de Castro Korgi (2004). Teoría de la Computación, Lenguajes Autómatas, Gramáticas.
-
E. Gaudioso Vásquez et al. (2017). Introducción a la Teoría de Autómatas, Gramáticas y Lenguajes.