CARRERAS
Licenciatura en Informática-
Contenidos Mínimos
Máquinas de Turing. Máquinas Algorítmicas. Conceptos Básicos de Teoría de Computabilidad y Complejidad: Problemas computables y no computables. Problema de la parada. Problemas tratables e intratables. Conjuntos decidibles, Funciones recursivas. Conjuntos recursivamente enumerables. Reducciones many-one. Clases L, P, PSPACE, NP, NP - completitud. Análisis de Algoritmos: Análisis asintótico, comportamiento en el mejor caso, caso promedio y peor caso. Notación 0(). Balance entre tiempo y espacio en los algoritmos. Análisis de Complejidad de Algoritmos. Teoría de base de datos.
