Complementos de Complexidade Computacional
Código
9644
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
Oleksiy Karlovych
Língua de ensino
Português
Objectivos
No final desta unidade curricular o estudante terá adquirido conhecimentos, aptidões e competências avançadas na área de complexidade computacional que lhe permitam:
- Compreender conteúdos avançados na área;
- Ser capaz de executar investigação num tópico da área.
Conteúdo
Modelos de computação: sequenciais, não-deterministas e paralelos.
Classes de complexidade computacional (como FPtime, P, NP, PH, Pspace, FPspace, NC^k, NC, AC^k, AC, Logspace, entre outras).
Caracterizações independentes de máquinas: caracterização de Cobham para FPtime, de Thompson para FPspace, de Clote para classes paralelas, etc.
Caracterizações implícitas.
Bibliografia
S. Bellantoni, Predicative Recursion and Computational Complexity. Ph. D. Dissertation, University of Toronto, 1993.
S. Buss and P. Scott, Feasible Mathematics, Birkhäuser, 1990.
N. Immerman, Descriptive Complexity, Springer, 1999.
C.H. Papadimitirou, Computational Complexity, Addison-Wesley, 1994.