Teoría de la Computación 2023
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 19:00 a 21:25 CIT-503, y Miércoles de 19:00 a 20:35 CIT-301.
Office Hours
- Viernes de 18:00 a 19:00.
Material del curso
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 01 | 05.07.2023 | Introducción al curso. Aspectos generales de la teoría de la computación. Aula 01 |
Hopcroft-Ullman, Sección 1.1 |
| 02 | 10.07.2023 | Autómatas Finitos Deterministas (AFD). Tabla de transiciones. Aula 02a Aula 02b |
Hopcroft-Ullman, Secciones 2.1, 2.2 |
| 03 | 12.07.2023 | Expresiones regulares. Árboles sintáctivos para regexp. Notación infix y postfix. Aula 03a Aula 03b |
Hopcroft-Ullman, Sección 3.1 |
| L1 | 17.07.2023 | Lab 01 | |
| 04 | 19.07.2023 | Función de transición extendida. Implementación de AFDs. Aula 04 | Hopcroft-Ullman, Sección 2.2 |
| 05 | 19.07.2023 | Autómatas Finitos No Deterministas (AFN). Aula 05 | Hopcroft-Ullman, Sección 2.3 |
| 06 | 24.07.2023 | Conversión de AFN a AFD. Cerradura y épsilon-transiciones. |
Hopcroft-Ullman, Sección 2.5 |
| L2 | 26.07.2023 | Lab 02 | |
| 07 | 31.07.2023 | Conversión de Regexp a AFN. Algoritmo de Thompson. Algoritmo de Glushkov. Aula 06a Aula 06b | Hopcroft-Ullman, Sección 3.2 |
| 08 | 07.08.2023 | Conversión de AFN a Regexp. Algoritmo de Reducción. Método de Arden. Aula 07 | Hopcroft-Ullman, Sección 3.4 |
| L3 | 09.08.2023 | Lab 03 | |
| 09 | 14.08.2023 | Propiedades de lenguajes regulares: vacuidad, finitud, Pumping Lemma. Aula 08 | Hopcroft-Ullman, Sección 3.4 |
| 10 | 16.08.2023 | Producto de autómatas. Algoritmo de equivalencia. Algoritmo de minimización. Aula 09a | Hopcroft-Ullman, Sección 3.4 |
| 11 | 16.08.2023 | Propiedades de cerradura. Algoritmos para unión, intersección, diferencia. Aula 09b | Hopcroft-Ullman, Sección 3.4 |
| L4 | 21.08.2023 | Lab 04 | |
| L5 | 23.08.2023 | Lab 05 | |
| 12 | 28.08.2023 | Gramáticas libres del contexto. Aula 12 |
Hopcroft-Ullman, Sección 4.2 |
| 13 | 30.08.2023 | Examen Corto 1. |
Corto 1 |
| 14 | 18.09.2023 | Árboles sintácticos. Derivaciones leftmost y rightmost. Aula 13 | Hopcroft-Ullman, Sección 4.3 |
| 15 | 20.09.2023 | Ambigüedad en gramáticas. Aula 14 |
|
| 16 | 25.09.2023 | Algoritmo de simplificación de gramáticas. Aula 15 |
|
| 17 | 27.09.2023 | Entrega del proyecto 1. | |
| 18 | 02.10.2023 | Forma Normal de Chomsky (CNF). Conversión a la CNF. Aula 16 |
|
| 19 | 04.10.2023 | Ejemplos de reducción y conversión a CNF. Ejemplo Reducción Ejemplo Binarización Ejemplo CNF |
|
| 20 | 09.10.2023 | Autómatas de pila (PDA). Ejemplos. Aula 17 Aula 18 |
|
| L6 | 11.10.2023 | Lab 06 | |
| 21 | 16.10.2023 | Ejemplos. Conversión entre PDA y CFG. Pumping Lemma para PDA. Aula 19 Aula 20 | |
| L7 | 18.10.2023 | Lab 07 | |
| 22 | 23.10.2023 | Máquinas de Turing. Aula 21 Aula 22 |
|
| 23 | 25.10.2023 | Ejemplos de máquinas de Turing. Aula 23 |
|
| 24 | 30.10.2023 | Entrega del proyecto 2. | |
| 25 | 06.11.2023 | Análisis de algoritmos. Aula 24 |
|
| L8 | 08.11.2023 | Lab 08 | |
| 26 | 13.11.2023 | Extensiones de máquinas de Turing: Multi-tracks y multi-cinta. Aula 25 | |
| 27 | 13.11.2023 | Complejidad y computabilidad. Aula 26 |
|
| 28 | 15.11.2023 | Cálculo Lambda: Axiomas, ejemplos, Números de Church. Aula 27 | |
| 29 | 15.11.2023 | Clases de complejidad. P vs NP. Ejemplo del TSP. Aula 28 | |
| 30 | 20.11.2023 | Máquinas de Turing Universales (UTM). Dispositivos Turing-completos. | |
| 31 | 22.11.2023 | Entrega del Proyecto 3. |
Lecturas complementarias
(Autores: T. Gálvez, B. Pojoy, P. Mejía y A. Reyes-Figueroa, 2022).
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 01 | 31.07.2023 | Lectura 1 - Expresiones regulares y AFNs. | Lectura 1 |
| 02 | 07.08.2023 | Lectura 2 - Conversión de AFNs a AFDs y construcción directa del AFD. | Lectura 2 |
| 03 | 21.08.2023 | Lectura 3 - Minimización de AFDs. | Lectura 3 |
| 04 | 23.10.2023 | Lectura 4 - Máquinas de Turing. | Lectura 4 |
| 05 | 08.11.2023 | Lectura 5 - Análisis de Algoritmos y notación asintótica. | Lectura 5 |
Proyectos
En el curso se desarrollarán tres proyectos.
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 21.08.2023 | Proyecto 1 - Algoritmos sobre AFDs, AFNs y regexp. | Proyecto 1 Fecha de Entrega: 25-29 septiembre. |
| 2 | 27.09.2023 | Presentación y revisión del proyecto. | |
| 3 | 29.09.2023 | Entrega del reporte final. |
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 01.10.2023 | Proyecto 2 - Algoritmo CYK para gramáticas. | Proyecto 2 Fecha de Entrega: lunes 30 de octubre. |
| 2 | 30.10.2023 | Presentación y revisión del proyecto. | |
| 3 | 02.11.2023 | Entrega del reporte final. |
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 05.11.2023 | Proyecto 3 - Máquinas de Turing. | Proyecto 3 Fecha de Entrega: miércoles 22 de noviembre. |
| 2 | 22.11.2023 | Presentación y revisión del proyecto. | |
| 3 | 24.11.2023 | 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 automatas, 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). Introduccón a la Teoría de Autómatas, Gramáticas y Lenguajes.