Projeto e análise de algoritmos e estruturas de dados avançadas: filas com prioridade, heaps, tabelas de hash, mapas, dicionários, conjuntos e grafos. Discussão, análise e raciocínio sobre a complexidade de algoritmos e implementações correspondentes.
1. Conhecer estruturas de dados avançadas: filas de prioridades, mapas e conjuntos;
2. Conhecer grafos, suas formas de representação e seus algoritmos mais importantes;
3. Indicar as estruturas de dados que melhor se adaptam para a solução de um determinado problema;
4. Analisar e selecionar o algoritmo mais eficiente para a solução de um determinado problema.
1.1 Algoritmos e complexidade
1.2 Ordem de Crescimento e Notação Assintóticas
1.2.1 Notação O
1.2.2 Notação Theta
1.2.3 Notação Omega
1.3 Classes de algoritmos: logarítmico, linear, quadrático, exponencial e outros
1.4 Estruturas lineares e hierárquicas
2.1 Filas de prioridade
2.1.1 Heaps: min-heap e max-heap
2.1.2 Heapsort
2.2 Tabelas de espalhamento
2.2.1 Estruturas hash: conceitos e implementação
2.2.2 Funções de hash
2.2.3 Tratamento de colisões
2.3 Conjuntos
2.4 Aplicações
2.4.1 Banco de dados: Árvores B
2.4.2 Compressão: Códigos de Huffman
2.4.3 Processamento de Imagens: Quadtrees
2.4.4 Processamento de Textos: Dicionários
3.1 Definições e algoritmos básicos
3.1.1 Representação e implementação
3.1.2 Caminhamentos: largura e profundidade
3.1.3 Detecção de ciclos
3.1.4 Ordenação topológica
3.1.4 Detecção de Componentes
3.2 Árvores Geradoras Mínimas
3.3.1 Algoritmos de Prim e Kruskal
3.3 Caminhos mínimos
3.3.1 Algoritmo de Dijkstra
3.3.2 Algoritmo de Floyd-Warshall
3.4 Caminho Crítico
3.5 Fluxos
3.5.1 Redes de fluxo
3.5.2 Algoritmo de Ford-Fulkerson
3.6 Outras aplicações
1. CORMEN, T. H. Algoritmos teoria e prática. 3ª ed., Rio de Janeiro: Elsevier-Campus, 2012.
2. ELLIS, H.; SAHNI, S.; RAJASEKARAN, S. Computer algorithms. Silicon Press, 2007.
3. GOODRICH, M. T.; TAMASSIA, R. Estruturas de dados e algoritmos em Java. 5ª ed., Porto Alegre: Bookman, 2013.
1. AHO, A. V. Foundations of computer science. New York: Computer Science Press, 1998.
2. GERSTING, J. L. Fundamentos matemáticos para ciência da computação: um tratamento moderno de matemática discreta. 5. ed., Rio de Janeiro: LTC, 2004.
3. GIBBONS, A. Algorithmic graph theory. Cambridge (UK): Cambridge Univ., 1985.
4. LEVITIN, A. Introduction to the design and analysis of algorithms. Boston: Addison-Wesley, 2003.
5. WALLIS, W. D. A beginner's guide to graph theory. Boston: Birkhäuser, 2000.
Onde: