Introducción a la teoría de la computación

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

  1. Introducción, autómatas finitos. (Taller1)

  2. Expresiones regulares y lenguajes.

  3. Propiedades de los lenguajes regulares.

  4. Gramáticas libres de contexto y lenguajes

  5. Lema de bombeo.

  6. Propiedades de los lenguajes libres de contexto.

  7. Introducción a las maquinas de Turing.

  8. Indecibilidad.

  9. Problemas intratables.

Recursos

Estrategia de calificación

Tres evaluaciones parciales de 25 % cada una. 25% sistema de puntos.