View on GitHub

tc2025

Teoría de la Computación 2025

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:

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

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.1
18 01.09.2025 Parsing trees. Derivaciones a la izquierda y a la derecha. Aula 13  
19 01.09.2025 Ambigüedad. Remoción de la ambigüedad.
Aula 14		  
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		  
L5 10.09.2025 Lab 05.
Lab 05
Entrega: 24 de septiembre
23      

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

Proyectos

En el curso se desarrollarán tres proyectos, los cuales se indicarán más adelante.

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: 13 de octubre.
2 13.10.2025 Presentación y revisión del proyecto.  
3 17.10.2025 Entrega del reporte final.  

Referencias