Cb00003. TEORIA DE LA COMPUTACION.

(3-0-8. Requisito:Haber aprobado Cb00859 o Cb95831. 5 ISC)

==================================================

SISTEMA ITESM

___________________________________________________

Cb00003. TEORIA DE LA COMPUTACION

___________________________________________________

OBJETIVO GENERAL DE LA MATERIA

Al finalizar este curso se espera que el alumno:

Conozca los elementos principales en que se sustenta la teoría de la computación.

Sea capaz de comprender y aplicar las herramientas empleadas en el diseño de los lenguajes de programación.

TEMAS Y SUBTEMAS DEL CURSO

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 determinísticos.

3.2 Autómatas no-determinísticos.

3.3 Autómatas finitos y conjuntos regulares.

4. Teoría de gramáticas.

4.1 Jerarquía de Chomsky

4.2 Gramáticas regulares y autómatas finitos.

4.3 Gramáticas 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.

OBJETIVOS ESPECIFICOS DE APRENDIZAJE POR TEMA

1. Conceptos matemáticos preliminares.

1.1 Relaciones y funciones.

1.1.1 Describir el concepto de relación matemática.

1.1.2 Ejemplificar algunos tipos de relaciones binarias.

1.1.3 Describir el concepto de función en matemáticas discretas.

1.1.4 Definir el dominio y el rango para una función.

1.1.5 Describir algunos tipos de funciones, tales como binarias, n-arias, parciales, etc.

1.1.6 Ejemplificar la aplicación de diversos operadores sobre funciones.

1.1.7 Establecer las diferencias básicas entre relaciones y funciones.

1.2 Conjuntos contables y no-contables.

1.2.1 Definir el concepto de cardinalidad de un conjunto.

1.2.2 Explicar las diferencias básicas que distinguen un conjunto contable de uno no-contable y de uno infinitamente enumerable.

1.3 Definiciones recursivas.

1.3.1 Explicar el concepto de definición recursiva.

1.3.2 Describir cada uno de los componentes esenciales de toda definición recursiva.

1.3.3 Ejemplificar el uso de definiciones recursivas.

1.4 Inducción matemática.

1.4.1 Describir el principio de la inducción matemática.

1.4.2 Explicar cada uno de los componentes de una inducción matemática.

2. Lenguajes.

2.1 Especificación de un lenguaje.

2.1.1 Describir los elementos que conforman la especificación de un lenguaje.

2.2 Strings y lenguajes.

2.2.1 Introducir los conceptos de alfabeto y lenguaje.

2.2.2 Describir a los strings como elementos básicos en la definición de un lenguaje.

2.2.3 Establecer la relación existente entre strings y lenguajes.

2.3 Expresiones y conjuntos regulares.

2.3.1 Introducir el concepto de especificación finita de un lenguaje.

2.3.2 Establecer las principales características de los lenguajes regulares.

2.3.3 Definir el conjunto de operaciones básicas a aplicar sobre lenguajes regulares.

2.3.4 Introducir el concepto de expresión regular.

2.3.5 Explicar la relación que existe entre las expresiones regulares y la definición de lenguajes.

3. Teoría de autómatas y lenguajes regulares.

3.1 Autómatas finitos determinísticos.

3.1.1 Introducir el concepto de diagrama de transiciones o máquina de estados.

3.1.2 Especificar cuáles son los elementos que conforman a una máquina de estados.

3.1.3 Explicar que una máquina de estados (autómata) es útil para generar lenguajes.

3.1.4 Definir los términos: lenguaje generado por un autómata y equivalencia entre autómatas.

3.1.5 Establecer las características particulares de un autómata determinístico.

3.2 Autómatas no-determinísticos.

3.2.1 Especificar las características de autómata no-determinístico

3.2.2 Introducir el concepto de transiciones múltiples y transiciones nulas.

3.2.3 Describir las facilidades que proporcionan este tipo de autómatas para el diseño de ciertos tipos de lenguajes, así como las dificultades que presentan para su automatización.

3.2.4 Explicar cómo puede convertirse un autómata no-determinístico a uno determinístico.

3.3 Autómatas finitos y conjuntos regulares.

3.3.1 Describir la equivalencia que existe entre los autómatas y las expresiones regulares.

3.3.2 Explicar cómo, en forma algorítmica, puede convertirse una expresión regular a su correspondiente autómata no-determinístico.

4. Teoría de gramáticas.

4.1 Jerarquía de Chomsky

4.1.1 Introducir el concepto de gramática.

4.1.2 Decribir cada uno de los elementos que conforman la definición de una gramática.

4.1.3 Explicar los conceptos de símbolo no-terminal o variable sintáctica y de símbolo terminal.

4.1.4 Describir la jerarquía de gramáticas de Chomsky.

4.1.5 Explicar las características particulares de cada tipo de gramática.

4.2 Gramáticas regulares y autómatas finitos.

4.2.1 Analizar las características propias de una gramática regular.

4.2.2 Establecer la equivalencia existente entre una gramática regular y un autómata.

4.2.3 Establecer la equivalencia existente entre una gramática regular y una expresión regular.

4.2.4 Explicar la forma en que se puede convertir una gramática regular a un autómata o a una expresión regular y viceversa.

4.3 Gramáticas libres de contexto y lenguajes.

4.3.1 Analizar las características propias de una gramática libre de contexto.

4.3.2 Establecer la relación que existe entre una gramática libre de contexto y un lenguaje.

4.3.3 Analizar las características de los lenguajes libres de contexto.

4.4 Ambigüedad.

4.4.1 Explicar el concepto de ambigüedad en una gramática.

4.4.2 Decribir cómo afecta la ambigüedad de una gramática al reconocimiento de lenguajes.

4.5 Autómatas PushDown y lenguajes libres de contexto.

4.5.1 Introducir el concepto de autómata pushdown.

4.5.2 Explicar el funcionamiento típico de un autómata pushdown.

4.5.3 Describir cómo un autómata pushdown es utilizado para el reconocimiento de lenguajes libres de contexto.

5. Análisis determinístico.

5.1 Gramáticas LL(k).

5.1.1 Establecer las características particulares de una gramática LL(k).

5.1.2 Explicar el significado de "k" en una gramática LL(k).

5.1.3 Explicar qué características tienen los lenguajes libres de contexto diseñados a partir de una gramática LL(k).

5.2 Top-Down Parsing.

5.2.1 Introducir el concepto de análisis Top-Down.

5.3.1 Explicar cómo trabajan los métodos para realizar un "parsing" de tipo Top-Down.

5.3.2 Ejemplificar los principales métodos top-down.

5.3 Gramáticas LR(k).

5.1.1 Establecer las características particulares de una gramática LR(k).

5.1.2 Explicar el significado de "k" en una gramática LR(k).

5.1.3 Explicar qué características tienen los lenguajes libres de contexto diseñados a partir de una gramática LR(k).

5.4 Bottom-Up Parsing.

5.2.1 Introducir el concepto de análisis Bottom-Up.

5.3.1 Explicar cómo trabajan los métodos para realizar un "parsing" de tipo Bottom-Up.

5.3.2 Ejemplificar los principales métodos bottom-up.

6. Máquinas de Turing.

6.1 La máquina estándar de Turing.

6.1.1 Introducir el concepto de máquina de Turing.

6.1.2 Describir los componentes típicos de máquina de Turing.

6.1.3 Analizar las características particulares de los diferentes tipos de máquinas de turing.

6.1.4 Explicar cómo, las máquinas de turing, son generadoras de lenguajes.

6.2 Máquinas de doble cinta.

6.2.1 Establecer las características particulares de la máquina de doble cinta de turing.

6.2.2 Describir las principales aplicaciones para máquinas de turing.

7. Tópicos avanzados.

7.1 Decidibilidad.

7.1.1 Introducir el concepto de decidibilidad.

7.1.2 Establecer las características principales de los problemas de decibilidad.

7.1.3 Describir las aplicaciones típicas de este tipo de problemas.

7.2 Computabilidad.

7.2.1 Introducir el concepto de computabilidad.

7.2.2 Describir las principales características de los problemas computables y no computables.

7.3 Problemas P y NP

7.3.1 Introducir el concepto de problemas clase .

7.3.2 Describir el problema de complejidad computacional.

7.3.3 Describir las aplicaciones típicas de este tipo de problemas.

METODOLOGIA Y ACTIVIDADES DE APRENDIZAJE

Exposición de los temas en el salón de clase por parte del profesor.

Tareas escritas para promover la práctica de los conceptos.

Autoestudios de temas complementarios.

Aplicación de los conceptos referentes a autómatas y gramáticas, a través de la implementación de programas.

TIEMPO ESTIMADO POR TEMA

1. Conceptos matemáticos preliminares (5 horas).

2. Lenguajes (4 horas).

3. Teoría de autómatas y lenguajes regulares (10 horas).

4. Teoría de gramáticas. (10 horas).

5. Análisis determinístico.(6 horas).

6. Máquinas de Turing. (4 horas).

7. Tópicos avanzados (4 horas).

POLITICAS DE EVALUACION SUGERIDAS

3 exámenes parciales 45%

1 examen final 35%

Tareas, proyectos y exámenes rápidos 20%


LIBRO(S) DE TEXTO

Bibliografía Actualizada

Thomas Sudkamp

Languages and machines (An introduction to the theory of computer science).

Addison Wesley, 1994.

Apoyos Tecnológicos para el curso


LIBRO(S) DE CONSULTA

Dr. Ramón Brena

Teoría de la computación

ITESM, CIA, 1995.

J. Hopcroft, J. Ullman

Introduction to automata theory, languages and computation

Addison Wesley, 1979.

J. Brookshear

Theory of computation

Benjamin Cummings, 1989.

J. Carroll, D. Long

Theory o finite automata

Prentice Hall, 1989.

R. Johnsonbaugh

Matemáticas discretas

Editorial Iberoamericana, 1988.

MATERIAL Y/O SOFTWARE DE APOYO

Compilador de C++

PERFIL DEL MAESTRO

Profesor con maestría en el área de computación, y carrera de computación, preferentemente, con experiencia impartiendo cursos de programación, estructuras de datos y compiladores.