Skip to content. | Skip to navigation

Personal tools

Navigation

You are here: Home / Teaching / CI057 - Algorithms and Data Structures III / CI057 - Algorithms and Data Structures III

CI057 - Algorithms and Data Structures 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.

Cálculo da nota:

(Prova1 + Prova 2 + Trabalhos) / 3

Horários e ensalamento:

  • 4as-15:30 e 6as-15:30
  • O ensalamento deve ser verificado no mural logo na entrada do Dinf.

Trabalhos:

Exercícios:

(página do Prof. Marcos Didonet)

Calendário:

  • Primeira prova: 16/10
  • Entrega do trabalho prático: 14/10
  • Segunda prova: 18/12
  • Prova final: 23/12
  • Não havera aulas: 06-07/Out (SIEPE)
  • Semana acadêmica (16-21/Nov), não será cobrado presença.

Abaixo, uma tentativa de calendário devido ao período de greve e semanas acadêmica e EVINCI:

09 02/10 AVL
--  07/10 EVINCI
10 09/10 Arv. 2-3-4
11 14/10 Exercícios
12 16/10 Prova 1
13 21/10 Arv. RedBlack
14 23/10 Arv. RedBlack
15 28/10 Arv. RedBlack
16 30/10 Arv. B
17 04/11 Arv. B
18 06/11 Arv. B+, ISAM
19 11/11 feriado
20 13/11 Heap e HeapSort
21 18/11 Semana academica
22 20/11 Semana academica
23 25/11 Pesquisa digital e Arv. Trie
24 27/11 Arv. Patricia
25 02/12 Compressão
26 04/12 Hashing
27 09/12 Ordenação externa
28 11/12 Splay
29 16/12 Exercícios
30 18/12 Prova 2
-- 23/12 prova final

 

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.