4.23.5.2 Teoría de la Computabilidad (20 horas) [Habilidades a,b,1]

Referencias Bibliográficas: [Sipser, 2012,Kelley, 1995] Temas

1. Problema de la parada.
2. Introducción a las clases P y NP y al problema P vs. NP.
3. Introducción y ejemplos de problemas NP- Completos y a clases NP-Completos.
4. Máquinas de Turing, o un modelo formal equivalente de computación universal.
5. Máquinas de Turing no determinísticas.
6. Jerarquía de Chomsky.
7. La tesis de Church-Turing.
8. Computabilidad.
9. Teorema de Rice.
10. Ejemplos de funciones no computables.
11. Implicaciones de la no-computabilidad.

Objetivos de Aprendizaje

1. Explique porque el problema de la parada no tiene solucion algorítmica [Assessment]

2. Define las clases P y NP [Assessment]
3. Explique el significado de NP-Completitud [Assessment]
4. Explica la tesis de Church-Turing y su importancia [Familiarity]
5. Explica el teorema de Rice y su importancia [Familiarity]
6. Da ejemplos de funciones no computables [Familiarity]
7. Demuestra que un problema es no computable al reducir un problema clásico no computable en base a él