4.16.5.1 Computabilidad y complejidad básica de autómatas (20 horas) [Habilidades a]

Referencias Bibliográficas: [Martin, 2010,Linz, 2011,Sipser, 2012] Temas
  1. Máquinas de estado finito.
  2. Expresiones regulares.
  3. Problema de la parada.
  4. Gramáticas libres de contexto.
  5. Introducción a las clases P y NP y al problema P vs. NP.
  6. Introducción y ejemplos de problemas NP- Completos y a clases NP-Completos.
  7. Máquinas de Turing, o un modelo formal equivalente de computación universal.
  8. Máquinas de Turing no determinísticas.
  9. Jerarquía de Chomsky.
  10. La tesis de Church-Turing.
  11. Computabilidad.
  12. Teorema de Rice.
  13. Ejemplos de funciones no computables.
  14. Implicaciones de la no-computabilidad.
Objetivos de Aprendizaje
  1. Discute el concepto de máquina de estado finito [Evaluar]
  2. Diseñe una máquina de estado finito determinista para aceptar un determinado lenguaje [Evaluar]
  3. Genere una expresión regular para representar un lenguaje específico [Evaluar]
  4. Explique porque el problema de la parada no tiene solucion algorítmica [Evaluar]
  5. Diseñe una gramática libre de contexto para representar un lenguaje especificado [Evaluar]
  6. Define las clases P y NP [Evaluar]
  7. Explique el significado de NP-Completitud [Evaluar]
  8. Explica la tesis de Church-Turing y su importancia [Familiarizarse]
  9. Explica el teorema de Rice y su importancia [Familiarizarse]
  10. Da ejemplos de funciones no computables [Familiarizarse]
  11. Demuestra que un problema es no computable al reducir un problema clásico no computable en base a él [Familiarizarse]

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