2.3.5 AL/Computabilidad Básica. (6 horas)
Tópicos
- Máquinas de estado finito.
- Gramáticas libres del contexto.
- Problemas tratables e intratables.
- Funciones no computables.
- El problema de la parada.
- Implicaciones de la no-computabilidad.
Objetivos
- Discutir el concepto de máquinas de estado finito.
- Explicar las gramáticas libres de contexto.
- Diseñar una máquina de estados finitos determinística para aceptar un lenguage específico.
- Explicar cómo algunos problemas no tienen solución algorítmica.
- Proveer ejemplos que ilustren el concepto de no-computabilidad.
Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, Universidad Católica San Pablo, Arequipa-Peru
basado en el modelo de la Computing Curricula de IEEE-CS/ACM
