NOMBRE DE LA MATERIA: CC209 TEORÍA DE LA COMPUTACIÓN.
TIPO: CURSO TEÓRICO.
CARACTER DEL CURSO: OBLIGATORIO.
ÁREA DE FORMACIÓN: BÁSICA PARTICULAR.
PREREQUISITOS: MATEMÁTICAS DISCRETAS.
DEPTO. DE ADSCRIPCIÓN: CIENCIAS COMPUTACIONALES.
CARGA HORARIA GLOBAL: 80 HORAS.

CARGA HORARIA SEMANAL: 4 HORAS.
VALOR EN CRÉDITOS: 11 CRÉDITOS.


OBJETIVO GENERAL.
APLICAR LOS MODELOS MATEMÁTICOS PROPIOS DE ESTE CURSO PARA REPRESENTAR POR MEDIO DE LOS MISMOS, CIERTOS SISTEMAS DEL MUNDO REAL, ENFOCANDO EL CONOCIMIENTO DE MANERA PRINCIPAL A OBTENER LOS ANTECEDENTES NECESARIOS PARA PODER IMPLEMENTAR LAS ETAPAS DE ANÁLISIS DE UN COMPILADOR.

OBJETIVOS ESPECÍFICOS:
SE MENCIONAN EN CADA MÓDULO DEL CONTENIDO TEMÁTICO PRINCIPAL.

CONTENIDO TEMÁTICO PRINCIPAL.
Módulo 1. Gramáticas y lenguajes formales.
Objetivo: Comprender la forma en la que los lenguajes de programación se pueden asociar con la teoría matemática para su mejor entendimiento y un diseño eficiente.

1.1 Conceptos generales.
1.2 Diseño de Gramáticas.
1.3 Forma normal de Backus.
1.4 Jerarquía de Chomsky.BR> 1.5 Arboles de derivación.
1.6 Conceptos específicos.
1.7 Aplicación en el diseño de compiladores.
1.8 Forma normal de Chomsky.

Módulo 2. Máquinas de estado finito.
Objetivo: Comprender la gran cantidad de aplicaciones que pueden tener estos modelos matemáticos, sobre todo en las áreas de la computación y la electrónica. 2.1 Concepto.
2.2 Representación.
2.3 Aplicaciones.

Módulo 3. Autómatas de estado finito.
Objetivo: Obtener las bases necesarias para el diseño de analizadores lexicográficos y comprender la gran variedad de aplicaciones que se pueden representar con este tipo de Autómatas. 3.1 Concepto.
3.2 Relación y diferencias con las Máquinas de Estado Finito.
3.3 Implementación del software.
3.4 Aplicaciones en general.
3.5 Aplicaciones en electrónica.
3.6 Aplicaciones en inteligencia artificial.
3.7 Autómatas Finitos: deterministas y no deterministas.
3.8 Relación entre Autómatas Finitos y Gramáticas Regulares.
3.9 Expresiones regulares.
3.10 Limitaciones de los Autómatas de Estado Finito.

Módulo 4. Autómatas de pila.
Objetivo: Obtener las bases para el diseño de estos dispositivos, especialmente para aplicarse como analizadores sintácticos en un compilador. 4.1 Concepto.
4.2 Relación entre Autómatas de Pila y Gram. Libres de Contexto.
4.3 Limitaciones de los Autómatas de Pila.

Módulo 5: Máquinas de Turing.
Objetivo: Conocer el poder computacional de estas máquinas en el contexto de la solución de problemas de reconocimiento de lenguajes. 5.1 Concepto.
5.2 Máquinas de Turing como aceptadores de Lenguajes.
5.3 Construcción de Máquinas de Turing.
5.4 El problema de la parada.

Módulo 6. Computabilidad.
Objetivo: Entender que el diseño de algoritmos presenta limitaciones en ciertos casos, que impiden su representación adecuada. 6.1 Complejidad de los cálculos.
6.2 Complejidad de los algoritmos.
6.3 Complejidad de los problemas.
6.4 Problemas NP.
6.5 Problemas irresolubles.

BIBLIOGRAFÍA BÁSICA. - Teoría de Autómatas y Lenguajes Formales. Dean Kelley. Editorial Prentice Hall.
- Introd. a la Teoría de Autómatas, Lenguajes y Computación. John E. Hopcroft y Jeffrey D. Ullman. Editorial CECSA.
-Teoría de la Computación. J. Glenn Brookshear. Editorial Addison Wesley Iberoamericana.

BIBLIOGRAFÍA COMPLEMENTARIA. - Compiladores. Alfred V. Aho , Ravi Sethi y Jeffrey D. Ullman. Editorial Addison Wesley Iberoamericana.
- Matemáticas Discretas. Richard Johnsonbaugh. Editorial Iberoamericana.
- Lenguajes de Programación Ravi Sethi. Editorial Addison Wesley.
- Introducción a las Ciencias de la Computación J. Glenn Brookshear Editorial Addison Wesley.
Como comentario adicional se puede decir que otros textos con títulos semejantes a los cuatro anteriores, pueden ser considerados como parte de esta bibliografía complementaria.

MODALIDAD DE ENSEÑANZA Y APRENDIZAJE. En virtud de que el contenido del curso es adecuado para que el alumno desarrolle su creatividad, se recomienda que se le asesore para que pueda utilizar su iniciativa para descubrir la solución a los problemas con los que se habrá de encontrar. Además se le pueden solicitar tareas de investigación que hagan que el curso avance en forma más fluida.

MATERIAL DE APOYO ACADÉMICO.
- Notas sobre el curso.
- Acetatos.
- Fuentes de consulta en Internet.
- Aplicaciones desarrolladas por los alumnos de cursos anteriores.

CRITERIOS DE EVALUACIÓN. Se evaluará a lo largo del periodo escolar mediante exámenes parciales departamentales, implementación de software, tareas y un proyecto final.
En caso de no haber obtenido una calificación aprobatoria en el curso ordinario, se presentará un examen extraordinario departamental.

CRITERIOS DE CALIFICACIÓN. La calificación final se compone de los siguientes aspectos:
- 25% Primer Exámen Parcial Departamental.
- 25% Segundo Exámen Parcial Departamental.
- 25% Implementación del Software.
- 10% Tareas (investigaciones y problemas).
- 15% Proyecto Terminal (investigación de aplicación).

CRITERIOS DE ACREDITACIÓN. - Obtener por lo menos 60 puntos totales acumulados de un máximo de 100 puntos posibles.
- Conseguir un promedio mínimo de 60 (sobre 100) en los dos exámenes parciales.
- Presentar funcionando correctamente por lo menos el 80% de los proyectos que corresponden a la implementación de software, además del proyecto terminal.

COMPETENCIAS QUE SE PUEDEN ADQUIRIR. - Obtención de los conocimientos necesarios para la elaboración de la etapa de análisis de un compilador.
- Habilidad para implementar modelos matemáticos a partir de sistemas de tipo electrónico o computacional.
- Conocimiento más profundo sobre la computabilidad de los algoritmos.

APLICACIÓN PROFESIONAL. Comprender la importancia de la teoría matemática en aplicaciones prácticas relacionadas con su campo de estudio.