Este curso es una introducción a la Teoría de la Computación a través de los lenguajes formales. Nos enfocaremos en los modelos más sencillos de sistemas de cómputo y su relación con lenguajes: automatas finitos/pushdown automata y lenguajes regulares / context free grammars.

Estos modelos simples de cómputo estan en todas partes (por ejemplo controlan las puertas automáticas de los supermercados asi como muchos de los robots que hacen posible la producción industrial moderna) y tienen una teoría muy bien desarrollada y completa. Por esas dos razones juegan un papel preponderante en la Teoría de la Computación.

En el curso aprenderán las equivalencias que existen entre algunos de estos modelos simples de cómputo y adquirirán las habilidades necesarias para poder diseñarlos y manipularlos algorítmicamente.

Textos: La referencia principal del curso seran las notas del instructor. Estas se basarán en los siguientes libros de referencia (complementarios entre si):

• [S] Sipser Michael: Introduction to the Theory of Computation (MIT). Thomson Course Technology (2006).
• [LP] Lewis Harry y Papadimitriou Christos: Elements of the Theory of Computation (MIT). Prentice-Hall (1998).

Metodología y Evaluación:

La mayor parte de lo que aprenderán en este curso será el resultado de su propio trabajo en dos aspectos de igual importancia: Reflexión posterior a cada clase sobre los resultados discutidos en ella, trabajo en los talleres Prácticos asignados clase a clase.

Los criterios de evaluación del curso son:

• El 50% de la nota será determinado por talleres prácticos a ser realizados en grupos de a lo más tres estudiantes (ver fechas de entrega de los prácticos abajo, marcados con la letra [P]). Todos los prácticos tienen una participación igual en el 50%.
• El 50% restante de la nota será determinado por dos exámenes parciales individuales (25% cada uno) a ser realizados en clase en las fechas marcadas abajo.
• Hay un 5% adicional (optativo) para todo grupo que entregue al menos el 50% de sus prácticos en LaTex. LaTex es el lenguaje de la comunicación científica asi que vale la pena aprenderlo. Pueden encontrar un tutorial breve de LaTex en este [link] ó en este [otro link].

• La nota final se decidirá calculando el promedio ponderado de las notas como en los párrafos anteriores, redondeando al entero más cercano y convirtiéndolo a la escala oficial: S: 96-100 MB: 91-95, BMB: 83-90, B: 75-82, R: 41-74, D: 0-40.

Instructor:

• Mauricio Velasco