6.16.4.1 AL/Computabilidad Básica. (20 horas) [Nivel Bloom 4]

Referencias Bibliográficas: [Kolman, 1997,Kelley, 1995]

Tópicos

  1. Máquinas de estado finito.
  2. Gramáticas libres del contexto.
  3. Problemas tratables e intratables.
  4. Funciones no computables.
  5. El problema de la parada.
  6. Implicaciones de la no-computabilidad.

Objetivos

  1. Discutir el concepto de máquinas de estado finito.
  2. Explicar las gramáticas libres de contexto.
  3. Diseñar una máquina de estados finitos determinística para aceptar un lenguage específico.
  4. Explicar cómo algunos problemas no tienen solución algorítmica.
  5. 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