Ciencias de la Computación (plan 1994) 2012-2

Quinto Semestre, Teoría de la Computación

Teoría de la computación (grupo 7015)

Profesora: Laura Freidberg Gojman

lfreidberg@yahoo.com

Lunes y miércoles de 17:00 a 18:30 hrs. salón P 213

Ayudante: Juan Germán Castañeda Echevarría juanger@ciencias.unam.mx

Martes y jueves de 16:00 a 17:00 hrs. salón O 129

Temario:

1.- Fundamentos

2.- Máquinas con un número finito de estados y sus equivalencias

3.- Gramáticas y lenguajes formales

4.- Autómatas de finitos y lenguajes tipo 3

5.- Autómatas de stack

6.- Lenguajes libres del contexto

7.- Propiedades de los lenguajes libres del contexto

8.- Máquinas de Turing

Calificación:

4 exámenes parciales 65%

14 tareas semanales35%

Los exámenes serán los días: 29 de febrero, 28 de marzo, 2 de mayo y 23 de mayo.

A los alumnos que hayan presentado los 4 exámenes se les promediarán los tres más altos. Si no presentan alguno, se promediarán los cuatro (incluyendo cero en los exámenes no presentados). Los exámenes tendrán una duración de una hora. No habrá reposiciones ni examen final.

Bibliografía:

Libro de texto:Viso, E. “Introducción a la teoría de la computación (autómatas y lenguajes formales)”Facultad de ciencias, UNAM. 2008.

Consulta:John E. Hopcroft, Rajeev Motwani, and Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, second edition edition, 2001.

Peter Linz. An Introduction to Formal Languages and Automata. D.C. Heath and Company, fourth edition, 2006.