Complexidade

Código:

CC441

Sigla:

CC441

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

Ocorrência: 2013/2014 - 2S

Ativa?	Sim
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Mestrado Integrado em Engenharia de Redes e Sistemas Informáticos

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	6	PE do Mestrado em Ciência de Computadores	1	-	7,5	67	202,5
MI:ERS	1	Plano de Estudos a partir de 2007	4	-	7,5	67	202,5

Língua de trabalho

Portuguê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$, $PH$, $RP$, $BPP$, $IP$. É dado ênfase especial ao papel que a aleatoriedade desempenha no desenho de algoritmos bem como a técnicas de diminuição da quantidade de aleatoriedade usada por algoritmos aleatórios.

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 randomizados e usar essa informação de forma eficaz.

 

(c) Usar o conceito de provas interativas na análise de problemas de otimização.

 

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 conjuntos recursivos, recursivamente enumeráveis e não computáveis. 2) Classes de Complexidade $P$ e $NP$ Definir as classes de complexidade $P$ e $NP$ usando máquinas de Turing e como um problema de procura. Conhecer as propriedades das classes $P$, $NP$ co-$NP$ e $NP$-c. Interpretar a questão $P$ vs $NP$. 3) 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. Definir a classe $PSPACE$. 4) Classes de Complexidade Aleatorizadas Extensão da noção de eficiência permitindo aos algoritmos o uso de aleatoriedade. Definição de classes de complexidade aleatoriezadas. Nomeadamente $RP$, co-$RP$, $BPP$ e $ZPP$. Definição de geradores de pseudo-aleatórios. 5) Protocolos Interactivos, Classes $IP$, $AM$ e $MA$ 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. 6) Protocolos de Conhecimento Zero Definição de sistemas de prova interactivos de conhecimento zero. Conhecimento zero perfeito, computacional e estatístico e respectivas classes de complexidade. Conhecimento zero: composição sequencial vs repetições paralelas.

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 e aulas práticas com trabalhos práticos.

Avaliação distribuída com dois testes e um relatório final.

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

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

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

A classificação final será a média dos dois testes e o ralatório a realizar.

Provas e trabalhos especiais

Dois testes e relatório final.