Especialización en Procesadores del Lenguaje

Módulo 1. Informática Teórica

1.1. Conceptos matemáticos utilizados

1.1.1. Introducción a la lógica proposicional
1.1.2. Teoría de relaciones
1.1.3. Conjuntos numerables y no numerables

1.2. Lenguajes y gramáticas formales e introducción a las máquinas de Turing

1.2.1. Lenguajes y gramáticas formales
1.2.2. Problema de decisión
1.2.3. La máquina de Turing

1.3. Extensiones para las máquinas de Turing, máquinas de Turing restringidas y computadoras

1.3.1. Técnicas de programación para las máquinas de Turing
1.3.2. Extensiones para las máquinas de Turing
1.3.3. Máquinas de Turing restringidas
1.3.4. Máquinas de Turing y computadoras

1.4. Indecibilidad

1.4.1. Lenguaje no recursivamente enumerable
1.4.2. Un problema indecidible recursivamente enumerable

1.5. Otros problemas indecibles

1.5.1. Problemas indecidibles para las máquinas de Turing
1.5.2. Problema de correspondencia de Post (PCP)

1.6. Problemas intratables

1.6.1. Las clases P y NP
1.6.2. Un problema NP completo
1.6.3. Problema de la satisfacibilidad restringido
1.6.4. Otros problemas NP completos

1.7. Problemas co-NP y PS

1.7.1. Complementarios de los lenguajes de NP
1.7.2. Problemas resolubles en espacio polinómico
1.7.3. Problemas PS completos

1.8. Clases de lenguajes basados en la aleatorización

1.8.1. Modelo de la MT con aleatoriedad
1.8.2. Las clases RP y ZPP
1.8.3. Prueba de primalidad
1.8.4. Complejidad de la prueba de primalidad

1.9. Otras clases y gramáticas

1.9.1. Autómatas finitos probabilísticos
1.9.2. Autómatas celulares
1.9.3. Células de McCullogh y Pitts
1.9.4. Gramáticas de Lindenmayer

1.10. Sistemas avanzados de cómputo

1.10.1. Computación con membranas: sistemas P
1.10.2. Computación con ADN
1.10.3. Computación cuántica

Módulo 2. Teoría de Autómatas y Lenguajes Formales

2.1. Introducción a la teoría de autómatas

2.1.1. ¿Por qué estudiar teoría de autómatas?
2.1.2. Introducción a las demostraciones formales
2.1.3. Otras formas de demostración
2.1.4. Inducción matemática
2.1.5. Alfabetos, cadenas y lenguajes

2.2. Autómatas finitos deterministas

2.2.1. Introducción a los autómatas finitos
2.2.2. Autómatas finitos deterministas

2.3. Autómatas finitos no deterministas

2.3.1. Autómatas finitos no deterministas
2.3.2. Equivalencia entre AFD y AFN
2.3.3. Autómatas finitos con transiciones ϵ

2.4. Lenguajes y expresiones regulares (I)

2.4.1. Lenguajes y expresiones regulares
2.4.2. Autómatas finitos y expresiones regulares

2.5. Lenguajes y expresiones regulares (II)

2.5.1. Conversión de expresiones regulares en autómatas
2.5.2. Aplicaciones de las expresiones regulares
2.5.3. Álgebra de las expresiones regulares

2.6. Lema de bombeo y clausura de los lenguajes regulares

2.6.1. Lema de bombeo
2.6.2. Propiedades de clausura de los lenguajes regulares

2.7. Equivalencia y minimización de autómatas

2.7.1. Equivalencia de AF
2.7.2. Minimización de AF

2.8. Gramáticas independientes de contexto (GIC)

2.8.1. Gramáticas independientes de contexto
2.8.2. Árboles de derivación
2.8.3. Aplicaciones de las GIC
2.8.4. Ambigüedad en las gramáticas y lenguajes

2.9. Autómatas a pila y GIC

2.9.1. Definición de los autómatas a pila
2.9.2. Lenguajes aceptados por un autómata a pila
2.9.3. Equivalencia entre autómatas a pila y GIC
2.9.4. Autómata a pila determinista

2.10. Formas normales, lema de bombeo de las GIC y propiedades de los LIC

2.10.1. Formas normales de las GIC
2.10.2. Lema de bombeo
2.10.3. Propiedades de clausura de los lenguajes
2.10.4. Propiedades de decisión de los LIC

Módulo 3. Procesadores de Lenguajes

3.1. Introducción al proceso de compilación

3.1.1. Compilación e interpretación
3.1.2. Entorno de ejecución de un compilador
3.1.3. Proceso de análisis
3.1.4. Proceso de síntesis

3.2. Analizador léxico

3.2.1. ¿Qué es un analizador léxico?
3.2.2. Implementación del analizador léxico
3.2.3. Acciones semánticas
3.2.4. Recuperación de errores
3.2.5. Cuestiones de implementación

3.3. Análisis sintáctico

3.3.1. ¿Qué es un analizador sintáctico?
3.3.2. Conceptos previos
3.3.3. Analizadores descendentes
3.3.4. Analizadores ascendentes

3.4. Análisis sintáctico descendente y análisis sintáctico ascendente

3.4.1. Analizador LL(1)
3.4.2. Analizador LR(0)
3.4.3. Ejemplo de analizador

3.5. Análisis sintáctico ascendente avanzado

3.5.1. Analizador SLR
3.5.2. Analizador LR (1)
3.5.3. Analizador LR (k)
3.5.4. Analizador LALR

3.6. Análisis semántico (I)

3.6.1. Traducción dirigida por la sintaxis
3.6.2. Tabla de símbolos

3.7. Análisis semántico (II)

3.7.1. Comprobación de tipos
3.7.2. El subsistema de tipos
3.7.3. Equivalencia de tipos y conversiones

3.8. Generación de código y entorno de ejecución

3.8.1. Aspectos de diseño
3.8.2. Entorno de ejecución
3.8.3. Organización de la memoria
3.8.4. Asignación de memoria

3.9. Generación de código intermedio

3.9.1. Traducción dirigida por la síntesis
3.9.2. Representaciones intermedias
3.9.3. Ejemplos de traducciones

3.10. Optimización de código

3.10.1. Asignación de registros
3.10.2. Eliminación de asignaciones muertas
3.10.3. Ejecución en tiempo de compilación
3.10.4. Reordenación de expresiones
3.10.5. Optimización de bucles