Teoría de la Computación – 2022c1, UNQ

Principal

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

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

Universidad Nacional de Quilmes

Horarios

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

Salvo las primeras dos semanas, las clases serán presenciales.

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

Bibliografía complementaria

Clases

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