Datos Identificativos | 2012/13 | |||||||||||||
Asignatura | Teoría da computación | Código | 614G01039 | |||||||||||
Titulación |
|
|||||||||||||
Descriptores | Ciclo | Período | Curso | Tipo | Créditos | |||||||||
Grao | 2º cuadrimestre |
Terceiro | Obrigatoria | 6 | ||||||||||
|
Temas | Subtemas |
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 |
Introducción a la teoría de la complejidad computacional | Complejidad algorítmica Modelo general de cómputo y complejidad computacional Tiempo y espacio en máquinas de Turing Las distintas clases de complejidad Los problemas tratables y no tratables Reducibilidad en tiempo polinómico Problemas NP-completos |