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

Créditos | Fale conosco
© 1999 - 2024 - Superintendência de Tecnologia da Informação/USP