Disciplina GA-024

Last modified on Friday, June 11th 2010 at 9:52 AM.

Pós-graduação em Modelagem Computacional do LNCC

Ciência da Computação: Estruturas de Dados e Aplicações

Período: 2010.2 (de 08/03/2010 a 28/05/2010)

Professor: Antônio Tadeu Azevedo Gomes

Horário: 3as e 5as-feiras, de 9h às 10:30h

Descrição: Este curso tem por finalidade apresentar aos alunos as principais técnicas de projeto e codificação de estruturas de dados em computadores, bem como induzir os alunos no uso dessas técnicas em problemas práticos na área de computação científica. Um enfoque particular será dado à análise de desempenho das estruturas de dados estudadas, permitindo ao aluno identificar as melhores estruturas para determinados problemas na área, considerando tempo de execução das operações de inserção, remoção e busca de dados, espaço de memória utilizado pelos dados e número de operações de entrada e saída dos dados, no caso de estruturas em memória secundária.

Ementa

0. Fundamentos (slides)

• Algoritmos, estruturas de dados, arquiteturas e programas
• Tipos abstratos de dados
• Alguns paradigmas básicos de projeto de algoritmos

1. Estruturas de Dados Elementares (slides, lista de exercícios)

• Matrizes
• Matrizes esparsas
• Cadeias de caracteres
• Pilhas e Filas
• Listas ligadas

2. Estruturas de Dados para Pesquisa em Memória Primária (slides, lista de exercícios)

• Árvores binárias
• Árvores Trie e Patricia
• Tabelas de dispersão (hash)

3. Estruturas de Dados para Pesquisa em Memória Secundária (slides, lista de exercícios (atualizada em 10/06/2010))

• Acesso sequencial indexado
• Árvores B, B+ e B*

4. Grafos (slides, lista de exercícios (atualizada em 10/06/2010))

• Formas de representação
• Busca em largura e profundidade
• Alguns problemas clássicos em grafos

Avaliação

Trabalhos práticos ao longo do período letivo e prova teórica ao final do período letivo.

Trabalho 1: Matrizes esparsas (atualizado em 30/04/2010)

Trabalho 2: Arquivos invertidos

Observação: os exemplos da aula teórica e os trabalhos práticos usam a linguagem de programação ANSI C. Onde couber, referências a outras linguagens de programação podem ser usadas.

Referências bibliográficas

• Rangel Netto, J. L. M.; Cerqueira, R. F. de G.; Celes Filho, W. (2004) Introdução A Estrutura de Dados Com Técnicas de Programação em C, Campus.
• Ziviani, N. (2007) Projeto de Algoritmos – Com Implementações em Java e C++, Thomson.
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. & Stein, C. (2001) Introduction to Algorithms, Second Edition, MIT Press.
• Szwarcfiter, J. L.; Markenzon, L. (1994) Estruturas de dados e seus algoritmos, Livros Tecnicos e Científicos.
• Knuth, D. E. (1997) The Art of Computer Programming, Vol 1, Fundamental Algorithms, Third Edition, Addison Wesley.
• Knuth, D. E. (1998) The Art of Computer Programming, Vol 3, Sort and Searching, Second Edition, Addison Wesley.

Added the file “trab1v2.pdf”.
Added the file “parte3.pdf”.
Added the file “lista2.pdf”.
Added the file “trab2.pdf”.
Added the file “parte4.pdf”.
Added the file “lista3.pdf”.
Added the file “lista4.pdf”.
Added the file “lista4v2.pdf”.
Added the file “lista3v2.pdf”.