Principal

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

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

Universidad Nacional de Quilmes

Horarios

Miércoles de 18:00 a 22:00.

Aula CyT-1.

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.

• 15/03 – [§§ 0, 1, 3.1] Introducción a la materia. Máquinas de Turing. [Práctica 1] [Notas] Ejercicios: 3.2, 3.8, 3.13, 3.15, 3.16, 3.22.
• 22/03 – [§ 4] Lenguajes decidibles y semi-decidibles (reconocibles). [Práctica 2] [Notas] Ejercicios: 4.3, 4.7, 4.16, 4.18.
• 29/03 – [§ 5] Reducibilidad. [Práctica 3] [Notas] Ejercicios: 5.4, 5.6, 5.7, 5.12, 5.15, 5.22, 5.24
• 05/04 – [§ 3.2] Otros modelos de cómputo: máquinas de Turing multicinta y no determinísticas. Funciones recursivas de Gödel/Kleene. [Práctica 4] [Notas] Ejercicios: 3.18, 3.19
• 12/04 – [§§ 6.3, 6.4] Turing-reducibilidad. Complejidad descriptiva e incompresibilidad. [Práctica 5] [Notas] Ejercicios: 6.14, 6.15
• 19/04 – Teorema de Rice. Nociones de teoría de la información. [Notas] [Práctica 6] Ejercicios: 7.1, 7.2
• 26/04 – Repaso.
• 03/05 – Primer parcial.
• 10/05 – [§ 7.1] Complejidad temporal, notación "O". [Notas] [Práctica 7]
• 17/05 – [§§ 7.2, 7.3] Las clases de complejidad P y NP. [Notas] [Práctica 8] Ejercicios: 7.6, 7.7, 7.9
• 24/05 – [§ 7.4] NP-completitud, reducciones polinomiales y teorema de Cook–Levin. [Notas] [Práctica 9]
• 31/05 – [§ 7.5] Lenguajes NP-completos. [Notas] Ejercicios: 7.18, 7.20, 7.21
• 07/06 – [§§ 8.1, 8.2, 8.4] Clases de complejidad y su relación. [Notas]
• 14/06 – Repaso.
• 21/06 – Segundo parcial.
• 28/06 – Recuperatorio del primer parcial.
• 05/07 – Recuperatorio del segundo parcial.
• 14/07 – Finalización de cursada.
• 19/07 – Fecha límite de cierre y entrega de actas.