115829 Teoría de la Computación
Trimestre 2009 Invierno
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
19 de enero a viernes 3 de abril de 2009.
Grupo: (lunes,
miércoles y viernes de 14:30
a 16:00).
Asesorías: lunes,
miércoles y viernes de 16:00 a 17:30 en la
oficina H-264.
Salón: E-312.
Cupo: 40 estudiantes incluyendo
a los
oyentes.
Contenido
Se cubrirá el contenido
oficial del curso (el cual se detalla
abajo). Es posible que el temario se cubra en un
orden distinto al allí mencionado.
- Conceptos básicos.
- Autómatas finitos y lenguajes regulares.
- Autómatas de pila y lenguajes libres de contexto.
- Máquinas de Turing.
- Indecidibilidad.
- Complejidad.
Evaluación
Habrá una tarea por cada uno, dos o tres capítulos.
Habrá un
proyecto de programación. No
habrá examen global. Se
requiere obtener
- al menos 60 puntos para acreditar con S,
- al menos 73 puntos para acreditar con B y
- al menos 87 puntos para acreditar con MB.
Las tareas se deberán entregar por correo electrónico a
la cuenta franz
en correo.azc.uam.mx.
Recuerden que, de acuerdo al Reglamento de
Alumnos de la UAM, es falta de los alumnos en contra de la
Institución el suplantar o permitir ser suplantado en la
realización de actividades académicas (Artículo 9)
y se impondrá desde amonestación escrita hasta
suspensión por dos trimestres (Artículo 13).
Calendario
El calendario de clases y de entrega de tareas que
muestro abajo es tentativo e
irá
apareciendo paulatinamente. He anotado los capítulos y secciones
correspondientes del Hopcroft y Ullman, tanto las que cubriré en
clase como las que espero que hayan leído antes de llegar a
clase.
- 19/01: Inicio del curso. Presentación del curso y de las
reglas de
evaluación.
- 21/01: Preliminares [1.1 y 1.5]. Lectura posterior [1.2, 1.3, 1.4
y 1.6].
- 23/01: Autómatas finitos [2.2, 2.3]. Lectura previa [2.1].
- 26/01: Autómatas
finitos con transiciones vacías [2.4].
- 28/01: Expresiones regulares [2.5]. Lectura posterior [2.6, 2.7,
2.8].
- 30/01: Primera sesión de ejercicios. Primera
tarea (para el 06/02).
- 02/02: Lema de bombeo para conjuntos regulares [3.1].
- 04/02: Propiedades de cerradura de conjuntos regulares [3.2].
- 06/02: Algoritmos de decisión para conjuntos regulares
[3.3]. Lectura posterior [3.4].
- 09/02: Gramáticas
libres de contexto [4.2].
Lectura previa [4.1]. Segunda tarea (para el
16/02).
- 11/02: Probablemente no estaré en la UAM.
- 13/02: Probablemente no estaré en la UAM.
- 16/02: Árboles de derivación [4.3].
- 18/02: Simplificación de gramáticas libres de
contexto [4.4].
- 20/02: Formas normales de Chomsky y de Greibach [4.5 y 4.6].
Lectura posterior [4.7].
- 23/02: Segunda sesión de ejercicios. Tercera
tarea (para
el 06/03).
- 25/02: Autómatas de pila [5.2]. Lectura previa [5.1].
- 27/02: Autómatas de pila y lenguajes libres de contexto
[5.3].
- 02/03: Lema de bombeo para lenguajes libres de contexto [6.1].
- 04/03: Día feriado.
- 06/03: Propiedades de cerradura de lenguajes libres de contexto
[6.2].
- 09/03: Algoritmos de decisión para lenguajes libres de
contexto [6.3].
- 11/03: Tercera sesión de ejercicios. Cuarta
tarea (para el
20/03).
- 13/03: Máquinas de Turing [7.2]. Lectura previa [7.1].
- 16/03: Lenguajes computables y funciones [7.3].
- 18/03: Clase cancelada
por causas de fuerza mayor.
- 20/03: Técnicas de construcción de máquinas
de Turing [7.4]. Lectura posterior [7.5, 7.6].
- 23/03: Clase cancelada
por causas de fuerza mayor.
- 25/03: Clase cancelada
por causas de fuerza mayor.
- 27/03: Clase cancelada
por causas de fuerza mayor.
- 30/03: Máquinas de Turing como enumeradores [7.7]. Lectura
posterior [7.8]. Quinta tarea (para el 08/04).
- 01/04: Fin del curso.
- 03/04: Fin del curso.
- Fecha del global: .
Bibliografía
- Gödel, Escher, Bach: An Eternal Golden Braid. Hofstadter.
Vintage.
- Introduction to Automata Theory, Languages, and Computation.
Hopcroft y Ullman. Addison Wesley. [Libro de texto.]
- Automata and Formal Languages: An Introduction. Kelly. Prentice
Hall.
- Elements of the Theory of Computation. Lewis y Papadimitriou.
Prentice Hall.
- The Theory of Computation. Moret. Addison Wesley.
- Introduction to the Theory of Computation. Sipser. PWS Publishing.