Programa

• Notação Assintótica
• Divisão e Conquista
• Algoritmos Gulosos
• Programação Dinâmica
• Análise Amortizada
• Algoritmos e Estruturas de Dados Aleatorizados
• Algoritmos de Aproximação
• Busca Exaustiva

Objetivo

Apresentar um conjunto de técnicas de análise de algoritmos, considerando o recurso consumido, os casos de execução e notação assintótica.

• Explicar o que se entende pelos casos "melhor", "esperado" e "pior" do comportamento de um algoritmo.
• Identificar as características, condições ou suposições que levam a comportamentos diferentes de algoritmos.
• Determinar a complexidade do tempo de algoritmos simples.
• Contrastar classes de complexidade linear, quadrática, logarítmica e exponencial.
• Usar formalmente a notação O, Ômega e Teta para fornecer limitantes assintóticos e de caso esperado na complexidade de tempo de algoritmos.
• Usar relações de recorrência para determinar a complexidade do tempo de algoritmos recursivamente definidos.
• Resolver relações de recorrência com notação assintótica.

Avaliação

Duas provas, além da prova final.

Calendário

• Início: 01/02/2022
• Término: 12/05/2022
• 23 encontros
• O professor estará em viagem de 14 a 23 de fevereiro
• 01/03/2022: Recesso de carnaval
• 31/03/2022: Primeira prova
• 21/04/2022: Feriado de Tiradentes
• 05/05/2022: Segunda prova
• 12/05/2022: Prova final

Notas e Avaliação

Veja suas notas aqui.

Material de leitura e exercícios

Os números do tipo "[nn]" se referem a itens da bibliografia. Lista ainda em construção.

• Exercícios
• Introdução à Análise de Algoritmos
  • [1], cap 1 e 2
  • [2], cap 2
  • [3], cap 0
• Notação Assintótica
  • [1], cap 3
  • [2], sec. 2.2
  • [3], sec 0.3
• Divisão e Conquista
  • [1], cap 4
  • [2], cap 5
  • [3], cap 2
• Algoritmos Gulosos
  • [1], cap 16
  • [2], cap 4
  • [3], cap 5
• Programação Dinâmica
  • [1], cap 15
  • [2], cap 6
  • [3], cap 6
• Análise Amortizada
  • [1], cap 17
• Algoritmos e Estruturas de Dados Aleatorizados
  • [1], cap 5
  • [2], cap 13
• Algoritmos de Aproximação
  • [1], cap 35
  • [2], cap 11

Bibliografia

[1] Introduction to Algorithms. Third Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. 2009.

[2] Algorithm Design. Jon Kleinberg e Éva Tardos. 2005.

[3] Algorithms. S. Dasgupta, C. H. Papadimitriou e U. Vazirani. McGraw Hill. 2006

Bibliografia complementar

[4] Donald E. Knuth. The art of computer programming, volume 3: (2nd ed.) sorting and searching. Redwood City, CA, USA: Addison Wesley Longman Publishing Co., Inc., 1998. ISBN : 0-201-89685-0.

[5] Udi Manber. Introduction to Algorithms: A Creative Approach. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1989. ISBN : 0201120372.

[6] Robert Sedgewick. Algorithms in C. Addison-Wesley, 1990, p. 657.

[7] Michael Mitzenmacher e Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. New York, NY, USA: Cambridge University Press, 2005. ISBN : 0521835402.

[8] Robert Sedgewick e Philippe Flajolet. An Introduction to the Analysis of Algorithms. 512 pages. (ISBN 0-201-40009-X). Addison-Wesley Publishing Company, 1996.