Plano de Ensino

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