Estruturas de Dados e Algoritmos 2002.1 
Motivação e Apresentação do Curso 
Curso de Ciência da Computação

Dalton Serey
DSC - UFPB
(Este material em formato postscript ou pdf.)

Local:	Sala de reuniões do DSC
Horário:	T102 X082

Créditos: 4
Carga Horária: 60 horas-aula

Motivação e objetivos

Programas manipulam dados. Portanto, sua eficiência está diretamente ligada à eficiência com que são capazes de armazenar, recuperar e alterar os dados. Usamos a expressão estruturas de dados para referir-nos à forma como os dados são organizados dentro do espaço de memória necessário à execução de um programa. O objetivo deste curso é introduzir você às questões fundamentais envolvidas na escolha criteriosa de estruturas de dados e algoritmos.

É bastante intuitivo que a escolha dos algoritmos e das estruturas de dados tem influência na eficiência dos programas. Contudo, a experiência também mostra que além da eficiência, outros aspectos da qualidade de um programa são afetados. Em particular a escalabilidade, a reusabilidade e a manutenibilidade do código são diretamente influenciadas pelas questões que abordaremos no decorrer do curso.

Ao final do curso, além de conhecer as estruturas de dados clássicas, suas propriedades e seus respectivos algoritmos, você deverá ser capaz de, diante de um dado problema, escolher ou projetar uma estrutura de dados adequada.

Programa de curso

O curso foi dividido em 6 unidades. As primeiras três unidades formam a parte básica do curso em que veremos as estruturas fundamentais. As Unidades 4 e 5 formam a segunda e maior parte do curso. A Unidade 6 não é parte obrigatória do curso, mas é nosso propósito vermos pelo menos representação de grafos e conjuntos disjuntos, bem como alguns algoritmos.

1. Introdução (3 aulas)
1. Algoritmos
2. Revisão de conceitos de tipos de dados
3. Análise de algoritmos

 

 
 
 

2. Estruturas de dados básicas (5 aulas)
1. Conjuntos dinâmicos.
2. Listas
3. Pilhas e filas
4. Representações de árvores (com raiz)
5. Filas de prioridade e heaps

 

 
 
 

3. Tabelas de espalhamento (hash) (4 aulas)
1. Tabelas de acesso direto
2. Hashing aberto
3. Hashing fechado
4. Hashing dinâmico

 

 
 
 

4. Árvores de pesquisa (9 aulas)
1. Árvores binárias de pesquisa
2. Balanceamento em árvores
3. Árvores PV
4. Árvores B
5. Tries

 

 
 
 

5. Ordenação (4 aulas)
1. Ordenação em heaps (heapsort)
2. Ordenação por inserção (insertion-sort)
3. Ordenação rápida (quicksort)

 

 
 
 

6. Grafos e outras estruturas (2 aulas)

 

 
 
 

Calendário

O exame do primeiro estágio será feito após o final da exposição do material da Unidade 3. O exame referente ao segundo estágio somente será realizado ao final do curso. A agenda para o curso é ilustrada na Tabela 1.
 

Tabela 1: Agenda de atividades do curso

Data	Evento previsto
25/06	Apresentação + Início Unidade 1
05/07	Início Unidade 2
23/07	Início Unidade 3
06/08	Exame do primeiro estágio
07/08	Último dia para trancamento de matrícula 2002.1
09/08	Início Unidade 4
10/09	Início Unidades 5 e 6
01/10	Exame do segundo estágio
04/10	Reposição dos exames
04/10	Entrega dos projetos
08/10	Exame final

Durante o semestre, contudo, pode ser necessário fazer ajustes nessas datas. Qualquer mudança será informada na página do curso, onde será mantido o calendário válido para o curso.

Forma de avaliação

Tabela 2: Discriminação dos eventos de avaliação e seus pesos.

Variável	Descrição	Peso
MED	média
MT	média dos mini-testes	30%
E1	nota obtida no $1^{o}$ exame	20%
E2	nota obtida no $2^{o}$ exame	20%
PRJ	nota obtida no projeto	30%

A avaliação será feita através de mini-testes, exames e um mini-projeto ou trabalho final. Faremos um mini-teste por semana de aula e dois exames ao longo do semestre (ver calendário). O mini-projeto ou trabalho final deve ser entregue ao final do semestre. A média do aluno deve ser calculada pela fórmula abaixo (ver discriminação e peso das variáveis na Tabela 4): $$\mbox{MED}= 0.3 \cdot \mbox{MT} + 0.2 \cdot \mbox{E1} + 0.2 \cdot\mbox{E2} + 0.3 \cdot \mbox{PRJ}$$

Aprovação por média

Para ser aprovado por média, o aluno deve obter média acima de $7.0$ ($\mbox{MED} \geq 7.0$) e deve ter feito pelo menos 75% dos mini-testes. Neste caso, sua nota final no curso será a própria média.

Aprovação por exame final

Os alunos que obtiverem média entre $4.0$ e $7.0$ ($4.0 \leq \mbox{MED}< 7.0$) poderão se submeter ao exame final (ver calendário). A média final do aluno é calculada pela fórmula: $$\mbox{MF} = 0.6 \cdot \mbox{MED} + 0.4 \cdot\mbox{NF}$$

onde NF é a nota obtida no exame final e MED é a média obtida durante o curso. Serão considerados aprovados no exame final¹ os alunos que obtiverem média final acima de $5.0$ ($\mbox{MF} \geq 5.0$).

Reprovação

Os alunos que obtiverem média MED abaixo de $4.0$ ($\mbox{MED} < 4.0$) e os que, submetendo-se ao exame final, obtiverem média final abaixo de $5.0$ ($\mbox{MF} < 5.0$) serão considerados reprovados no curso.

Eventos de avaliação

Mini-testes

Os mini-testes são exercícios individuais executados no início de uma aula. O propósito dos mini-testes é identificar falhas no entendimento o mais cedo possível e servir de método de avaliação contínua. Sempre consistem em duas questões simples. Uma sobre o assunto visto nas aulas imediatamente anteriores e outra sobre qualquer assunto já visto.

Todos os mini-testes serão aplicados nos 20 minutos iniciais das aulas das sextas-feiras. O aluno deve fazer pelo menos 75% dos mini-testes para ser aprovado. Cabe ao aluno decidir quais mini-testes fazer e quais não. É importante observar que a menor nota dos mini-testes será eliminada para o cálculo de MT (desde que restem pelo menos 75% de mini-testes). Só serão aceitos os mini-testes entregues no tempo indicado ao início. Isto é necessário para garantir o tempo necessário para o restante da aula.

Exames

Os exames são provas propriamente ditas, aplicadas em aulas completas. Cada exame tem a função de avaliar os conhecimentos e habilidades adquiridas pelo aluno até aquele ponto no curso. Consistem de 4 a 5 questões, envolvendo a solução de problemas e que demonstram o grau de maturidade do aluno em relação aos tópicos estudados. Naturalmente, as questões envolvem mais raciocínio e são mais difíceis do que as dos mini-testes.

Serão aplicados dois exames ao longo do curso. O aluno deve fazer ambas, obrigatoriamente. Ambas as notas entram no cálculo da média (ver Seção 4). Será permitido a cada aluno repor uma das provas em data e horário a determinar, desde que a falta seja devidamente justificada.

Mini-projeto

O mini-projeto será especificado no decorrer do semestre. Alternativamente, o aluno poderá conduzir um trabalho de pesquisa individual e apresentá-lo na forma de seminário. O mini-projeto é obrigatório.

Material bibliográfico

Oficialmente, o livro-texto do curso é o Cormen [Cormen et al., 1990]. Contudo, em cada momento do curso, vou indicar leituras complementares. As notas de aula contêm o material minimamente necessário para o cumprimento do curso. Logo, é muito importante que você procure ler diretamente as fontes indicadas.

Pessoalmente, os livros de que mais gosto são o ``Cormem'' (também conhecido como CLR) [Cormen et al., 1990] e o ``Aho'' [Aho et al., 1983]. Ambos estão disponíveis na biblioteca do departamento. O primeiro é um livro de referência sobre projeto e análise de algoritmos e estruturas de dados. De fato, tem muito mais material do que podemos abordar em um curso introdutório. Ainda assim, as explicações são muito boas e os algoritmos, escritos em pseudo-código, podem ser facilmente traduzidos para qualquer linguagem de programação de alto nível. O livro é referência global no assunto. O segundo livro também cobre o assunto que estudaremos. Os algoritmos são expressos em pseudo-código com sintaxe semelhante a Pascal. Contudo, o seu ponto forte são as explicações e exemplos.

Também há diversos livros de estruturas de dados e algoritmos centrados em linguagens de programação específicas. Particularmente, não gosto muito deles. Contudo, são muito úteis quando o problema é entender como uma estrutura de dados é codificada em determinada linguagem. Alguns desses livros são [Horowitz and Sahni, 1984], [Budd, 1994], [Goodrich and Tamassia, 1998] e [Weiss, 1998]. Podem servir de consulta durante o curso.

Há ainda outros livros que podem servir de leitura complementar. É o caso dos ótimos livros de Jon Bentley (Programming Pearls) e a série clássica de Donald Knuth (The Art of Computer Programming). Este último é a referência maior quando o tema é estruturas de dados e algoritmos. É a verdadeira ``Bíblia'' da programação. É muito importante que você dê pelo menos uma olhada nesses livros ao longo do curso.

Recursos na rede

A página da disciplina é onde concentrarei toda a informação relativa ao curso. Todo o material usado em sala de aula (notas de aula, exercícios, etc), bem como avisos, datas e outras informações serão mantidos na página.

O endereço completo é:

http://www.labpetri.dsc.ufpb.br/~dalton/edados

Condições para fazer um bom curso

Três condições são fundamentais para fazer um bom curso:

• certa experiência com programação, incluindo a compreensão e o uso de recursividade e da noção de referência;
• certa familiaridade com a notação e o raciocínio matemáticos; noções de álgebra abstrata, de matemática discreta (somas, grafos, matrizes) e fundamentos de provas ajudam;
• estar realmente disposto a ler, pensar e entender! É importante que você seja capaz de ler inglês; a maioria esmagadora dos bons textos sobre o assunto está em inglês e as traduções são, via de regra, fracas.

 

 
 
 

Logo, procure identificar e sanar possíveis deficiências o mais cedo possível. Se precisar de ajuda, procure-me o mais cedo possível.

Bibliografia

Aho et al., 1983

Aho, A., Hopcroft, J., and Ullman, J. (1983).

Data Structures and Algorithms.
Computer Sciente and Information Processing. Addison-Wesley.

Budd, 1994

Budd, T. (1994).

Classic Data Structures in C++.
Addison-Wesley.

Cormen et al., 1990

Cormen, T. H., Leiserson, C. E., and Rivest, R. L. (1990).

Introduction to Algorithms.
The MIT Electrical Engeneering and Computer Science Series. MIT Press / McGraw-Hill.

Goodrich and Tamassia, 1998

Goodrich, M. T. and Tamassia, R. (1998).

Data Structures and Algorithms in Java.
John Wiley & Sons.

Horowitz and Sahni, 1984

Horowitz, E. and Sahni, S. (1984).

Fundamentals of Data Structures in Pascal.
Computer Science Press.

Weiss, 1998

Weiss, M. A. (1998).

Data Structures and Problem Solving Using Java.
The MIT Electrical Engeneering and Computer Science Series. Adisson-Wesley.

Notas de rodapé

... final¹

Logo, o aluno que fizer o exame final deve obter nota mínima igual a $(50 -6\cdot\mbox{MED})/4$.