MAC0338 Análise de Algoritmos

Por | Em

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.

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.

RESPONSÁVEIS: Arnaldo Mandel, Carlos Eduardo Ferreira, Cristina Gomes Fernades, Paulo Feofiloff, Yoshiharu Kohayakawa.

PRÉ-REQUISITO NO CURRÍCULO DO BCC: MAC0323.

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.

BIBLIOGRAFIA BÁSICA:

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.

OBSERVAÇÃO: Disciplina obrigatória no currículo do BCC.

[Veja dados da disciplina no JúpiterWeb]

Oferecimentos recentes da disciplina: 2000/1, 2001/1, 2002/1, 2010/1