Departamento de Informática Universidade Federal do Paraná
Carga Horária: 60 horas
Prof. Hélio Pedrini
Objetivos
Apresentar e analisar algoritmos e estruturas de dados avançadas para uso eficiente do computador na resolução de problemas.
Diversos aspectos teóricos e práticos são abordados, buscando-se a construção de estruturas modulares e reutilizáveis. Os
algoritmos são descritos através de uma linguagem simples, com ênfase no método utilizado para solucionar o problema,
facilitando sua implementação em linguagens de programação tais como Pascal, C, C++ ou Java.
Ementa
Análise de Algoritmos. Recursividade. Árvores Binárias. Árvores Balanceadas. Árvores-B. Técnicas de Espalhamento. Pesquisa
em Memória Primaria. Pesquisa em Memória Secundária. Organização de Arquivos. Índices.
Programa
Introdução
Algoritmos, estruturas de dados e programas
Análise de algoritmos
Recursividade
Árvores
Definições e representações básicas
Árvores binárias
Percurso em árvores binárias
Aplicações (códigos de Huffman, pesquisa binária, expressões matemáticas, jogos)
Árvores Balanceadas
Definições e propriedades
AVL-Trees
Red-Black Trees
Splay Trees
B-Trees
Organização de Arquivos
Pesquisa em memória secundária
Índices
Tabelas de Dispersão
Introdução
Funções de dispersão
Tratamento de colisões
Bibliografia
Básica
A.M. Tenenbaum, Y. Langsam, M.J. Augenstein. Estruturas de Dados Usando C. Makron Books do Brasil Editora Ltda, São Paulo, SP, 1995.
N. Ziviani. Projeto de Algoritmos com Implementações em Pascal e C. Livraria Pioneira Editora, São Paulo, SP, 1994.
J.L. Szwarcfiter, L. Markenzon. Estruturas de Dados e seus Algoritmos. LTC-Livros Técnicos e Científicos, Rio de Janeiro, RJ, 1994.
Complementar
T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, 1996.
R. Sedgewick. Algorithms. Addison-Wesley, Reading, Massachusetts, 1983.
A.V. Aho, J.E. Hopcroft, J.D. Ullman. Data Structures and Algorithms. Addison-Wesley, Reading, Massachusetts, 1983.
P.A.S. Veloso, C.S. Santos, P.A. Azeredo, A.L. Furtado. Estruturas de Dados. Editora Campus, Rio de Janeiro, RJ, 1986.
N. Wirth. Algorithms and Data Structures. Prentice-Hall, 1986 (Tradução: Algoritmos e Estruturas de Dados. Prentice-Hall do Brasil Ltda, 1989).