4.18.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 [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]