Autómatos e Linguagens Formais (CC4089)
Objectivo O objetivo desta UC é o estudo das linguagens formais e da teoria dos autómatos, juntamente como a apresentação de alguns desenvolvimentos recentes assim como problemas relevantes em aberto.
O estudante deverá ser capaz de utilizar linguagens formais e a teoria dos autómatos para descrever formalmente linguagens formais (por exemplo linguagens de programação) ou de modelos computacionais simples. O estudante deverá também ser capaz de comparar diferentes modelos formais no que diz respeito ao poder computacional e à complexidade das suas descrições. Também compreender a diversidade de aplicações dos autómatos e a vantagem de ter algoritmos comuns para aplicar em áreas muito diferentes.
Resultados de aprendizagem e competências O programa explora as principais classes de linguagens e os seus modelos computacionais que caracterizam diferentes poderes expressivos e complexidades dos sistemas computacionais. A ênfase na complexidade descritiva corresponde a temas de pesquisa recentes na área. Modelos de autómatos de árvore são usados em diversas aplicações, como tecnologias XML, como esquema, transformações e linguagens de pesquisa. Os transdutores podem ser usados no processamento de linguagem natural e na teoria de códigos. Automatos podem modelar diversos problemas de bioinformática e processamento de imagens. Os alunos deverão compreender as diversas representações para linguagens formais e operações, e a sua relativa complexidade descritiva e computacional, bem como a diversidade de aplicações dos autómatos e a vantagem de ter algoritmos comuns para aplicar em áreas muito diferentes.
O estudante deverá ser capaz de utilizar linguagens formais e a teoria dos autómatos para descrever formalmente linguagens formais (por exemplo linguagens de programação) ou de modelos computacionais simples. O estudante deverá também ser capaz de comparar diferentes modelos formais no que diz respeito ao poder computacional e à complexidade das suas descrições. Também compreender a diversidade de aplicações dos autómatos e a vantagem de ter algoritmos comuns para aplicar em áreas muito diferentes.
Resultados de aprendizagem e competências O programa explora as principais classes de linguagens e os seus modelos computacionais que caracterizam diferentes poderes expressivos e complexidades dos sistemas computacionais. A ênfase na complexidade descritiva corresponde a temas de pesquisa recentes na área. Modelos de autómatos de árvore são usados em diversas aplicações, como tecnologias XML, como esquema, transformações e linguagens de pesquisa. Os transdutores podem ser usados no processamento de linguagem natural e na teoria de códigos. Automatos podem modelar diversos problemas de bioinformática e processamento de imagens. Os alunos deverão compreender as diversas representações para linguagens formais e operações, e a sua relativa complexidade descritiva e computacional, bem como a diversidade de aplicações dos autómatos e a vantagem de ter algoritmos comuns para aplicar em áreas muito diferentes.