Pré-Req: MC202 MC348/ MC202 MS328

Ementa

Técnicas de projeto e análise de algoritmos. Algoritmos de ordenação e algoritmos básicos para problemas em grafos.

Programa

Conteúdo

Tópicos de cobertura obrigatória:
(legenda: M=Modelo, A=Análise, P=Projeto/Paradigma)

1. Revisão de conceitos

Modelos Computacionais

O que é análise de um algoritmo

O que é quota inferior de um problema

- Exemplos: busca em vetor ordenado, entrada/saída

2. (A) Ferramental Matemático para Análise de Algoritmos

Crescimento de Funções e Notação Assintótica

Relações de Recorrência: resolução assintótica e exata.

3. (P) Projeto de algoritmos por indução

Indução Matemática e Projetos de algoritmos por indução.

Projetos por Indução Simples e Forte.

Projetos por Divisão e Conquista. 
Sugestões: [Manber] 2.7, 2.8, 2.10, 5.2, 5.3, 5.4, 5.5, 5.7, 5.8, 5.9, 6.11.1, 6.11.2

4. Busca, ordenação e estatísticas de ordem (exemplos)

(P) busca binária (simples, variações, seqüências gaguejantes, n=a^b para n, a, b naturais)

(P) paradigma de divisão e conquista (mergesort, busca binária, mediana)

(P) conquista pode preceder a divisão (quicksort)

(A) análise de caso médio de quicksort

(P) seleção do mediano e do k-ésimo menor elemento via partição do quicksort

(A) algoritmo de pior caso linear para seleção do mediano e do k-ésimo menor elemento

(P) benefícios da escolha de estrutura de dados adequada para projeto de algoritmos eficientes (ordenação com várias estruturas de apoio)

(A) quota inferior para busca em vetor ordenado, ordenação e mediana

(M/A/P) Algoritmos lineares para ordenação

5. Programação Dinâmica

Pelo menos 2 exemplos dentre os seguintes

- (P) Multiplicação de cadeias de matrizes

- (P) Mais longa subseqüência comum

- (P) Árvore binária de busca ótima

6. Algoritmos Gulosos

Pelo menos 2 exemplos. Sugestões:

- (P) Problema da seleção de atividades

- (P) Códigos de Huffman

7. Algoritmos em Grafos

- Revisão de definições básicas

- Representação de Grafos

- (P) Busca em profundidade

- (P) Busca em largura

- (P) Ordenação topológica

- (P) Árvore Geradora Mínima: Algoritmos Gulosos de Prim e Kruskal.
            NOTA: apresentar Kruskal com "union-find", introduzindo análise amortizada.

- (P) Caminhos Mínimos com uma única fonte: Algoritmo Guloso de Dijkstra.  

Tópicos opcionais à escolha do docente:

Fluxos em Redes

Emparelhamento de cadeias de caracteres e biologia computacional

Aritmética de ponto flutuante

Operações sobre matrizes

Algoritmos paralelos

Transformanda rápida de Fourier

Análise amortizada

Busca em tempo contante (hashing)

Caminhos Mínimos entre todos os vértices e detecção de ciclo negativo: Algoritmo de Programação Dinâmica de Floyd-Warshall

Projeto de programação enfatizando diferenças entre comportamento assintótico de um algoritmo e seu desempenho com entradas realistas.

Bibliografia

1.  [Livro-texto] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algoritmos - Teoria e Prática (tradução da 2ª Ed. Americana), Ed. Campus (2002).

2.  U. Manber, Algorithms: A Creative Approach, Addison-Wesley (1989).

3.  J. Kleinberg e E. Tardos, Algorithm Design, Addison Wesley, (2005).

4.  G. Brassard e P. Bratley, Algorithmics: Theory and Practice, Prentice-Hall.

5.  A. Aho, J. Hopcroft, e J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley (1974).

6.  N. Ziviani Projeto de Algoritmos com Implementações em Pascal e C, Pioneira Thomson Learning, 2ª. edição, (2004).

7.  J. Szwarcfiter, Algoritmos em Grafos, Editora Campus (1987).

8.  J. Szwarcfiter e L. Markenson, Estruturas de Dados e seus Algoritmos, LTC Editora (1994).