115829 Teoría de la Computación
Trimestre 2005 Otoño

Instructores: Dr. Javier Ramírez Rodríguez y Dr. Francisco Javier Zaragoza Martínez.
Inicio y fin del curso: Lunes 19 de septiembre a viernes 2 de diciembre.
Grupo: CMC81 (LMV de 10:00 a 11:30 con FJZM y de 11:30 a 13:00 con JRR).
Asesorías: Lunes y miércoles de 13:00 a 14:30 en la oficina H-252 y de 14:30 a 16:00 en la oficina H-264.
Salón: Por definirse [MCC].
Laboratorio: Por definirse [MCC].

Contenido

Se cubrirá el contenido oficial del curso, el cual se detalla abajo. Al lado de cada tema anotamos el tiempo aproximado que se le dedicará y el instructor correspondiente. Observe que las clases que sean con Francisco Zaragoza serán de 10:00 a 11:30 y las clases que sean con Javier Ramírez serán de 11:30 a 13:00 (a menos que se llegue a algún acuerdo distinto).
  1. Conceptos básicos (2 semanas, JRR).
  2. Autómatas finitos y lenguajes regulares (2 semanas, FJZM).
  3. Autómatas de pila y lenguajes libres de contexto (2 semanas, FJZM).
  4. Máquinas de Turing (2 semanas, FJZM).
  5. Indecidibilidad (1 semana, JRR).
  6. Complejidad (2 semanas, JRR).

Evaluación

Se harán tres evaluaciones de resolución escrita de problemas o ejercicios o preguntas conceptuales y se requerirá la presentación de un proyecto final. La primera evaluación corresponderá con los temas 1 y 2, la segunda con los temas 3 y 4 y la tercera con los temas 5 y 6. Cada una de estas evaluaciones tendrá un valor entero de 0 a 20 puntos, para un total de 60 puntos. El proyecto final tendrá un valor entero de 0 a 40 puntos. Se requiere acumular al menos 60 puntos para acreditar con S, 73 para acreditar con B y 87 para acreditar con MB. No habrá evaluación terminal.

Bibliografía

  1. Gödel, Escher, Bach: An Eternal Golden Braid. Hofstadter. Vintage.
  2. Introduction to Automata Theory, Languages, and Computation. Hopcroft y Ullman. Addison Wesley.
  3. Automata and Formal Languages: An Introduction. Kelly. Prentice Hall. [Libro de texto.]
  4. Elements of the Theory of Computation. Lewis y Papadimitriou. Prentice Hall.
  5. The Theory of Computation. Moret. Addison Wesley.
  6. Introduction to the Theory of Computation. Sipser. PWS Publishing.
La versión más reciente de esta página se puede encontrar en http://ce.azc.uam.mx/profesores/franz/tcm/