Introdução

Programas de computador armazenam, acessam e manipulam informações, isto é, dados. Programas são uma formulação concreta de algoritmos abstratos baseados em uma representação particular dos dados. Muito do que é feito em várias áreas da Ciência da Computação (tais como compiladores, computação gráfica ou sistemas operacionais) é buscar maneiras de representar os dados para que o armazenamento, acesso e manipulação destes seja feito de maneira eficiente (ou seja, rápida e gastando pouco espaço).

Sempre que representamos dados em um computador consideramos cada um dos seguintes aspectos:

1. a maneira que essas informações (ou objetos do mundo real) são modelados como objetos matemáticos;
2. o conjunto de operações que definiremos sobre estes objetos matemáticos;
3. a maneira na qual estes objetos serão armazenados (representados) na memória de um computador;
4. os algoritmos que são usados para executar as operações sobre os objetos com a representação escolhida.

Os itens (1) e (2) acima dizem respeito ao tipo abstrato de dados, ou seja, ao modelo matemático junto com uma coleção de operações definidas sobre este modelo. (Um exemplo de tipo abstrado de dados é o conjunto dos números inteiros com as operações de soma, subtração, multiplicação e divisão sobre inteiros.) Já os itens (3) e (4) estão relacionados aos aspectos de implementação. Para representar um tipo abstrato de dados em um computador usamos uma estrutura de dados, que é uma coleção de variáveis, possivelmente de diferentes tipos, relacionadas de diversas maneiras.

Uma boa escolha das estruturas de dados usadas na resolução de um problema é essencial para se obter um algoritmo eficiente para o problema.

Objetivos

Nesta disciplina consideraremos vários tipos abstratos de dados e estudaremos diferentes estruturas de dados para armazenar (representar) estes tipos, juntamente com os algoritmos para manipular estas estruturas. Existem várias estruturas de dados para um mesmo tipo abstrato de dados e em geral não existe uma estrutura de dados que é a melhor para todas as circunstâncias.

As estruturas de dados que veremos nasceram de aplicações cotidianas de Ciência da Computação. Novas aplicações irão requerer a criação de novas estruturas de dados. Esperamos que esta disciplina forneça elementos e técnicas que possam ajudá-los a projetar/escolher boas estruturas de dados.

Método

Nas aulas, serão apresentadas várias estruturas de dados para diferentes tipos abstratos de dados. Após cada aula, será recomendada a leitura de trechos do livro texto relacionados ou que complementem o conteúdo da aula. Serão dados quatro exercícios-programa e algumas listas de exercícios. É essencial que os alunos resolvam estes exercícios e as listas para garantir a assimilação gradativa do material apresentado. As provas complementarão a avaliação e darão uma noção mais concreta ao professor do grau de aprendizado dos alunos.

Espera-se que os alunos resolvam os exercícios-programa de maneira clara e bem documentada. Aprenda a programar bem!! Existem livros muito bons [7,8], com dicas que podem fazer muita diferença tanto na qualidade dos programas que você escreve quanto no tempo que você gasta na depuração e teste dos seus programas.

Critério de avaliação

Haverá três provas, quatro exercícios-programa (EPs) e algumas listas de exercícios.

Data das provas:

• P1: 30 de março
• P2: 11 de maio
• P3: 29 de junho

Note que não há prova substitutiva.

Além das provas, apenas a entrega dos EPs é obrigatória. Se for detectada cola nos EPs, todos os alunos envolvidos serão reprovados na disciplina sem mais, com nota inferior a 3,0.

Denotando por MP a média aritmética das notas nas três provas e por MEP a média aritmética das notas nos EPs, a média final do aluno (a menos do caso acima), denotada por MF, será calculada da seguinte maneira:

Se MP >= 5,0 e MEP >= 5,0
então MF = alfa*max{MP,(2*MP+MEP)/3}
senão MF = min{4,0,MP,MEP}

Bibliografia

O livro texto é o seguinte

1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, segunda edição, MIT Press, 2001. (Há uma versão em português, da Editora Campus.) [QA758 C811i]

Além deste, o aluno interessado pode consultar também os seguintes textos

2. A.V. Aho, J.E. Hopcroft, e J.D. Ullman, Data structures and algorithms, Addison-Wesley, Reading, Mass., 1983. [QA758 A286d]
3. J.L. Szwarcfiter e L. Markenzon, Estruturas de Dados e seus Algoritmos, segunda edição, LTC Editora, 1994. [QA758 S998e]
4. D.E. Knuth, The art of computer programming, vol 1: Fundamental algorithms, Addison-Wesley, Reading, Mass., 1968. [QA758 K74a]
5. N. Wirth, Algorithms and Data Structures, Prentice-Hall, Englewood Cliffs, NJ, 1986. [QA758 W799]
6. N. Ziviani, Projeto de Algoritmos com Implementação em Pascal e C, segunda edição. Thomson, 2004. [QA758 Z82a]

Aqui estão duas sugestões de livros que podem ajudá-lo a se tornar um programador melhor. Pegue um deles agora no início do semestre na biblioteca e dê uma olhada!

7. J. Bentley, Programming Pearls, segunda edição, Addison-Wesley, Inc., 2000. [QA754 B477p]
8. B.W. Kernighan e R. Pike, The Practice of Programming, Addison-Wesley, Inc., 1999. (Existe uma versão em português deste.) [QA754 K39p]

Outras informações

Várias informações sobre a disciplina estarão disponíveis aqui. e no sistema Panda você encontra o fórum da disciplina. No Panda ficarão disponíveis também durante o semestre as suas notas. Assumirei que os alunos estão cientes de todos os avisos postados no fórum e na página da disciplina.

Vocês podem me encontrar na sala 107-C do IME-USP e o meu e-mail cris at ime.usp.br.