Teoría de la Computación
En este curso se discuten la naturaleza matemática de la computación y sus limitaciones teóricas. Se dan los principios de la teoría de automátas finitos, determinastas y no deterministas, asi como la clasificación de las gramáticas de Chomsky. Se discuten las Máquinas de Turing y se presenta el problema de decibilidad. Finamente se presentan los fundamentos para las complejidades temporales y espaciales.
Contenido temático
1. Introducción
1.1. Autómatas, Computabilidad y Complejidad
1.2. Nociones Matemáticas y Terminología
a. Conjuntos
b. Funciones, relaciones
c. Pruebas, tipos de pruebas
Parte uno. Autómatas y Lenguajes
2. Lenguajes Regulares
2.1. Autómatas finitos
2.2. Autómatas no-deterministas
2.3. Expresiones regulares y lenguajes
2.4. Lenguajes no-regulares
3. Lenguajes Libres de Contexto
3.1. Gramáticas libres de contexto
3.2. Autómatas de pila (pushdown automaton)
3.3. Lenguajes no-libres de contexto
Parte dos. Teoría de la Computabilidad
4. La Tesis de Church- Turing
4.1. Máquinas de Turing
4.2. Variantes de las Máquinas de Turing
4.3. Definición de algoritmo. El problema de Hilbert
5. Decidibilidad
5.1. Lenguajes decidibles
5.2. Problema de la detención (Halting problem)
5.3. Problemas indecidibles
Parte tres. Teoría de la Complejidad
6. Complejidad como función del tiempo
6.1. Medidas-de complejidad
6.2. La clase P y la clase NP
6.3. NP-completitud
6.4. Algunos problemas NP-completos
7. Complejidad como función del espacio
7.1. Teorema de Savitch
7.2. La clase PSPACE y PSPACE-completitud
7.3. Las clases N, NL Y NL-completitüd
7.4. Jerarquía de la complejidad
Bibliografía básica
° Michael Sipser. 2012. Introduction to the Theory of Computation (3rd ed.). International
Thomson Publishing.
° Harry R. Lewis and Christos H. Papadimitriou. 1997. Elements of the Theory of
Computation (2nd ed.). Prentice Hall PTR, Upper Saddle River, NJ, USA.
° An Introduction to Formal Languages and Automata. Fifth Edition. Peter Linz.
° Peter Linz. 2011. An Introduction to Formal Languages and Automáta (5th ed.). Jones and
Bartlett Publishers, Inc., USA.
Bibliografía complementaria
° John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2006. Introduction to Automata
Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing
Co., Inc., Boston, MA, USA.
° Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; a Cuide to the
Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.
