|
Teaching GuideTerm Faculty of Computer Science |
| Grao en Enxeñaría Informática |
 Subjects |
| Theoretical Computer Science |
| Contents |
|
|
| Identifying Data | 2019/20 | |||||||||||||
| 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 |
|
