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 |
Lecturas complementarias
(Autores: T. Gálvez, B. Pojoy, P. Mejía y A. Reyes-Figueroa, 2022).
Se agregarán conforme se desarrolle el curso.
Proyectos
En el curso se desarrollarán tres proyectos, los cuales se indicarán más adelante.
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.