Autómatas y Lenguajes Formales 2018-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á entendimiento para crear sistemas computacionales más robustos, elegantes y eficientes.

Obtendrás habilidades para expresar de manera más clara y precisa problemas relacionados a computación. También aprenderás muchas técnicas para resolverlos, y tendrás suficiente criterio para saber cuando no es posible resolver un problema utilizando una computadora.

Éste 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)

Luis Felipe Ruíz Castañeda (lruiz@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 (se pueden reponer hasta dos exámenes) - 70% de la calificación

Tareas - 30% de la calificación

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

Exposición - Puntos extra