Disciplina
Informações da Disciplina

 Preparar para impressão 
Júpiter - Sistema de Graduação

Instituto de Matemática e Estatística
 
Ciência da Computação
 
Disciplina: MAC0338 - Análise de Algoritmos

Créditos Aula: 4
Créditos Trabalho: 0
Tipo: Semestral

Objetivos
Consolidar conceitos de análise da correção e do desempenho de algoritmos. Consolidar estratégias algorítmicas. Desenvolver a habilidade de projetar algoritmos e estimar seu desempenho. Introduzir noções da teoria da complexidade computacional.
 
Docente(s) Responsável(eis)
Alair Pereira do Lago
Cristina Gomes Fernandes
Jose Coelho de Pina Junior
Paulo Feofiloff
Yoshiharu Kohayakawa
 
Programa Resumido
Análise da correção e do desempenho de algoritmos. Análise amortizada de estruturas dinâmicas. Paradigmas de projeto de algoritmos. Estudo de casos. Introdução à complexidade computacional.
 
Programa
Complexidade de tempo e espaço de algoritmos. Análise assintótica: notação O, Ômega e Teta. Análise de pior caso e análise probabilística. Análise amortizada de estruturas dinâmicas (tabelas dinâmicas, union find, splay trees). Paradigmas de projeto de algoritmos (programação dinâmica, divisão e conquista, aleatorização) e métodos de análise. Algoritmos gulosos. Estudo de casos: análise do algoritmo quicksort aleatorizado, análise de tabelas de hashing, problema da mochila, multiplicação de inteiros (algoritmo de Karatsuba) e matrizes (algoritmo de Strassen), árvores geradoras mínimas de grafos (algoritmos de Prim e Kruskal). Cota inferior de ordenação. Introdução à teoria da complexidade computacional. Redução entre problemas. As classes P, NP, e NP-completo. Tópicos opcionais: fluxo em redes (algoritmo de Ford-Fulkerson), programação linear, todos os caminhos mínimos num grafo (algoritmo de Floyd-Warshall), algoritmos de aproximação, algoritmos probabilísticos.
 
Avaliação
 
      Método
      média ponderada de provas e exercícios.
 
      Critério
      Média ponderada de provas e exercícios.
 
      Norma de Recuperação
      média ponderada da primeira e da segunda avaliação.
 
Bibliografia
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., McGraw-Hill, 2001.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Algoritmos, 3a. ed., Elsevier, 2013.
S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani, Algorithms, McGraw-Hill, 2007.
J. Kleinberg, É. Tardos, Algorithm Design, Addison-Wesley, 2005.
D.E. Knuth, The Art of Computer Programming, vols. 1 e 3, Addison-Wesley, 1973.
 
Requisitos
Os Requisitos variam conforme o curso para o qual ela é oferecida.

Clique para consultar o oferecimento para MAC0338.

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