"Ao verificar que um dado programa está muito lento,
uma pessoa prática normalmente pede uma máquina mais rápida ao seu chefe.
[...] Entretanto, o ganho potencial que uma máquina mais rápida pode proporcionar
é tipicamente limitado por um fator de 10, por razões técnicas ou econômicas.
Para obter um ganho maior de desempenho, é preciso buscar melhores algoritmos.
Como veremos adiante, um algoritmo rápido rodando em uma máquina lenta sempre acaba ganhando
para instâncias grandes do problema. Sempre."

— S. S. Skiena, The Algorithm Design Manual

Programa oficial

Segundo o programa oficial, o objetivo da disciplina MAC0338 é

• a análise do desempenho de alguns algoritmos clássicos e
• o estudo de ferramentas de matemática discreta úteis para a análise de algoritmos.

Ainda segundo o programa oficial, o conteúdo da disciplina é o seguinte:

• Matemática Discreta:
  solução de recorrências;
  problemas elementares de enumeração;
  coeficientes binomiais;
  funções geradoras;
  probabilidade discreta;
  elementos de análise assintótica.
  
  
• Análise do Desempenho de alguns algoritmos clássicos de busca, ordenação, manipulação de árvores binárias, hashing, etc. Análise do pior caso e análise do caso médio. Análise do desempenho de alguns algoritmos clássicos sobre grafos.  [Vários desses algoritmos já foram estudados em outras disciplinas, como MAC0122 e MAC0323, mas sem ênfase na análise de desempenho.]

A disciplina tem carga horária semanal de 4 horas de aulas (aproximadamente 30 horas de aulas no semestre) e dá direito a 4 créditos.

Pré-requisitos

MAC0338 não tem pré-requisitos oficiais, mas vou supor que todos os alunos foram aprovados em

MAC0122 (Princípios de Desenvolvimento de Algoritmos).

É muito desejável, também, que todos tenham cursado MAC0323 (Estruturas de Dados) e MAC0328 (Introdução à Teoria dos Grafos).

Bibliografia

Nosso texto básico será CLR:

Th.H. Cormen, Ch.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press & McGraw-Hill, 1991.

É um livro enorme que já se tornou um clássico. Veja o que Ian Parberry diz sobre o livro: "Esse é um excelente livro para quem puder lidar com ele. Escrito no espírito de Aho, Hopcroft e Ullman [The Design and Analysis of Computer Algorithms], o livro não fica "enrolando" o leitor. [. . .]  Contém material suficiente para um curso de algoritmos na graduação e na pós-graduação. É o texto definitivo para aqueles que querem ir direto ao assunto, sem conversa fiada; mas não serve para os medrosos."

Nosso texto auxiliar será o livro de exercícios IP:

I. Parberry, Problems on Algorithms, Prentice Hall, 1995.

Outros livros

Há muitos outros livros sobre o assunto:

• A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1975.
  [Não confunda com Data Structures and Algorithms (1983), dos mesmos autores, que contém uma versão nova dos seis primeiros capítulos do The Design.]
  
  
• R. Sedgewick, Algorithms, 2nd. edition, Addison Wesley, 1988.
  
  
• G. Brassard e P. Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996.
  
  
• U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
  
  
• J. Bentley, Programming Pearls, Addison-Wesley, 1986.
  J. Bentley, More Programming Pearls: Confessions of a Coder, Addison-Wesley, 1988.
  [Palavras do Ian Parberry: "Este delecioso par de livros é uma coletânea de pérolas da coluna de Jon Bentley na [revista] Communications of the ACM. Eles deveriam ser leitura recomendada para todos os alunos de graduação de computação. Bentley explora os problemas e armadilhas do projeto e análise de algoritmos, e dedica especial atenção à implementação e experimentação. Os assuntos escolhidos são um tanto peculiares e pessoais para um livro texto; ainda assim, o par de livros é útil."]
  
  
• J. L. Szwarcfiter e L. Markenzon, Estruturas de Dados e seus Algoritmos, Livros Técnicos e Científicos, 1994.
  
  
• R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.
  Um livro muito interessante, que trata da matemática necessária para a análise de algoritmos. Há uma edição em português (editora Livros Técnicos e Científicos, Rio de Janeiro, 1995), sob o previsível título "Matemática Concreta".