Sylabus SCM0433

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 (260176 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 (76179 bytes) Conceptos Básicos (112433 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 (137191 bytes) Problemas de Inducción Matemática (117735 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 (65100 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 (176309 bytes) Autómatas finitos determinísticos (99840 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 (171008 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 (161964 bytes) Equivalencia de Expresiones Regulares (293375 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 (160798 bytes)
3. Lenguajes Libres de Contexto 3.1. Gramáticas 3.1.1. Árboles de derivación Cómo dibujar un árbol sintáctico (115712 bytes) Gráficos y Árboles (51200 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 (90112 bytes) Forma Normal de Chomsky (40960 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 (263690 bytes) 3.1.4. Ambigüedad Árboles y gramáticas (50688 bytes) Ambigüedad (38912 bytes) Equivalencia y Ambigüedad (44544 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 (152576 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 (310371 bytes) 3.2.2. Lenguajes no regulares Lenguajes Libres de Contexto (36352 bytes) Ramón, Brena. Autómatas y Lenguajes, un enfoque práctico. Tec de Monterrey. México 2003. pags 136-139 Lema de Bombeo (82145 bytes)
4. Máquinas de Turing 4.1. Diseño 4.1.1. Definición de Máquina de Turing Máquina de Turing (61440 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 (35328 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 (160418 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 (53789 bytes) 4.2.2. Problemas de Hilbert Problemas de Hilbert (904408 bytes)
5. Decibilidad 5.1. Lenguajes Decidibles 5.1.1. Definición Teoria de la Computacion (59392 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 (46592 bytes) Problema de Decisión (29184 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 (25600 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 (39424 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 (44032 bytes) 6.1.2. Un problema simple insoluble Ejemplos de Problemas Insolubles (28672 bytes) 6.2. Funciones Computables 6.2.1. Computabilidad Funciones Computables (71680 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 (164746 bytes)