Análise de Algoritmos - 2009/2

Professor: Guilherme Dias da Fonseca
Horário e local: 5^a: 18:30 - 20:30h, na sala 212
6^a: 18:30 - 20:30h, na sala 212
Veja a pseudo-prova e primera prova resolvida.
Segunda pseudo-prova disponível.
Segunda prova no dia 03/12 às 18:00h.
Tópicos

Introdução: problemas, algoritmos, paradigmas, complexidade assintótica de pior caso, recorrências e somatórios.

Busca binária: busca em vetor, busca em vetor ciclicamente ordenado e ponto extremo de polígono convexo.

Divisão e conquista: ordenação, envelope superior, par mais próximo e multiplicação de inteiros.

Simplificação: seleção do k-ésimo e centro de árvore.

Programação dinâmica: maior subsequência crescente, distância de edição e todos os caminhos mais curtos.

Guloso: árvore geradora mínima, fecho convexo, códigos de Huffman...

Busca em grafos: busca em largura, busca em profundidade e aplicações.

NP-completude: Definições, teorema de Cook e reduções polinomiais. (slides)
Bibliografia Recomendada

Apostila do curso disponível nessa página.

Algorithm Design. Jon Kleinberg, Éva Tardos

Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani

Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (possui tradução para o português.

Algorithm Design. Michael T. Goodrich, Roberto Tamassia

Última atualização: 18/11/2009