Autómatas y Lenguajes Formales 2019-1

¿Qué es un modelo de cómputo? ¿Cuáles problemas puede resolver una computadora y cuáles no? La teoría de la computación se encarga de responder estas preguntas.

Esta materia expandirá tu mente: te dará el entendimiento necesario para crear sistemas computacionales más robustos, elegantes y eficientes. También obtendrás habilidades para expresar de manera más clara y precisa problemas relacionados a computación.

Aprenderás muchas técnicas para resolver problemas y tendrás suficiente criterio para saber cuando no es posible resolver un problema utilizando una computadora.

Este curso tiene impacto en todas las áreas de las ciencias de la computación.

Cenobio Moisés Vázquez Reyes (spidermoy@ciencias.unam.mx)

Enrique Antonio Bernal Cedillo (enrique_bernal@ciencias.unam.mx)

En esencia, el temario es el siguiente:

• Lenguajes regulares y autómatas finitos.
• Lenguajes libres del contexto.
• Máquinas de Turing.
• Introducción a la teoría de la complejidad computacional.

La bibliografía básica es la siguiente:

• Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.
• Kozen, D. C. (2012). Automata and computability. Springer Science & Business Media.
• Las notas de los profesores Favio Miranda, Liliana Reyes y Lourdes González.

Evaluación:

• Exámenes parciales: 70% de la calificación
• Tareas: 30% de la calificación
• Exposición: puntos extra.

De manera opcional, puedes presentar un examen final que vale el 100% de la calificación