Jupiterweb

Informações da Disciplina

Preparar para impressão

Júpiter - Sistema de Gestão Acadêmica da Pró-Reitoria de Graduação

Instituto de Matemática e Estatística

Ciência da Computação

Disciplina: MAC0430 - Algoritmos e Complexidade de Computação

Algorithms and Computational Complexity

Créditos Aula:	4
Créditos Trabalho:	0
Carga Horária Total:	60 h
Tipo:	Semestral
Ativação:	01/01/2024	Desativação:

Objetivos

Elaborar o estudo de complexidade computacional iniciado em MAC0414, Autômatos, Computabilidade e Complexidade.

Elaborate on the computational complexity study that was initiated in MAC0414, Automata, Computability and Complexity.

Docente(s) Responsável(eis)

	6901698 - Guilherme Oliveira Mota
	88134 - Yoshiharu Kohayakawa

Programa Resumido

Complexidade de tempo e espaço, algoritmos probabilísticos e de aproximação, provas interativas. O Teorema PCP. Tópicos adicionais: Complexidade de circuitos, Criptografia ou Computação quântica.

Time and space complexity, probabilistic and approximation algorithms, interactive proofs. The PCP Theorem. Additional topics: Circuit Complexity, Cryptography or Quantum Computing.

Programa

O Teorema de Cook--Levin. Complexidade de espaço. Teoremas de hierarquia e diagonalização. A hierarquia polinomial. Algoritmos probabilísticos e de aproximação. Provas interativas. O Teorema PCP. Tópicos adicionais: Complexidade de circuitos, Criptografia ou Computação quântica.

The Cook--Levin Theorem. Space complexity. Hierarchy and diagonalization theorems. The polynomial hierarchy. Probabilistic and approximation algorithms. Interactive tests. The PCP Theorem. Additional topics: Circuit Complexity, Cryptography or Quantum Computing.

Avaliação

Método

Listas de exercícios e provas.

Critério

Média ponderada das notas nas listas e provas.

Norma de Recuperação

Não há recuperação. Justificativa: a avaliação será baseada em um volume substancial de exercícios ao longo do semestre, que terão o papel de levar ao amadurecimento do aluno na área da disciplina. Não é possível reproduzir algo parecido no processo de recuperação, que tem de ter lugar em um período muito curto.

Bibliografia

Bibliografia Básica: 
1. S. Arora e B. Barak, Computational complexity. A modern approach. Cambridge University Press, Cambridge, 2009. xxiv + 579pp. ISBN: 978-0-521-42426-4 
2. M. Sipser, Introduction to the Theory of Computation. Cengage Learning, Boston, MA. 3rd edition, 2013. xxii + 458pp. 
3. C. H. Papadimitriou, Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994. xvi + 523pp. ISBN: 0-201-53082-1 
4. H. R. Lewis, C. H. Papadimitriou, Elementos de Teoria da Computação, 2nd ed., Bookman, 2000.

Clique para consultar os requisitos para MAC0430

Clique para consultar o oferecimento para MAC0430