Instructor: Francisco Gómez
Clase: Martes y Jueves (9:00 a 11:00) - Edificio 401 - Salón 205
Programa: Programa
Horario oficina: Martes (11:00-13:00) - Edificio 405 - Ofc. 336
email: fagomezj@gmail.com
website: https://sites.google.com/site/fagomezj/comp_theory
Libros de texto y material guía: Introduction to Automata Theory, Languages, and Computation, 3rd Edition by J. Hopcroft, R. Motwani, and J. Ullman, 2006, Addison-Wesley. Ejercicios y material seleccionado.
Descripción del curso:
La teoría de la computación estudia modelos abstractos de los dispositivos concretos que conocemos como computadores, y analiza lo que se puede y no se puede hacer con ellos. Se estudian diferentes estructuras discretas computacionales incluyendo autómatas, gramáticas, expresiones regulares, máquinas de Turing. Se estudia su poder de cómputo y la relación entre ellas.
Programación
Introducción, autómatas finitos. (Taller1)
Expresiones regulares y lenguajes.
Propiedades de los lenguajes regulares.
Gramáticas libres de contexto y lenguajes
Lema de bombeo.
Propiedades de los lenguajes libres de contexto.
Introducción a las maquinas de Turing.
Indecibilidad.
Problemas intratables.
Recursos
Estrategia de calificación
Tres evaluaciones parciales de 25 % cada una. 25% sistema de puntos.