2.1.4 AL/Computabilidad y complejidad básica de autómatas (3 horas Core-Tier1)

Temas:
Core Tier1

• Máquinas de estado finito.
• Expresiones regulares.
• Problema de la parada.

Core Tier2

• Gramáticas libres de contexto.
• Introducción a las clases P y NP y al problema P vs. NP.
• Introducción y ejemplos de problemas NP- Completos y a clases NP-Completos.

Objetivos de Aprendizaje (Learning Outcomes):
Core-Tier1:

1. Discute el concepto de máquina de estado finito [Familiarizarse]
2. Diseñe una máquina de estado finito determinista para aceptar un determinado lenguaje [Usar]
3. Genere una expresión regular para representar un lenguaje específico [Usar]
4. Explique porque el problema de la parada no tiene solucion algorítmica [Familiarizarse]

Core-Tier2:

1. Diseñe una gramática libre de contexto para representar un lenguaje especificado [Usar]
2. Define las clases P y NP [Familiarizarse]
3. Explique el significado de NP-Completitud [Familiarizarse]