Grao en Enxeñaría Informática |
Asignaturas |
Teoría de la computación |
Contenidos |
|
|
Datos Identificativos | 2014/15 | |||||||||||||
Asignatura | Teoría de la computación | Código | 614G01039 | |||||||||||
Titulación |
|
|||||||||||||
Descriptores | Ciclo | Periodo | Curso | Tipo | Créditos | |||||||||
Grado | 2º cuatrimestre |
Tercero | Optativa | 6 | ||||||||||
|
Tema | Subtema |
Preliminares sobre lenguajes formales | Alfabetos, palabras y lenguajes Lenguajes regulares y expresiones regulares Autómatas finitos |
Lenguajes independientes del contexto y autómatas de pila | Gramáticas regulares Gramáticas regulares y lenguajes regulares Gramáticas independientes del contexto Arboles de derivación y ambigüedad Simplificación de gramáticas independientes del contexto Propiedades de los lenguajes independientes del contexto Algoritmos de análisis sintáctico Autómatas de pila Forma normal de Greibach |
Máquinas de Turing | Definiciones básicas Máquinas de Turing como aceptadoras de lenguajes Construcción de máquinas de Turing Modificaciones de las máquinas de Turing Máquina de Turing universal |
Lenguajes recursivamente enumerables | Lenguajes aceptados por máquinas de Turing Lenguajes regulares e independientes del contexto como lenguajes recursivos Propiedades de los lenguajes recursivos y recursivamente enumerables Gramáticas no restringidas y lenguajes recursivamente enumerables Lenguajes sensibles al contexto y la jerarquía de Chomsky |
Resolubilidad | El problema de la parada El problema de correspondencia de Post Problemas no decidibles en lenguajes independientes del contexto |
Computabilidad | Fundamentos de la teoría de funciones recursivas Alcance de las funciones recursivas primitivas Funciones recursivas parciales El poder de los lenguajes de programación |
|