| Código |
13954
|
| Ano |
3
|
| Semestre |
S2
|
| Créditos ECTS |
6
|
| Carga Horária |
PL(30H)/T(30H)
|
| Área Científica |
Informática
|
|
Objectivos de Aprendizagem |
Existem limites à capacidade de resolução de problemas por um computador:
Para delinear esses limites, visaremos:
• perceber a capacidade de computação das máquinas, assim como os seus limites teóricos. Precisaremos de definir formalmente o que é e o que não é um programa, um algoritmo
• perceber os conceitos que fundamentam as linguagens de programação. Precisaremos de determinar e estudar formalmente as construções que determinam a expressividade (ou capacidade de computação) das linguagens de programação assim como o comportamento dos programas.
Competências por adquirir / Resultados da Aprendizagem:
O aluno deverá ser capaz de perceber e usar a capacidade de computação das máquinas, assim como os seus limites teóricos.
Deverá ser capaz de formalizar adequadamente e avaliar se determinados problemas tem solução computacional ou não.
Deverá perceber e saber usar modelos, técnicas e algoritmos de computação simbólica introduzidos na resolução de problemas informáticos do dia-a-dia.
|
|
Conteúdos programáticos |
1. Apresentação Contextual e Histórica.
2. Linguagens Regulares, expressões regulares, autómatos finitos: propriedades, algoritmos, transformações e limites
3. Ling. Livres de Contexto, gramáticas formais, autómatos de pilha: propriedades, algorit., transf. e limites
4. Teoria das Linguagens Formais: problemas decidíveis e respetivos algoritmos, processamento de linguagens formais, parsing, transformações gramaticais
5.Modelos da computação: dos autómatos às máquinas de Turing. Funções recursivas de Kleene e cálculo lambda. Progr. em modelos da computação
6.Tese de Church-Turing. Provas de equivalência de modelos
7.A não computabilidade e a indecidibilidade: Problemas indecidíveis, técnica da diagonalização, técnica da redução. Lidar com problemas indecidíveis, semi-decisão
8.Complexidade Computacional: definição de classes de compl., hierarquia das cl. de comp. computacionais
9.A NP-Completude: o teorema de Cook, reduções polinomiais, problemas NP-completos, lidar com a NP-Completude
|
|
Metodologias de Ensino e Critérios de Avaliação |
As aulas presenciais são divididas em:
- 2h/semana de aulas T para exposição oral dos conceitos teóricos, métodos e algorit., utilizando-se ainda a escrita no quadro, a discussão de ideias com os alunos, e a projeção de diapositivos;
- 2h/semana de aulas PL, para a aplicação das técnicas/conceitos introduzidos, uso das ferramentas existentes, programação, a construção de provas e raciocínios com base nestas. Em termos e trabalhos e aplicações práticas, visar-se-á dois tipos de aplicações: aplicação destes conceitos a problemas concretos da engenharia informática, e a construção/programação de pequenas aplicações que decorrem dos algoritmos expostos
Será realizada por uma prova escrita e avaliação contínua baseada em exercícios práticos.
NF =Nota final
NCP =Nota da componente prática (soma ponderada da avaliação dos exercícios avaliados)
NCT = Nota da componente teórica (prova escrita - exame ou frequência)
NF= if (NCT >= 6 e NCP >= 6) then (NCT + NCP)/2 else Reprovado/Não Admitido
|
|
Bibliografia principal |
[1] Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1997.
[2] P. Linz. An introduction to formal languages and automata. Jones and Bartlett Publisher, 2006.
[3] M. Sipser. Introduction to the Theory of Computation. PWS Publishing, 2012.
[4] Pierre Wolper. Introduction à la Calculabilité. Dunod, Paris, France, 3 edition, 2006.
[5] Chris Hankin. Lambda Calculi: A Guide for Computer Scientists, volume 3 of Graduate Texts in Computer Science. Clarendon Press, Oxford, 1994.
[6] M. Fernández. Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer, 2009.
[7] J.B. Almeida, M.J. Frade, J.S. Pinto, and S. Melo de Sousa. Rigorous Software Development, An Introduction to Program Verification, volume 103 of Undergraduate Topics in Computer Science. Springer-Verlag, first edition, 307 p. 52 illus. edition, 2011.
|
| Língua |
Português
|