Teoria da Computação

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
Esta informação promove os seguintes Objetivos de Desenvolvimento Sustentável da ONU:
Garantir o acesso à educação inclusiva, de qualidade e equitativa, e promover oportunidades de aprendizagem ao longo da vida para todos