Lenguajes Formales, Autómatas y Computabilidad

De Cuba-Wiki
Revisión del 17:46 30 oct 2024 de Laura (discusión | contribs.)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)
Esta página es sobre la materia del plan de estudios 2023. Para ver la materia del plan 1993, consultar Teoría de Lenguajes.
Lenguajes Formales, Autómatas y Computabilidad
Año Segundo año
Carga horaria 5 horas semanales
Correlativas Algoritmos y Estructuras de Datos
Correlativa de Complejidad Computacional

Lenguajes Formales, Autómatas y Computabilidad es una materia obligatoria de la Licenciatura en Ciencias de la Computación. Su objetivo es introducir al alumnado en las estructuras de autómatas y los lenguajes que estas estructuras pueden definir, junto con aspectos de computabilidad de problemas.

Programa

  • Lenguajes
  • Autómatas finitos
  • Lema de pumping y clausura para lenguajes regulares
  • Expresiones regulares
  • Autómatas de pila
  • Gramáticas
  • Funciones primitivas recursivas
  • Funciones computables
  • Indecibilidad. Diagonalización.
  • Reducciones. Teoremas del Parámetro, de la Recursión y de Rice.

Prácticas

TPs

Parcial

Parcial único