CI057 - Algoritmos e Estruturas de Dados III
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).
Critérios de Avaliação
- Listas de Exercícios
- Provas (70% da nota)
- Prova 1: 29 de abril de 2005
- Prova 2: 22 de junho de 2005
- Final: 01 de julho de 2005
- Trabalhos (30% da nota)
- Trabalho 1: 27 de abril de 2005
- Trabalho 2: 17 de junho de 2005
Notas e Frequências