MC3305
Algoritmos e Estruturas de Dados II

Ementa

Hashing: Fundamentos e aplicabilidade; Tabelas e funções de hashing; Resolução de colisões; Operações básicas em tabelas de hashing. Introdução a arquivos: Introdução: memória secundária, fundamentos de arquivos. Operações fundamentais em processamento de arquivos: Arquivos físicos e lógicos; Operações básicas. Armazenamento secundário e software de sistema: Organização de discos; Custo do acesso ao disco; Gerenciamento de arquivo; Entrada e saída no UNIX. Conceitos fundamentais de estrutura de arquivos: Organização dos arquivos; Acesso aos arquivos. Gerenciamento de arquivos de registros: Acesso seqüencial; Acesso direto; Modelos abstratos para acesso a arquivos; Portabilidade e extensibilidade. Organizando arquivos para desempenho: Compressão de dados; Algoritmo de Huffman para compressão de arquivos; Recuperação de espaço não usado em arquivos; Busca binária; Keysort. Arquivos indexados: Índices, índices simples, índices secundários, índices seletivos; Acesso através de chaves múltiplas. Processamento co-seqüencial e ordenação de arquivos muito grandes: Modelo co-seqüencial; Ordenação em memória; Merging para ordenação de arquivos grandes. Indexação multi-nível e árvores B: Árvores AVL, árvores B, árvores B* e árvores B virtuais. Acesso a arquivo seqüencial indexado: Acesso seqüencial indexado; Árvores B+.

Bibliografia Básica

Folk M.,, Zoellick B., Riccardi G. File Structures, An Object-Oriented Approach Using C++, Third Edition. Addison-Wesley, 1998Cormen T. H et al., Algoritmos: Teoria e Prática. Rio de Janeiro: Editora Campus, 2ª edição, 2002Folk M., Zoellick B. File Structures, Second Edition. Addison-Wesley, 1992

X

Bibliografia Complementar

Ziviani N. Projeto de Algoritmos com implementação em Java e C++.São Paulo: Editora Thomson, 1ª edição, 2007
ison-Wesley, 1998Cormen T. H et al., Algoritmos: Teoria e Prática. Rio de Janeiro: Editora Campus, 2ª edição, 2002Folk M., Zoellick B. File Structures, Second Edition. Addison-Wesley, 1992

X

Tipo