3.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 (Familiarity)]
2. Diseñe una máquina de estado finito determinista para aceptar un determinado lenguaje [Usar (Usage)]
3. Genere una expresión regular para representar un lenguaje específico [Usar (Usage)]
4. Explique porque el problema de la parada no tiene solución algorítmica [Familiarizarse (Familiarity)]

Core-Tier2:

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