Complexidade

Código:

CC441

Sigla:

CC441

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

Ocorrência: 2011/2012 - 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	7	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
M:M	0	PE do Mestrado em Matemática	1	-	7,5	67	202,5
			2
M:MAO	2	PE Mestrado em MAOPI	1	-	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.

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

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Participação presencial (estimativa)	Participação presencial	63,00
1º teste	Exame	2,00		2012-04-19
2º teste	Exame	2,00		2012-05-24
Apresentação trabalho	Trabalho escrito			2012-05-30
	Total:	-	0,00

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

A classificação final será a média dos dois testes a realizar e do trabalho de revisão de um artigo científico

Provas e trabalhos especiais

Dois testes e um trabalho de revisão