MAC 324 Estruturas de Dados para Engenharia

Bem-vindo!

Bem-vindo à MAC 324 Estruturas de Dados para Engenharia. Esta é uma disciplina introdutória em estruturas de dados e projetos de algoritmos. Abaixo encontra-se uma descrição de alguns dos ingredientes principais desta disciplina.

1. 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 nós 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.

   Apesar dos termos tipo de dados, tipo abstrato de dados e estrutura de dados parecerem semelhantes eles têm significados diferentes. O tipo de dado de uma variável é o conjunto de valores que esta variável pode assumir. Por exemplo, uma variável do tipo boolean só pode assumir os valores TRUE e FALSE.

   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 difinidas 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 nós usamos uma estrutura de dados, que é uma coleção de variáveis, possivelmente de diferentes tipos, ligadas (relacionas) de diversas maneiras.

2. Objetivos

   Nesta disciplina nós 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 nesta disciplina nasceram de aplicações cotidianas em ciência da computação. Novas aplicações irão requerer a criação de novas estruturas de dados. É desejado que esta disciplina forneça aos estudantes elementos e técnicas que possam auxilia-los a criarem boas estruturas de dados.

3. Pré-requisitos

   Para esta disciplina os pré-requisitos são: conhecimento de técnicas básicas de programação que são vistos em MAC 115 Introdução à Computação e conhecimento da linguagem de programação C.

4. Critério de avaliação

A nota final na disciplina será baseada em dois componentes:

Provas

Teremos três provas nesta disciplina. Todas as provas serão às quarta-feiras. A primeira prova será no dia 28 de março, a segunda no dia 16 de maio e a terceira no dia 20 de junho. Teremos ainda uma prova substutiva no dia 4 de julho. A média aritmética das provas representará 75% da nota final.

Projeto

Durante o semestre desenvolveremos projeto de programação que será divido em fases. O projeto poderá ser feito em duplas (de dois! ;-)). A nota do projeto, que será a média das notas obtidas nas fases, representará 25% da nota final.

5. Alguns tópicos que pretendemos cobrir

Pretendemos cobrir os tópicos básicos em estrutura de dados. Alguns destes tópicos (não necessariamente nesta ordem) são:

1. listas lineares: filas e pilhas;
2. algoritmos de busca e ordenação;
3. árvores: árvores binárias; árvores de busca binária; árvore balanceadas (como, por exemplo, árvores AVL, {splay trees); e B-árvores;
4. métodos de busca e ordenação;
5. hashing;
6. filas de prioridades (Heaps); e
7. grafos.
Para descrevermos as estruturas de dados e os algoritmos que manipulam estas estruturas faremos uso da linguagem de programação C.
6. Bibliografia

Para prepara as aulas desta disciplina consultarei vários livros (veja a Bibliografia). Entretanto, vou procurar seguir de perto o livro

• Robert Sedgewick,
  Algorithms in C, 3rd. edition, vol. 1
  Addison Wesley Longman, 1998.
7. Estruturas de dados na Internet

Existe muito material muito bom de Estruturas de Dados na Internet. Durante o andamento da disciplina estarei mantendo, na página

http://www.ime.usp.br/~coelho/mac324/sitios/,

uma lista de alguns sítios de Estruturas de Dados. Durante o andamento da disciplina está página deverá ser atualizada e expandida. Se você encontrar algum sítio de Estrutura de Dados (ou de qualquer outra coisa) que você ache interessante, por favor, não deixe de me avisar.
8. Monitor

O assistente/monitor desta disciplina é Aritanan Borges Garcia Gruber, sala B-??, e-mail gruber@ime.usp.br.

9. Outras informações

A minha sala é a B-164, o número do meu telefone é 3818-6295 e meu endereço eletrônico é coelho@ime.usp.br.

Manterei uma página de MAC 324 no URL

http://www.ime.usp.br/~coelho/mac324/.

Nessa página colocarei o material da disciplina (como, por exemplo, listas de exercícios). Por favor, dê uma olhada nesta página regularmente.

Estarei mantendo uma lista de discussão que tem como objetivo servir de suporte para a disciplina. Recomenda-se que você mande para esta lista suas dúvidas, sugestões, críticas ou observações sobre o andamento da disciplina. Assim, se você pretende cursar estruturas de dados, por favor, veja a página

http://www.ime.usp.br/~coelho/mac324/lista/

e inscreva-se na lista de discussão. Sinta-se a vontade para escrever-me e fazer perguntas ou comentários sobre a disciplina.