Teoría de la Computación
Teóricas
Guías de ejercicios
Parciales
Programa
- Unidad 0: Repaso.
Técnicas de demostración: directa, por la contrarrecíproca, por el absurdo, por inducción. Estructuras: palabras, grafos, conjuntos. Lenguajes y autómatas.
- Unidad 1: Concepto de algoritmo.
Máquinas de Turing (determinística, multi-cinta, no determinística) y sus equivalencias. Máquinas de Turing universales. Funciones recursivas primitivas y recursivas generales. de Church–Turing.
- Unidad 2: Decidibilidad.
Lenguajes decidibles (computables) y semi-decidibles (computablemente enumerables). Método de diagonalización.
- Unidad 3: Reducibilidad.
Turing-reducibilidad. Autómatas linealmente acotados (LBAs) y reducibilidad por historial de cómputos. Reducibilidad funcional ("many-one").
- Unidad 4: Complejidad temporal.
Complejidad temporal, notación O, clases de complejidad determinísticas y no determinísticas. Clases P, NP, co-NP. NP-completitud y NP-completitud fuerte. Teorema de Cook–Levin. Reducciones à la Cook y à la Karp.
- Unidad 5: Complejidad espacial.
Clases de complejidad determinísticas y no determinísticas. Teorema de Savitch. Clases PSPACE, EXPTIME. Problemas PSPACE-completos y métodos de reducción. Clases L y NL. Problemas NL-completos y reducciones logspace.
Bibliografía
- Michel Sipser. Introduction to the theory of computation (2nd ed.). Cengage Learning, 2012.
- Arnold L. Rosenberg. The Pillars of Computation Theory: State, Encoding, Nondeterminism. Springer Science &et; Business Media, 2009.
- Alan M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem, en Proceedings of the London Mathematical Society. Addison Wesley, 1936.
- Michel Garey y David Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, 1979.