4.15.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



Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, basado en el modelo de la Computing Curricula de IEEE-CS/ACM