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:

  • Aún no disponible

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