Teoría de la Computación 2022
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).
- Programación en Python.
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:50 a 21:25, y Miércoes de 19:00 a 21:25.
Office Hours
- Viernes, de 19:00 a 20:00.
Material del curso
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 00 | 06.07.2022 | Introducción. Aspectos generales de la teoría de la computación. |
|
| 01 | 11.07.2022 | Alfabetos, palabras y lenguajes. Autómatas finitos deterministas (AFD). Aula 01a Aula 01b |
Secciones 1.5 y 2.1 Hopcroft. |
| 02 | 13.07.2022 | Expresiones regulares. Formalismo de los AFD. Aula 02a Aula 02b |
Sección 2.1 Hopcroft. |
| L1 | 13.07.2022 | Lab 01. |
Lab 01 |
| 03 | 18.07.2022 | Función de transición extendida. Derivaciones. Simulación de un AFD. Aula 03 | Capítulo 2 Hopcroft. |
| 04 | 20.07.2022 | Autómatas finitos no-deterministas (AFN). Equivalencia entre AFD y AFN. Aula 04 | Capítulo 2 Hopcroft. |
| L2 | 20.07.2022 | Lab 02. |
Lab 02 |
| 05 | 25.07.2022 | epsilon-AFN. Conversión de regexp a AFN: Algoritmo de Thompson. Aula 05a Aula 05b | Capítulo 3 Hopcroft. |
| 06 | 27.07.2022 | Conversión de AFN a regexp: Algoritmo de reducción. Lema de Arden. Aula 06 Aula 06_notas |
Capítulo 3 Hopcroft. |
| 07 | 03.08.2022 | Repaso de algoritmos en autómatas. |
|
| L3 | 03.08.2022 | Lab 03. |
Lab 03 |
| 08 | 08.08.2022 | Propiedades de lenguajes regulares. Pumping Lemma. Aula 07a |
|
| 09 | 10.08.2022 | Examen Corto 1. | Corto 01 |
| 10 | 17.08.2022 | Equivalencia de lenguajes regulares. Propiedades de cerradura. Aula 08 |
Capítulo 3 Hopcroft. |
| L4 | 17.08.2022 | Lab 04. |
Lab 04 |
| 11 | 22.08.2022 | Propiedades de Decisión. Algoritmo de minimización de AFD. Aula 09 |
Capítulo 3 Hopcroft. |
| 12 | 24.08.2022 | Repaso de algoritmo de minimización. Aula 10 |
Capítulo 3 Hopcroft. |
| L5 | 24.08.2022 | Lab 05. |
Lab 05 |
| 13 | 31.08.2022 | Gramáticas libres del contexto (CFG). Aula 12 |
|
| 14 | 05.09.2022 | Árboles sintácticos (parse trees). Ambigüedad. Aula 13 |
|
| 15 | 07.09.2022 | Remoción de Ambigüedad. Aula 14 |
|
| L6 | 07.09.2022 | Lab 06. |
Lab 06 |
| 16 | 21.09.2022 | Algoritmo de simplificación de gramáticas. Aula 15 Ejemplos |
|
| 17 | 26.09.2022 | Autómatas de Pila. Aula 16 Aula 17 |
|
| 18 | 28.09.2022 | Presentación del primer proyecto. |
|
| 19 | 03.10.2022 | Análisis de algoritmos. Notaciones asintóticas. Aula 18 |
|
| 19 | 05.10.2022 | Ejemplos de notación asintótica. |
|
| L7 | 05.10.2022 | Lab 07. |
Lab 07 |
| 20 | 12.10.2022 | Máquinas de Turing: motivación. Aula 20 |
|
| 21 | 17.10.2022 | Máquinas de Turing II: formalización, transiciones. Aula 21 |
|
| 22 | 19.10.2022 | Ejemplos de máquinas de Turing. Aula 22 |
|
| 23 | 24.10.2022 | Más ejemplos de máquinas de Turing. Aula 23 |
|
| L8 | 26.10.2022 | Lab 08. |
Lab 08 |
| 24 | 26.10.2022 | Examen Corto 2. | Corto 02 Fecha de Entrega: lunes 31 de octubre. |
| 25 | 31.10.2022 | Máquinas de Turing III: Extensiones. Aula 24 |
|
| 26 | 07.11.2022 | Computabilidad, Decidibilidad. Modelos computacionales. Aula 25 |
|
| 27 | 09.11.2022 | Cálculo Lambda. Aula 26 |
|
| 28 | 09.11.2022 | Examen Corto 3. | Corto 03 Fecha de Entrega: domingo 13 de noviembre. |
| 29 | 14.11.2022 | Resolución de dudas sobre el proyecto. | |
| 30 | 16.11.2022 | Clases de Complejidad. P vs NP. Máquinas de turing universales. |
|
| 31 | 23.11.2022 | Presentación de proyectos finales. |
Lecturas complementarias
(Autores: T. Gálvez, B. Pojoy, P. Mejía y A. Reyes-Figueroa).
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 01 | 25.07.2022 | Lectura 1 - Expresiones regulares y AFNs. | Lectura 1 |
| 02 | 08.08.2022 | Lectura 2 - Conversión de AFNs a AFDs y construcción directa del AFD. | Lectura 2 |
| 03 | 22.08.2022 | Lectura 3 - Minimización de AFDs. | Lectura 3 |
| 04 | 05.10.2022 | Lectura 4 - Notación Asintótica. | Lectura 4 |
| 05 | 24.10.2022 | Lectura 5 - Máquinas de Turing. | Lectura 5 |
| 06 | 07.11.2022 | Lectura 6 - Complejidad. | Lectura 6 |
Proyectos
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 1 | 22.08.2022 | Proyecto 1 - Algoritmos sobre AFDs, AFNs y regexp. | Proyecto 1 |
| . | 28.09.2022 | Presentación y entrega de informe. |
| No. | Fecha | Tópicos | Recursos |
|---|---|---|---|
| 2 | 31.10.2022 | Proyecto 2 - Algoritmo CYK y Funciones Lambda. | Proyecto 2 |
| . | 23.11.2022 | Presentación. | |
| . | 26.11.2022 | Entrega de informe final. |
Horarios para la presentación del segundo proyecto. (23 de noviembre)
| No. | Hora | Grupo |
|---|---|---|
| 1 | 7:00 pm - 7:15pm | Equipo 9 |
| 2 | 7:15 pm - 7:30pm | Equipo 8 |
| 3 | 7:30 pm - 7:45pm | Equipo 1 |
| 4 | 7:45 pm - 8:00pm | Equipo 7 |
| 5 | 8:00 pm - 8:15pm | Equipo 4 |
| 6 | 8:15 pm - 8:30pm | Equipo 2 |
| 7 | 8:30 pm - 8:45pm | Equipo 5 |
| 8 | 8:45 pm - 9:00pm | Equipo 3 |
| 9 | 9:00 pm - 9:15pm | Equipo 10 |
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.
-
H. Lewis, C. Papadimitriou (1998). Elements of the Theory of Computation.
Referencias adicionales:
-
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.