Computabilidade e Complexidade
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Ciência de Computadores |
Ocorrência: 2023/2024 - 2S ![Requerida a integração com o Moodle Ícone do Moodle](/fcup/pt/imagens/MoodleIcon)
Ciclos de Estudo/Cursos
Língua de trabalho
Português
Objetivos
Estudo e comparação de vários modelos de computação
(Turing-completos), do seu poder computacional e das suas limitações. Estudo das diversas classes de complexidade computacional.
Ao completar este curso espera-se que os alunos
- conheçam os modelos de computação clássicos utilizados no estudo da computabilidade de diversos problemas;
- saibam provar a equivalência de vários modelos Turing-completos;
- conheçam os resultados e métodos mais importantes no estudo da computabilidade e complexidade;
- saibam classificar exemplos concretos de problemas e provar a sua (in)decidibilidade dentro das diversas classes de computabilidade.
- saibam classificar elemplos concretos pelas sua complexidade temporal e interpretar essa classificação.
Resultados de aprendizagem e competências
Os alunos são expostos a vários dos modelos de computação Turing-completos standard, como as máquinas de registo, máquinas de Turing e as funções recursivas. Para além da prova da equivalência dos diferentes modelos, estes são também utilizados para identificar diferentes problemas indecidíveis. São usadas diferentes técnicas, como o método da diagonalização e da redução entre linguagens. Para adquirirem experiência em identificar a complexidade computacional de problemas concretos, faz-se uma introdução às classes P e NP, completude NP e o teorema de Cook, voltando também à técnica da redução.
Modo de trabalho
Presencial
Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)
Conhecimentos de alguns modelos de computação como Autómatos finitos, Expressões regulares e Gramáticas independentes. Conhecimentos básicos de Lógica.
Programa
Noção de linguagem/problema (semi-)decidível.
Revisão de alguns modelos de computação (DFA's, NFA's, CFG's e PDA's) e do seu poder computacional.
Máquinas de Turing. Máquinas de registo. Funções Recursivas. Lambda Calculus. Tese de Church-Turing.
Hierarquia de Chomsky. Teorema da Recursão de Kleene. Método da diagonalização e indecidibilidade do problema
da paragem. Redução "muitos para um" entre linguagens.
Introdução à teoria de complexidade: classes P e NP; completude em NP; teorema de Cook e outros problemas NP-completos. reduções polinomiais.
Classes co-NP, etc.
A classe dos problemas PSPACE.
Bibliografia Obrigatória
Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullmann.
Recursion theory, Phillips, in Handbook of logic in computer science (vol. 1), Oxford University Press.
Bibliografia Complementar
Introduction to the Theory of Computation, Michael Sipser.
Models of Computation - An Introduction to Computability Theory, Maribel Fernández.
Oded Goldreich; P, NP, and NP-Completeness - The Basics of Computational Complexity, Cambridge University Press, 2010
Métodos de ensino e atividades de aprendizagem
Aulas teóricas de exposição dos conteúdos programáticos.
Aulas práticas de resolução de exercícios propostos semanalmente.
Tipo de avaliação
Avaliação distribuída sem exame final
Componentes de Avaliação
Designação |
Peso (%) |
Teste |
100,00 |
Total: |
100,00 |
Componentes de Ocupação
Designação |
Tempo (Horas) |
Estudo autónomo |
114,00 |
Frequência das aulas |
48,00 |
Total: |
162,00 |
Obtenção de frequência
Sem critérios de frequência.
Fórmula de cálculo da classificação final
Primeiro teste (50% de peso na nota final).
Segunto teste (50% de peso na nota final).
Sendo PT a classificação obtida no teste intercalar e ST a
classificação obtida no exame final, então a nota final é dada por:
F = PT*(0.5) + ST*(0.5)
PT,ST >= 6 e F >= 9.5
Não obterão aprovação na avaliação distribuída, os alunos que não obtiverem um mínimo de 6 valores (em 20), em ambos os testes e um mínimo de 9.5 valores de nota final.
Para os alunos que não obtiverem aprovação, haverá um exame de recurso, cotado para 20 valores.
Adicionalmente poderão ser propostos projectos laboratoriais, sendo o peso desses projectos na classificação final a determinar pelo docente responsável.