4.16.2.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 [Assessment]
2. Diseñe una máquina de estado finito determinista para aceptar un determinado lenguaje [Assessment]
3. Genere una expresión regular para representar un lenguaje específico [Assessment]
4. Explique porque el problema de la parada no tiene solucion algorítmica [Assessment]
5. Diseñe una gramática libre de contexto para representar un lenguaje especificado [Assessment]
6. Define las clases P y NP [Assessment]
7. Explique el significado de NP-Completitud [Assessment]
8. Explica la tesis de Church-Turing y su importancia [Familiarity]
9. Explica el teorema de Rice y su importancia [Familiarity]
10. Da ejemplos de funciones no computables [Familiarity]
11. Demuestra que un problema es no computable al reducir un problema clásico no computable en base a él [Familiarity]