La materia tiene por objetivo
- Que los alumnos comprendan qué es un modelo de cómputo y la equivalencia entre cualquier par de modelos de computo de propósito general (Tesis de Church-Turing) en cuanto a la resolución de problemas.
- Que los alumnos entiendan los límites de la computabilidad y puedan demostrar y entender si un problema es decidible y/o reconocible (recursivamente enumerable).
- Que los alumnos puedan codificar los problemas utilizando lenguajes y entiendan qué es un decisor, qué es un enumerador y cuál es la relación intuitiva entre máquinas de Turing y algoritmos.
- Que los alumnos desarrollen la intuición de la equivalencia entre máquinas de Turing universales con los intérpretes de lenguajes y, en particular, con la arquitectura de Von Neumann.
- Que los alumnos desarrollen tanto una noción informal como formal de problema tratable vs. intratable y comprendan los límites prácticos de la computación.
- Que los alumnos diferencien entre la dificultad de resolver un problema vs. la certificación del mismo y cuál es la relación entre las máquinas de Turing determinísticas y las no-determinísticas.
- Que los alumnos conozcan las clases de complejidad temporal y espacial más comunes (Clases L, NL, P, NP, PSPACE, NPSPACE, EXPTIME), el concepto de completitud en cada clase (especialmente NL, NP y PSPACE), y sus contrapartes hard (NL-hard, NP-hard, PSAPCE-hard), y conozca sus relaciones de inclusión conocidas y desconocidas (en particular P vs NP, L vs. NL, y P vs. EXP).
- Que los alumnos entiendan el concepto de reducción, particularmente la reducción many-to-one y la reducción de Turing, al igual que las reducciones de Karp y Cook y logspace, y puedan comprender cuándo aplicar cada una de ellas.
Modos de Cursada: Cuatrimestral Presencial
Horas Semanales: 4 horas
Demanda de tiempo en casa semanal: 4 horas
Sitio web:
Programa de la materia:
Contenidos Mínimos:
- Máquinas de Turing. Maquinas algorítmicas.
- Problemas computables y no computables
- Problema de la parada.
- Problemas tratables e intratables.
- Conjuntos decidibles, r.e., reducciones many-one.
- Clases L, P, PSPACE, NP, NP-completitud