Principal

Teoría de la Computación – 1er cuatrimestre de 2021

Licenciatura en Informática con Orientación en Desarrollo de Software

Universidad Nacional de Quilmes

Horarios

Martes de 18:00 a 22:00.

Las clases se publicarán grabadas y habrá encuentros para consultas en vivo (a través de algún medio a convenir).

Docentes

Pablo Barenbaum

pbarenbaum at dc dot uba dot ar

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

Bibliografía básica

• 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.

Bibliografía complementaria

• 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.

Clases

Los números de sección (§) corresponden (aproximadamente) a las secciones del libro de Sipser que cubren los temas de cada clase.

• 06/04 – [§§ 0, 1, 3.1] Introducción a la materia. Máquinas de Turing. [video] Ejercicios: 3.2, 3.8, 3.13, 3.15, 3.16, 3.22.
• 13/04 – [§ 4] Lenguajes decidibles y semi-decidibles (reconocibles). [video] Ejercicios: 4.3, 4.7, 4.16, 4.18.
• 20/04 – [§ 5] Reducibilidad. [video] Ejercicios: 5.4, 5.6, 5.7, 5.12, 5.15, 5.22, 5.24
• 27/04 – [§ 3.2] Otros modelos de cómputo: máquinas de Turing multicinta y no determinísticas. Funciones recursivas de Gödel/Kleene. [video] Ejercicios: 3.18, 3.19
• 04/05 – [§§ 6.3, 6.4] Turing-reducibilidad. Complejidad descriptiva e incompresibilidad. [video] Ejercicios: 6.14, 6.15
• 11/05 – Teorema de Rice. Nociones de teoría de la información. [video]
• 18/05 – [§ 7.1] Complejidad temporal, notación "O". [video] Ejercicios: 7.1, 7.2
• 25/05 – Feriado, Día de la Revolución de Mayo.
• 01/06 – Primer parcial.
• 08/06 – [§§ 7.2, 7.3] Las clases de complejidad P y NP. [video] Ejercicios: 7.6, 7.7, 7.9
• 15/06 – [§ 7.4] NP-completitud, reducciones polinomiales y teorema de Cook–Levin. [video]
• 22/06 – [§ 7.5] Lenguajes NP-completos. [video] Ejercicios: 7.18, 7.20, 7.21
• 29/06 – [§§ 8.1, 8.2, 8.4] Clases de complejidad y su relación. [video]
• 06/07 – Repaso.
• 13/07 – Segundo parcial.
• 16/07 – Finalización de cursada.
• 23/07 – Fecha límite de cierre y entrega de actas.