Estrutura de Dados II (IM860)

Estrutura de Dados 2

Informações

Codigo: IM860

Pré-requisito:

Estrutura de Dados 1

Ementa

Arquivos em Série e Sequências. Arquivos de Acesso Direto. Arquivos Indexados pela Chave Primária e por Múltiplas Chaves. Tabelas de Dispersão. Árvores B e B+. Compressão de arquivos. Processamento de cadeias. Tópicos Avançados e aplicações.

Objetivos

Ao final da disciplina o aluno deve:

(a) Aplicar em soluções algorítmicas os conceitos de série e sequências;

(b) Compreender o conceito de classificação externa;

(c) Aplicar arquivos de acesso direto em soluções computacionais;

(d) Aplicar em soluções algorítmicas os conceitos arquivos indexados pela chave primária e por múltiplas chaves;

(e) Aplicar em soluções algorítmicas os conceitos de processamento de cadeias e compressão de dados.

Conteúdo Programático

Sumario

1. Introdução
2. Acesso direto a arquivos
3. Arquivos indexados por chave primária
4. Processamento de cadeias
5. Compressão de arquivos
6. Tópicos avançados e aplicações

Tópicos de Aula

01. Introdução

• Conceito de Arquivo. Arquivos Físicos;
• Meios de armazenamento;
• Paginação
• Dispositivos de Entrada e Saída e seu Controle;
• Interface com os sistemas operacionais;

02. Acesso direto a arquivos

• Tabelas de dispersão;
• Funções “hash”
• Algoritmos de tratamento de colisões

03. Arquivos indexados por chave primária

• Arquivos sequenciais indexados;
• Árvores B e Algoritmos;
• Árvores B+ e Algoritmos;

04. Processamento de cadeias

• Algoritmo de Força Bruta
• Algoritmo de Knuth, Morris e Pratt

05. Compressão de arquivos

• Conceito de compressão
• Algoritmos de compressão sem perda
• Algoritmos de compressão com perda

06. Tópicos avançados e aplicações

• Algoritmos para manipulação de arquivos grandes em ambientes distribuídos

Bibliografia

Bibliografia Básica

1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Algoritmos – Tradução da 2ª Edição Americana – Teoria e Prática. Ed. Campus, 2002.
2. A. Tharp. “File Organization and Processing”. John Wiley & Sons, Inc. 1988.
3. P.D. Smith, G.M. Barnes. “Files and Databases: An Introduction”. Addison-Wesley – Series in Computer Science Reading, 1987.

Bibliografia Complementar

1. N. Wirth. “Algorithms + Data Structures = Programs”. Prentice-Hall- Englewood Cliffs, 1976.
2. D.E. Knuth. “The Art of Computer Programming”. Addison-Wesley- Reading, 1973.

Postado em 18/11/2013 - 08:10 - Atualizado em 15/08/2023 - 14:53