Teaching GuideTerm Faculty of Computer Science |
Grao en Enxeñaría Informática |
Subjects |
Theoretical Computer Science |
Contents |
|
|
Identifying Data | 2021/22 | |||||||||||||
Subject | Theoretical Computer Science | Code | 614G01039 | |||||||||||
Study programme |
|
|||||||||||||
Descriptors | Cycle | Period | Year | Type | Credits | |||||||||
Graduate | 2nd four-month period |
Third | Optional | 6 | ||||||||||
|
Topic | Sub-topic |
Preliminares sobre linguaxes formais | Alfabetos, palabras e linguaxes Linguaxes regulares e expresións regulares Autómatas finitos |
Linguaxes independentes do contexto e autómatas de pila | Gramáticas regulares Gramáticas regulares e linguaxes regulares Gramáticas independentes do contexto Árbores de derivación e ambigüidade Simplificación de gramáticas independentes do contexto Propiedades das linguaxes independentes do contexto Algoritmos de análise sintáctico Autómatas de pila Forma normal de Greibach |
Máquinas de Turing | Definicións básicas Máquinas de Turing como aceptadoras de linguaxes Construción de máquinas de Turing Modificacións das máquinas de Turing Máquina de Turing universal |
Linguaxes recursivamente enumerables | Linguaxes aceptadas por máquinas de Turing Linguaxes regulares e independentes do contexto como linguaxes recursivas Propiedades das linguaxes recursivas e recursivamente enumerables Gramáticas non restrinxidas e linguaxes recursivamente enumerables Linguaxes sensibles ao contexto e a xerarquía de Chomsky |
Resolubilidade | O problema da parada O problema de correspondencia de Post Problemas non decidibles en linguaxes independentes do contexto |
Computabilidade | Fundamentos da teoría de funcións recursivas Alcance das funcións recursivas primitivas Funcións recursivas parciais O poder das linguaxes de programación |
|