Ementa:
Estruturas de dados básicas. Análise de algoritmos. Busca e ordenação em estruturas lineares. Tabelas de dispersão. Árvores. Estruturas de dados para relações de equivalência. Grafos e algoritmos. Heurísticas para problemas intratáveis.
Objetivo geral: A disciplina tem como objetivo estudar estruturas de dados e algoritmos clássicos com o intuito de prover ferramentas para o projeto, a implementação e a análise de programas.
Conteúdo programático:
Análise de algoritmos
Fundamentos
Complexidade assintótica
Estruturas de dados básicas
Arrays estáticos e dinâmicos
Listas encadeadas
Filas e pilhas
Busca e ordenação em estruturas de dados lineares
Busca linear e busca binárias
Mergesort
Quicksort
Tabelas de dispersão
Árvores
Árvores binárias de busca
Árvores AVL
Heaps e heapsort
Estruturas para relações de equivalência
Grafos
Busca em profundidade e busca em largura
Caminhos mínimos (Dijkstra, Bellman-Ford, Floyd-Warshall)
Árvores geradoras de custo mínimo (Prim, Kruskal)
Computabilidade e complexidade computacional
Heurísticas para problemas intratáveis
Backtracking
Branch & bound
Programação dinâmica
Bibliografia básica:
Anany Levitin. Introduction to the design and analysis of algorithms (3rd ed). Addison Wesley, 2011.
Clifford Shaffer. Data Structures and Algorithm Analysis . Dover Publications, 2013.
Bibliografia auxiliar:
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms. MIT Press, 2009