Linguagens e Computação
A relação entre as linguagens formais e a computação é o tema desta unidade curricular. São abordados os vários formalismos de representação de linguagens, até ao conceito que deu origem ao computador actual: a máquina de Turing. As noções de decidibilidade, tratabilidade e complexidade computacional estão intimamente relacionadas com este conceito.
1. Linguagens regulares
2. Linguagens independentes do contexto
3. Máquinas de Turing
4. Decidibilidade e tratabilidade
Ao concluir esta unidade curricular o aluno deverá estar capaz de:
Compreender e aplicar os vários tipos de linguagens formais.
Estabelecer relações entre algoritmos/problemas e a sua representação formal em termos de máquina de Turing.
Autómatos.
Expressões e linguagens regulares.
Gramáticas e linguagens independentes do contexto.
Máquinas de Turing.
Decidibilidade e Tratabilidade.
Hopcroft, Motwani & Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd edition. Addison-Wesley. ISBN 0-321-47617-4
E-learning.
O regime de avaliação preferencial é o de avaliação contínua, constituída pela realização de 2 e-folios (trabalhos escritos em formato digital), ao longo do semestre letivo, e de um momento final de avaliação e-fólio Global (e-fólioG), a ter lugar no final do semestre, com peso de, respetivamente, 40% e 60% na classificação final. Os estudantes podem, no entanto, em devido tempo, optar um único momento de avaliação, realizando, então uma prova de Avaliação Final (exame) com o peso de 100%.