Apunte Curso de Fundamentos de la Ciencia de la Computación
(o Teoría de la Computación)

Departamento de Ciencias de la Computación (DCC), Universidad de Chile

(para descargar el apunte, ver al final del documento)

Para celebrar mi décimo año dictando este curso en el Departamento de Ciencias de la Computación de la Universidad de Chile (desde 1996 a 2006, excluyendo mi postdoc en 1999), y con los objetivos de que

este segundo semestre de 2006 redacté un apunte que corresponde en forma muy precisa al material que dicto en este curso. Este apunte reúne mis 10 años de experiencia sobre la mejor forma de dictar un curso que es ciertamente abstracto y difícil de seguir para los alumnos, si se lo compara con los cursos comunes de Computación.

El apunte, de 175 páginas, contiene el material de un curso de pregrado sobre lenguajes formales, computabilidad y complejidad básica. Está dividido en 6 capítulos:

  1. Conceptos Básicos
  2. Lenguajes Regulares
  3. Lenguajes Libres del Contexto
  4. Máquinas de Turing y La Tesis de Church
  5. Computabilidad
  6. Complejidad Computacional
Además del material ordenado en forma lógica, incluye una gran cantidad de ejemplos, figuras, comentarios y notas para motivar los temas y explicar la aplicación y utilidad de los conceptos que se van viendo. Cada capítulo incluye además una guía de ejercicios y las preguntas que se han hecho en controles y exámenes en los años anteriores, los cuales servirán a los alumnos para prepararse para lo que pueden esperar en los que vienen. Finalmente, el apunte tiene al final un índice de materias que facilita buscar cualquier símbolo, definición, teorema, concepto, etc. que se use en el apunte.

Tanto el apunte como el curso siguen bastante fielmente el libro de Lewis y Papadimitriou, aunque hay diferencias en algunas partes, cosas que se eliminan, otras que se agregan, y otras que se ven en otro orden, según mi experiencia en cómo ha resultado mejor. En el último capítulo se desvía más y buena parte se basa en el material del Aho, Hopcroft y Ullman (el verde).

El apunte puede descargarse gratuitamente, incluso si no se es alumno del curso. Me gustaría mucho saber que ha resultado útil para enseñar y aprender esta materia en otras universidades de Chile e Hispanoamérica. Por ello están invitados a descargarlo y usarlo. Sólo pido que me envíen un email de dos líneas a gnavarro@dcc.uchile.cl si lo usan para dictar un curso o para estudiar, para mis registros.

Asimismo, agradeceré me hagan saber de cualquier error que encuentren, por insignificante que parezca (soy muy detallista). Lo corregiré inmediatamente y actualizaré el apunte.

Gonzalo Navarro
DCC, Universidad de Chile
Noviembre de 2006

Creative Commons License
Esta obra está bajo una licencia de Creative Commons.
Descargar el apunte PS.gz PDF (si lo usa fuera del DCC hágamelo saber)