Syllabus

SCM0433 Teoría de la computación

DR. JOSE LUIS LIRA TURRIZA

jlira@itescam.edu.mx

Semestre Horas Teoría Horas Práctica Créditos Clasificación
4 3 2 8

Prerrequisitos
MATEMATICAS PARA COMPUTADORA: 1) Realizar operaciones de Conjuntos. 2) Validar problemas matemáticos por medio de unducción matemática. 3) Diseñar grafos dirigidos a partir de un problema planteado.
FUNDAMENTOS DE PROGRAMACION: 1) Manejar los conceptos de Programación, Lenguaje de Programación y Código Fuente 2) Ejecutar y diseñar algoritmos en la resolución de problemas.

Competencias Atributos de Ingeniería

Normatividad
1. Presentar los ejercicios en la hora y el día programados
2. Respetar a sus compañeros en sus comentarios

Materiales
No se requieren materiales adicionales a los especificados en la programación de clases.

Bibliografía disponible en el Itescam
Título
Autor
Editorial
Edición/Año
Ejemplares

Parámetros de Examen
PARCIAL 1 De la actividad 1.1.1 a la actividad 2.2.2
PARCIAL 2 De la actividad 3.1.1 a la actividad 3.2.2

Contenido (Unidad / Competencia / Actividad / Material de Aprendizaje)
1. Introducción
          1.1. Conceptos Básicos
                   1.1.1. Autómatas
                           Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pag 6 ( bytes)
                           http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito#Definici.C3.B3n_formal
                          
                   1.1.2. Nociones Matemáticas
                           Juan Manuel, Cueva Lovelle. 2001. Lenguajes, Gramáticas y Autómatas. Segunda Edición. Universidad de Oviedo. Pag. 3
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. Pags 3-11
                           Introducción ( bytes)
                           Conceptos Básicos ( bytes)
                          
          1.2. Métodos de Validación
                   1.2.1. Inducción Matemática
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. Pags 15-16
                           Carlos Chinea. Sobre la Inducción Matemática. Junio de 2003 ( bytes)
                           Problemas de Inducción Matemática ( bytes)
                           http://es.wikipedia.org/wiki/Inducci%C3%B3n_matem%C3%A1tica
                          
                   1.2.2. Técnica de lo Absurdo
                           Método de lo Absurdo ( bytes)
                           http://es.wikipedia.org/wiki/Reducci%C3%B3n_al_absurdo
                          
2. Lenguajes Regulares
          2.1. Autómatas Finitos
                   2.1.1. Determinísticos
                           Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pags 59-66
                           Unidad II. Lenguajes Regulares ( bytes)
                           Autómatas finitos determinísticos ( bytes)
                           http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito#Definici.C3.B3n_formal
                          
                   2.1.2. No Determinísticos
                           Autómatas finitos no determinísticos ( bytes)
                           Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pags 66-70
                           Unidad II.Lenguajes Regulares. Autómatas No Determinísticos ( bytes)
                           http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito#Definici.C3.B3n_formal
                          
          2.2. Expresiones regulares
                   2.2.1. Operaciones
                           Juan Manuel Cueva Lovelle. 2001. Lenguajes, Gramáticas y Autómatas. 2a Edición. Universidad de Oviedo. 29-33
                           Ramón Brena. 2003. Autómatas y Lenguajes, Un enfoque de Diseño. Tec. de Monterrey. 81-83
                           Expresiones Regulares ( bytes)
                           Equivalencia de Expresiones Regulares ( bytes)
                          
                   2.2.2. Lenguajes No Regulares
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 100-104
                           Lenguajes Regulares ( bytes)
                          
3. Lenguajes Libres de Contexto
          3.1. Gramáticas
                   3.1.1. Árboles de derivación
                           Cómo dibujar un árbol sintáctico ( bytes)
                           Gráficos y Árboles ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 95-97,111-122
                           Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pags 7-10
                          
                   3.1.2. Formas Normales
                           Forma Normal de Greibach ( bytes)
                           Forma Normal de Chomsky ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 132-136
                          
                   3.1.3. Recursividad
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 123-124
                           Recursividad ( bytes)
                          
                   3.1.4. Ambigüedad
                           Árboles y gramáticas ( bytes)
                           Ambigüedad ( bytes)
                           Equivalencia y Ambigüedad ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 124-125
                          
          3.2. Autómatas Push-Down
                   3.2.1. Lenguajes Libres de Contexto
                           Autómatas de Pila y Lenguajes Libres de Contexto ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 145-149
                           Cueva Lovelle. Lenguajes, Gramáticas y Autómatas.Departamento de Informática, Universidad de Oviedo. España 2001. pags 49-58
                           Lenguajes Libres de Contexto ( bytes)
                          
                   3.2.2. Lenguajes no regulares
                           Lenguajes Libres de Contexto ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 136-139
                           Lema de Bombeo ( bytes)
                          
4. Máquinas de Turing
          4.1. Diseño
                   4.1.1. Definición de Máquina de Turing
                           Máquina de Turing ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 169-174
                          
                   4.1.2. Construcción modular
                           Construccion Modular ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 178-180
                          
                   4.1.3. Lenguajes Aceptados
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pag 192-194
                           Lenguajes Aceptados ( bytes)
                          
          4.2. Lenguajes
                   4.2.1. Variantes de una máquina de Turing
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pag 184
                           Variaciones de las MT ( bytes)
                          
                   4.2.2. Problemas de Hilbert
                           Problemas de Hilbert ( bytes)
                          
5. Decibilidad
          5.1. Lenguajes Decidibles
                   5.1.1. Definición
                           Teoria de la Computacion ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 139-140,181-182
                          
                   5.1.2. El problema de Halting
                           Problema de Correspondencia de Post ( bytes)
                           Problema de Decisión ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 191-192
                          
          5.2. Teorías Lógicas
                   5.2.1. Decidibilidad
                           Decibilidad ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 184-186
                          
                   5.2.2. Lenguajes
                           Teoría de la Computación ( bytes)
                           http://delta.cs.cinvestav.mx/~gmorales/complex/node78.html
                          
6. Reducibilidad
          6.1. Teoría de Lenguajes
                   6.1.1. Problemas insolubles para la teoría de lenguajes
                           Problema de la Parada ( bytes)
                          
                   6.1.2. Un problema simple insoluble
                           Ejemplos de Problemas Insolubles ( bytes)
                          
          6.2. Funciones Computables
                   6.2.1. Computabilidad
                           Funciones Computables ( bytes)
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 179-181
                          
                   6.2.2. Reducibilidad de Turing
                           Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 47-53
                           Reducibilidad e Indecibilidad ( bytes)
                          

Prácticas de Laboratorio (20212022P)
Fecha
Hora
Grupo
Aula
Práctica
Descripción

Cronogramas (20212022P)
Grupo Actividad Fecha Carrera

Temas para Segunda Reevaluación