Teoría de la Computación 2024
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:40 G-205, y Miércoles de 19:00 a 20:35 G-205.
Office Hours
- Viernes de 18:00 a 19:00.
Material del curso
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 01 | 03.07.2024 | Introducción al curso. Aspectos generales de la teoría de la computación. Aula 01 |
Hopcroft-Ullman, sección 1.1 |
| 02 | 08.07.2024 | Autómatas Finitos Deterministas (AFD). Tabla de transiciones. Aula 02a Aula 02b | Hopcroft-Ullman, secciones 2.1, 2.2 |
| 03 | 10.07.2024 | Operaciones con lenguajes. Expresiones regulares (regexp). Abreviaturas para regexp. Aula 03a Aula 03b | Hopcroft-Ullman, Sección 3.1 regextutorials.com |
| L1 | 15.07.2024 | Lab 01 | |
| 04 | 17.07.2024 | Función de transición extendida. Configuraciones y derivaciones. Aula 04 | Hopcroft-Ullman, Sección 2.2 |
| 05 | 24.07.2024 | Autómatas Finitos No Deterministas (AFN). Aula 05 | Hopcroft-Ullman, Sección 2.3 |
| 06 | 29.07.2024 | Conversión de AFN a AFD: Construcción de subconjuntos. | Hopcroft-Ullman, Sección 2.5 |
| L2 | 29.07.2024 | Lab 02 | |
| 07 | 31.07.2024 | Conversión de Regexp a AFN: Algoritmo de Thompson. Algoritmo de Glushkov. Aula 06a Aula 06b | Hopcroft-Ullman, Sección 3.2 |
| L3 | 05.08.2024 | Lab 03 | |
| 08 | 05.08.2024 | Conversión de AFN a Regexp: Algoritmo de Reducción. | Hopcroft-Ullman, Sección 3.2 |
| 09 | 07.08.2024 | Conversión de AFN a Regexp: Método de Arden. Aula 07 | Hopcroft-Ullman, Sección 3.4 |
| 10 | 14.08.2024 | Propiedades de decisión. Producto de autómatas. Aula 08 | Hopcroft-Ullman, Sección 3.4 |
| 11 | 19.08.2024 | Minimización de autómatas: Algoritmo de Hopcroft. Aula 09 | Hopcroft-Ullman, Sección 3.4 |
| L4 | 19.08.2024 | Lab 04 | |
| 12 | 21.08.2024 | Lema de Bombeo (Pumping Lemma) para lenguales regulares. Aula 10 | Hopcroft-Ullman, Sección 3.4 |
| C1 | 26.08.2024 | Corto 1. | Corto 01 |
| 13 | 28.08.2024 | Gramáticas libres del contexto. Aula 12 |
Hopcroft-Ullman, Sección 4.1 |
| 14 | 18.09.2024 | Entrega proyecto 1. | |
| 15 | 23.09.2024 | Derivaciones leftmost y rightmost. Aula 13 |
Hopcroft-Ullman |
| 16 | 23.09.2024 | Ambigüedad. Remoción de ambgüedad. Aula 14 |
Hopcroft-Ullman |
| 17 | 25.09.2024 | Simplificación de gramáticas. Aula 15 |
Hopcroft-Ullman Ejemplo 1 |
| 18 | 30.09.2024 | Ejemplos de simplificación. Forma Normal de Chomsky. Aula 16 | Ejemplo 2 Ejemplo Binarización Ejemplo Chomsky |
| L5 | 30.09.2024 | Lab 05 | |
| 19 | 02.10.2024 | Autómatas de Pila (PDA). Aula 17 | |
| 20 | 07.10.2024 | Ejemplos de autómatas de Pila. Aula 18 |
|
| 21 | 09.10.2024 | Equivalencia entre CFG y PDAs. Aula 19 |
|
| L6 | 09.10.2024 | Lab 06 | |
| 22 | 14.10.2024 | Lema de Bombeo (Pumping Lemma) para gramáticas libres. Aula 20 | |
| 23 | 14.10.2024 | Máquinas de Turing. Aula 21 |
|
| 24 | 16.10.2024 | Ejemplos de máquinas de Turing. Aula 22 Aula 22b |
|
| 25 | 21.10.2024 | Máquinas de Turing II. Aula 23 |
|
| L7 | 23.10.2024 | Lab 07 | |
| 26 | 28.10.2024 | Entrega proyecto 2. | |
| 27 | 30.10.2024 | Extensiones de máquinas de Turing. Aula 24 |
|
| 28 | 04.11.2024 | Análisis de algoritmos. Notación Big O, Big Omega y Big Theta. Aula 25 | |
| L8 | 06.11.2024 | Lab 08 | |
| 29 | 11.11.2024 | Complejidad computacional. Clases P y NP. Aula 26 |
|
| 30 | 13.11.2024 | Máquinas de Turing universales. Turing-completeness. Aula 27 | |
| C1 | 13.01.2024 | Corto 2. | Corto 02 |
Lecturas complementarias
(Autores: T. Gálvez, B. Pojoy, P. Mejía y A. Reyes-Figueroa, 2022).
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 01 | 31.07.2024 | Lectura 1 - Expresiones regulares y AFNs. | Lectura 1 |
| 02 | 31.07.2024 | Lectura 2 - Conversión de AFNs as AFDs. | Lectura 2 |
| 03 | 19.08.2024 | Lectura 3 - Algoritmo de minimización. | Lectura 3 |
| 04 | 16.10.2024 | 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 | 14.08.2024 | Proyecto 1 - Algoritmos sobre AFDs, AFNs y regexp. | Proyecto 1 Fecha de Entrega: 16-20 septiembre. |
| 2 | 18.09.2024 | Presentación y revisión del proyecto. | |
| 3 | 20.09.2024 | Entrega del reporte final. |
Segundo Proyecto
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 30.09.2024 | Proyecto 2 - Algoritmo CYK para gramáticas. | Proyecto 2 Fecha de Entrega: lunes 28 de octubre. |
| 2 | 28.10.2024 | Presentación y revisión del proyecto. | |
| 3 | 31.10.2024 | Entrega del reporte final. |
Tercer Proyecto
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 23.10.2024 | Proyecto 3 - Máquinas de Turing. | Proyecto 3 Fecha de Entrega: domingo 24 de noviembre. |
| 2 | 18 al 22.11.2024 | Presentación y revisión del proyecto. | |
| 3 | 24.11.2024 | 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.