Objetivo general
Conocer los elementos principales en que se sustenta la teoría de la computación y comprender y aplicar las herramientas empleadas en el diseño de los lenguajes de programación.
TEMARIO
1.
CONCEPTOS MATEMÁTICOS PRELIMINARES
1.1.
Relaciones y funciones.
1.2.
Conjuntos contables y no contables.
1.3.
Definiciones recursivas.
1.4.
Inducción matemática.
2.
LENGUAJES
2.1.
Especificación de un lenguaje.
2.2.
Strings y lenguajes.
2.3.
Expresiones y conjuntos regulares.
3.
TEORÍA DE AUTÓMATAS Y LENGUAJES REGULARES.
3.1.
Autómatas finitos deterministicos.
3.2.
Autómatas no determinísticos.
3.3.
Autómatas finitos y conjuntos regulares.
4.
  .
4.1.
Jerarquía de Chomsky.
4.2.
Gramáticas regulares y autómatas finitos.
4.3.
Gramaticas libres de contexto y lenguajes.
4.4.
Ambigüedad.
4.5.
Autómatas pushdown y lenguajes libres de contexto.
5.
ANÁLISIS DETERMINÍSTICO.
5.1.
Gramáticas LL(k).
5.2.
Top-down parsing.
5.3.
Gramáticas LR(k).
5.4.
Bottom-up parsing.
6.
MÁQUINAS DE TURING.
6.1.
La máquina estándar de Turing.
6.2.
Máquinas de doble cinta.
7.
TÓPICOS AVANZADOS.
7.1.
Decidibilidad.
7.2.
Computabilidad.
7.3.
Problemas P y NP.