Home:  MAC5711-2008

Conceitos/palavras/tópicos importantes

1. Problema, instâncias de problemas, tamanho de instância
2. Algoritmo para um problema
3. Documentação de algoritmo: o que faz versus como faz
4. Invariantes de um algoritmo iterativo
5. Algoritmo recursivo
6. Desempenho de um algoritmo
7. Consumo de tempo em função do tamanho das instâncias
8. Consumo no pior caso, no melhor caso, no caso médio
9. Comparação assintótica de funções
10. Ordens assintóticas: O, Ω e Θ
11. Recorrências
12. Cálculo do consumo de tempo de algoritmos recursivos
13. Algoritmos probabilísticos
14. Algoritmos aleatorizados
15. Divisão e conquista
16. Árvore binária de busca
17. Máximo versus maximal
18. Fila com prioridades
19. Programação dinâmica
20. Algoritmo guloso
21. Certificados de solução
22. Complexidade de problemas e cotas inferiores
23. Intratabilidade computacional e a questão P = NP

Problemas/algoritmos importantes

1. Problema da ordenação: algoritmos Mergesort, Heapsort, Quicksort
2. Order statistics: k-ésimo menor elemento de um vetor
3. Hashing (tabelas de dispersão)
4. Implementação de fila de prioridades
5. Máximo divisor comum: algoritmo de Euclides
6. Subseqüência comum máxima
7. Multiplicação de cadeia de matrizes
8. Árvores de busca binária ótima
9. Escalonamento de tarefas
10. Coleção disjunta máxima de intervalos
11. Emparelhamento estável: algoritmo de Gale-Shapley
12. Optimum branchings
13. Problema da mochila booleana
14. Problema da mochila fracionária
15. Multiplicação de inteiros grandes: algoritmo de Karatsuba-Ofman
16. Transformada rápida de Fourier (FFT)
17. Multiplicação de matrizes: algoritmo de Strassen
18. ar de pontos mais próximos
19. Códigos de Huffman
20. Busca de padrão em texto: algoritmo KMP (Knuth, Morris, Pratt)
21. Conjuntos disjuntos dinâmicos (union/find)
22. Árvore geradora mínima: algoritmos de Prim e Kruskal
23. Busca em largura e busca em profundidade num grafo
24. Caminho mínimo: algoritmo de Dijkstra
25. Emparelhamento máximo em grafo bipartido
26. Conjunto independente máximo em grafo
27. Ciclo hamiltoniano