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: MAC0338 - Análise de Algoritmos
Analysis of Algorithms

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

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.
 
Consolidate concepts in analysis of correctness and performance of algorithms. Consolidate algorithmic strategies. Develop the capability to design algorithms and estimate their performance. Introduce the basics of the theory of computational complexity.
 
 
Docente(s) Responsável(eis)
58335 - Alair Pereira do Lago
55029 - Cristina Gomes Fernandes
91267 - Jose Coelho de Pina Junior
26472 - Paulo Feofiloff
88134 - 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.
 
Analysis of correctness and performance of algorithms. Amortized analysis of dynamic structures. Algorithm design strategies. Case studies. Introduction to the theory of computational complexity.
 
 
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.
 
Time and space complexity of algorithms. Asymptotic analysis: Oh, Omega, and Theta notation. Worst-case and probabilistic analysis. Amortized analysis of dynamic structures (dynamic tables, union-find, splay trees). Algorithm design paradigms (dynamic programming, divide and conquer, randomization) and analysis methods, Greedy algorithms. Case studies: analysis of the randomized quicksort algorithm, analysis of hash tables, knapsack problem, multiplication of integers (Karatsuba algorithm) and matrices (Strassen algorithm), minimum spanning trees of graphs (Prim and Kruskal algorithms). Sorting lower bound. Introduction to the theory of computational complexity. Reduction between problems. Classes P, NP, and NP-complete. Optional topics: network flows (Ford and Fulkerson algorithm), linear programming, all-pairs shortest paths in graphs (Floyd-Warshall algorithm), approximation algorithms, probabilistic algorithms.
 
 
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.
 

Clique para consultar os requisitos para MAC0338

Clique para consultar o oferecimento para MAC0338

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