Teoría de la Computación

Teóricas

• [Clase 01] [video] Introducción a la materia. Máquinas de Turing.
• [Clase 02] [video] Lenguajes decidibles y semi-decidibles (reconocibles).
• [Clase 03] [video] Reducibilidad.
• [Clase 04] [video] Otros modelos de cómputo: máquinas de Turing multicinta y no determinísticas. Funciones recursivas de Gödel/Kleene.
• [Clase 05] [video] Turing-reducibilidad. Complejidad descriptiva e incompresibilidad.
• [Clase 06] [video] Teorema de Rice. Nociones de teoría de la información.
• [Clase 07] [video] Complejidad temporal, notación "O".
• [Clase 08] [video] Las clases de complejidad P y NP.
• [Clase 09] [video] NP-completitud, reducciones polinomiales y teorema de Cook–Levin.
• [Clase 10] [video] Lenguajes NP-completos.
• [Clase 11] [video] Clases de complejidad y su relación.

Guías de ejercicios

• Práctica 1
• Práctica 2
• Práctica 3
• Práctica 4
• Práctica 5
• Práctica 6
• Práctica 7
• Práctica 8
• Práctica 9

Parciales

• 2021p1
• 2021p2
• 2022p1
• 2022p2
• 2023p1
• 2023p2
• 2024p1
• 2024p2

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.