General
Familiarizar al alumno con los fundamentos teóricos y los métodos básicos de la Ciencia de la Computación, lo que implica plantear y resolver problemas de decisión, comprender y elaborar diversos modelos de computación, apropiados para las aplicaciones que tenga en mente, y comprender los alcances y límites de la computación. Al mismo tiempo, se procurará fortalecer las habilidades del alumno para construir argumentos matemáticos rigurosos.

Específicos

1. Autómatas finitos y lenguajes regulares
1.1. Repaso de los Conceptos Básicos de Autómatas Finitos y Lenguajes Regulares
1.2. Minimización de AFDs. Relaciones de Myhill-Nerode
1.3. El Método de Derivadas
1.4. Aprendizaje de AFDs. El Algoritmo L*
1.5. Homomorfismos
1.6. Bisimulación. Reducción de Autómatas No Deterministas
1.7. Propiedades de Cerradura y Problemas de Decisión de los Lenguajes Regulares
1.8. Transductores. Máquinas de Moore y Mealy
1.9. Minimización de Máquinas de Mealy
2. Autómatas de pila y lenguajes libres de contexto
2.1. Gramáticas y Lenguajes Libres de Contexto (GLCs y LLCs)
2.2. Paréntesis Balanceados
2.3. Simplificación de GLCs. Formas Normales de Chomsky y Greibach
2.4. Autómatas de Pila No Deterministas (APNs)
2.5. Lenguajes Aceptados por APNs. Estado Final vs. Pila vacía
2.6. Autómatas de Pila y Gramáticas Libres de Contexto
2.7. El Algoritmo de Cocke-Younger-Kasami (CYK)
2.8. Lema de Bombeo para Lenguajes Libres de Contexto
2.9. Lenguajes Libres de Contexto Deterministas y APDs
2.10. Propiedades de Cerradura y Problemas de Decisión para LLCs
3. Máquinas de Turing y computabilidad efectiva
3.1. Máquinas de Turing
3.2. Modelos Equivalentes de Máquinas de Turing
3.3. Máquinas de Turing Como Aceptores y Como Transductores
3.4. Máquinas de Turing Universales y Diagonalización
3.5. Problemas Decidibles y No Decidibles. Reducción
3.6. Lenguajes Enumerables Recurrentemente y Lenguajes Recurrentes
3.7. Lenguajes Sensibles al Contexto y Autómatas Lineales Acotados
3.8. La Jerarquía de Chomsky
3.9. El Teorema de Rice
3.10. Más Allá de la Indecidibilidad
3.11. La Tesis de Church-Turing y El Teorema de Incompletud de Gödel
4. Temas adicionales: otros modelos de computación
4.1. Funciones Recurrentes
4.2. Autómatas Celulares y el Juego Life de Conway
4.3. Sistemas de Post, Sistemas de Lindenmayer, Computación con ADN, etc.

1. An Introduction to Formal Languages and Automata (4th. Ed.) por Peter Linz Jones & Bartlett Publishers, 2006.
2. An Introduction to the Theory of Computation (2nd Ed.) por Michael Sipser PWS Publishing Co., 1997.
3. Automata and Computability por Dexter C Kozen Springer-Verlag, New York, 1997.
4. Computability Theory por S. Barry Cooper Chapman and Hall/CRC, 2004.
5. Introducción a la Teoría de Autómatas, Lenguajes y Computación por John E. Hopcroft, et al. Pearson Educación, 2005.
6. Teoría de Autómatas y Lenguajes Formales por Dean Kelley Prentice Hall, 1995.
7. Models of Computation and Formal Languages por R. Gregory Taylor Oxford University Press, 1998.
8. Gödel, Escher, Bach: An Eternal Golden Braid por Douglas R. Hofstadter Basic Books, Inc., 1979.
9. La Nueva Mente del Emperador por Roger Penrose Ed. Grijalbo Mondadori, 1995.
10. A New Kind of Science por Stephen Wolfram, Versión electrónica disponible en la web: www.wolframscience.com, 2002.

• Tareas 15%
• Exámenes 1, 2, 3 70%
• Proyectos 15%
• Total 100%

• Conocimientos:
• Habilidades:
• Actitudes y valores: