CI1057 - Algoritmos e Estrutura de Dados III

Programa:

Introdução a tipos abstratos de dados e o tipo dicionário. Árvores: definição e conceitos; aplicações; algoritmos básicos. Tipos de árvores: binária, binária de busca, AVL, rubro- negra. Busca externa: árvore B, B+, ISAM. Árvore digitais: de busca, trie, Patricia. Compressão de dados e Heap. Ordenação externa. Tabelas de dispersão (hashing).

Ementa:

Memória principal. Acesso seqüêncial, indexado. Árvore. Complexidade algoritmos. Ordenação externa. Árvores balanceadas. Conjuntos não ordenáveis.

Horários e ensalamento:

• 3as-15:30
• O ensalamento deve ser verificado no mural logo na entrada do Dinf ou no site de ensalamento.

Calendário:

• Prova #1: 24/04
• Prova #2: 26/06
• Trabalho: 08/05
• Final e reaproveitamento: 08/07

Trabalho:

• AVL

Cálculo da nota:

(Prova1*0.4) + (Prova2*0.4) + (Trabalhos*0.2)

Exercícios:

(página dos profs. Vignatti e Didonet)

• Árvores BST, AVL, 2-3-4
• BST, AVL, 2-3-4, Rubro-negra
• B*, Heap, Hash
• Simulador de Rubro-negra

Bibliografia:

• Algoritmos - Teoria e prática, Cormen, Leiserson, Rivest, Stein.
• Estruturas de Dados e seus Algoritmos. J.L. Szwarcfiter, L. Markenzon. LTC-Livros Técnicos e Científicos, Rio de Janeiro, RJ, 1994.
• Algorithms. R. Sedgewick. Addison-Wesley, Reading, Massachusetts, 1983.
• Data Structures and Algorithms. A.V. Aho, J.E. Hopcroft, J.D. Ullman. Addison-Wesley, Reading, Massachusetts, 1983.
• Algorithms and Data Structures. N. Wirth. Prentice-Hall, 1986 (Tradução: Algoritmos e Estruturas de Dados. Prentice-Hall do Brasil Ltda, 1989).
• The Art of Computer Programming vol. 1, D.E. Knuth.
• The Art of Computer Programming vol. 3, D.E. Knuth.
• Introduction to Algorithms, Cormen, Leiserson, Rivest. MIT Press, Cambridge, Massachusetts, 1996.