Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

Estruturas de Dados

Especialização em Tecnologias da Computação

Professor: Wagner Meira Jr. meira@dcc.ufmg.br UFMG, ICEx, Sala 4047, (31) 3499-5867

Local: Unimontes - Montes Claros

Objetivo

O objetivo principal da disciplina é apresentar os algoritmos e as estruturas de dados básicas para o desenvolvimento de programas de computador. Ao final do curso o aluno deverá ser capaz de utilizar a programação modular, dominando as principais técnicas utilizadas na implementação de estruturas de dados básicas, de algoritmos de ordenação e de algoritmos de pesquisa em memória principal. O aluno deverá ainda ser capaz de efetuar análises simples da complexidade de algoritmos.

Programa

1.

Projeto e Análise de Algoritmos
Projeto de algoritmos; Refinamentos sucessivos; Tipos abstratos de dados; Medida do tempo de execução de programas; Técnicas de análise de algoritmos.

2.

Estruturas de Dados na Memória Principal

Listas lineares; Pilhas; Filas; Árvores.

3.

Algoritmos de ordenação

Seleção; Inserção; QuickSort; HeapSort.

4.

Algoritmos de Pesquisa

Pesquisa em tabelas: sequencial, binária, transformação de chave (hashing); Árvores de Pesquisa.

Livro-Texto

Ziviani, Nivio, Projeto de Algoritmos com Implementações em Pascal e C , Livraria Pioneira Editora, 1993.

Bibliografia

[Z]

N. Ziviani, Projeto de Algoritmos com implementações em Pascal e C , Editora Pioneira, 1993.

[CLR]

T. Cormem, C. Leiserson, R. Rivest, Introduction to Algorithms, MIT Press, 1992

[HS]

E. Horowitz, S. Sahni. Fundamentals of Computer Algorithms, Computer Science Press, 1978

[S]

R. Sedgewick. Algorithms in C, Addison Wesley, 1990.

[A]

Aho, A.V., Hopcroft, J.E. and Ullman, J.D., Data Structures and Algorithms , Addison-Wesley, 1983.

Avaliação

• Provas (2): 30 pontos
• Trabalhos Práticos (3): 70 pontos

Calendário

Aula Data Assunto Referências Obs.

01 10/11 Apresentação, conceitos básicos Z1.1-2, A1.1-3

Análise de algoritmos Z1.4, A1.4, S6

Listas lineares Z2.1, A2.1, S3

Pilhas Z2.2, A2.3, S3

Filas Z2.3, A2.4, S3

2 1/12 Prova 1 Z1 Z2 TP1

14/10 Seleção, inserção Z3.1, A8.1-2, S8

21/10 Quicksort Z3.1, A8.3, S9

21/10 Filas de prioridade, heapsort Z3.1, A4.10-8.4, S11

3 15/12 Pesquisa: métodos simples Z4.1-2, A4.5, S14 TP2

Hashing Z4.5, A4.7, S16

Árvore binária de pesquisa Z4.3, A5.1-2, S14

Prova 2 Z3 Z4

Trabalhos Práticos

O principal objetivo dos trabalhos práticos é exercitar os conceitos teóricos aprendidos em sala de aula. Isso deverá ajudá-lo a se preparar para as provas. Note bem que os trabalhos práticos são estritamente individuais. Isto, evidentemente, não significa que é proibido trocar idéias e discutir alternativas de solução. No entanto, na hora de escrever código, o trabalho deve ser individual.

Roteiro para preparação da documentação dos trabalhos práticos.

• Trabalho Prático 1: Simulacao de aeroporto, problema 10, cap. 2, pag. 66, livro texto. Alternativa: Notação pós-fixada
• Trabalho Prático 2: Ordenação usando Quicksort, problema 9, cap. 3, pag. 101, livro texto.
• Trabalho Prático 3: Geração de índice remissivo, problema 14, cap. 4, pag. 149, livro texto.

Listas de Exercícios

• Lista 1: Cap. 1: 2a, 2b, 2h, 4, 5 e Cap. 2: 1, 4.
• Lista 2: Cap 3: 1, 8, 10.
• Lista 3: Cap. 4: 1, 3, 4, 8, 12a.