Información general
INGENIERO EN INFORMÁTICA (Plan1994)
Departamento de Informática e Ingeniería de Sistemas
Área de Lenguajes y Sistemas Informáticos
Breve descripción:
Introducción a la complejidad y computabilidad de problemas.
Créditos 4,5
Período de impartición: cuatrimestre de otoño
Tipo: Troncal
Las clases se impartirán de septiembre a enero.
Lenguajes, Gramáticas y Autómatas, Estructuras de Datos y Algoritmos, Matemática Discreta.
Profundizar en el estudio de la clasificación y complejidad de los problemas, iniciado en la asignatura de Lenguajes, Gramáticas y Autómatas. Establecer la distinción fundamental entre problemas resolubles e irresolubles. Adquirir los rudimentos de las teorías de complejidad y calculabilidad de algoritmos. Obtener la capacidad de demostrar la indecidibilidad de un problema y tener una idea de la tratabilidad de los problemas decidibles.
Parte I: Calculabilidad:
1. Preliminares. Numerabilidad y diagonalización.
2. Problemas y datos. La máquina RAM.
3. Otros modelos de cálculo.
4. Lenguajes recursivos y enumerables recursivamente.
5. Reducciones. El teorema de Rice.
6. Indecidibilidad.
1. Medidas de complejidad.
2. Tiempo polinómico y exponencial.
3. Algunos problemas importantes. La clase NP.
4. Reducciones en tiempo polinómico.
5. Los problemas NP-completos.
6. Demostraciones de NP-completitud.
Etiquetas: contenidos
