Complexidade Computacional

Código:

CC4011

Sigla:

CC4011

Nível:

400

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2024/2025 - 2S

Ativa?	Sim
Página Web:	https://www.dcc.fc.up.pt/~rvr/aulas/CC2425/
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Mestrado em Ciência de Computadores

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
M:CC	3	PE a partir do ano letivo de 2014	1	-	6	42	162
M:ECAD	0	Plano Oficial do ano letivo 2021/2022	2	-	6	42	162
M:F	3	Plano de Estudos Oficial.	1	-	6	42	162

Língua de trabalho

Português e inglês

Objetivos

Nesta unidade curricular pretende-se expôr aos alunos técnicas que provem ou sugiram que não existem métodos eficientes para resolver alguns problemas importantes em Ciência de Computadores com impacto na vida real (nomeadamente a factorização). Neste sentido é feito um estudo teórico de várias classes de complexidade, das relações entre elas, tais como: P, NP, co-NP, PSPACE, NL, PH, RP, BPP,  e IP. 

Resultados de aprendizagem e competências

Após a conclusão deste curso, o aluno será capaz de:

 

(a) Distinguir entre classes de complexidade.

 

(b) Classificar problemas de decisão em classes de complexidade apropriadas, incluindo P, NP, PSPACE e classes de complexidade com base em modelos de máquinas randomizadas e usar essa informação de forma eficaz.

  

Modo de trabalho

Presencial

Programa

1. Motivação e Revisões. Reconhecer o papel da Complexidade Computacional como área científica da Ciência de Computadores. Saber a definição de máquina de Turing. Definir problemas decidíveis, semidecidíveis e não decidíveis.


2. Classes de Complexidade e teoremas de hierarquia.


3. As classes P e NP. Definir as classes de complexidade P e NP usando máquinas de Turing e como um problema de procura. Problemas completos para uma classe. Conhecer as propriedades das classes P, NP, co-NP e NP-c. Interpretar a questão P vs NP. 


4. A Hierarquia Polinomial e a classe PSPACE. Definir máquinas de Turing com acesso a um oráculo. Definir a hierarquia polinomial (PH) via máquinas de Turing com oráculo e via quantificadores. Alternância. PSPACE e Jogos.


5. Classe L e NL. Reduções em espaço logarítmico


6. Classes de complexidade não uniforme. Circuitos Booleanos e P/poly.  Máquinas de Turing com aviso. Limites inferiores.


7. Classes de Complexidade Aleatorizadas. Extensão (Ampliação) da noção de eficiência permitindo aos algoritmos o uso de aleatoriedade. Definição de classes de complexidade aleatorizadas, nomeadamente RP, co-RP, BPP e ZPP. Definição de geradores de pseudo-aleatórios.


8. Protocolos interactivos. Definição de sistemas de prova interactivos e classes de complexidade IP, AM e MA. Propriedades das classes de complexidade atrás referidas. Reconhecer o papel fundamental da aleatoriedade em protocolos interactivos.

Bibliografia Obrigatória

Sanjeev Arora and Boaz Barak; Complexity Theory: A Modern Approach
Oded Goldreich; Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008. ISBN: 978-0-521-88473-0

Bibliografia Complementar

Michael Garey and David Johnson; Computers and intractability: A guide to NP-Completeness, W. H. Freeman, 1979. ISBN: 0716710455
C. Papadimitriou; Computational complexity, Addison Wesley Longman, 1994. ISBN: 0201530821
D.Z. Du and K.I. Ko; Theory of Computational Complexity, John Wiley and Sons, 2000. ISBN: 978-0-471-34506-0

Métodos de ensino e atividades de aprendizagem

Aulas teóricas.

Avaliação distribuída.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Teste	100,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Frequência das aulas	42,00
Estudo autónomo	120,00
Total:	162,00

Obtenção de frequência

A avaliação será efectuada com base num conjunto de dois testes (com nota mínima de 1/3 em cada).

Fórmula de cálculo da classificação final

A classificação final (CF) corresponde à média das classificações dos testes.

Avaliação especial (TE, DA, ...)

Exame final

Melhoria de classificação

Exame final