MAC 122 Princípios de Desenvolvimento de Algoritmos

Bem-vindo!

Bem-vindo à MAC 122 Princípios de Desenvolvimento de Algoritmos. 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 estudaremos, através de exemplos, a correção, a análise de eficiência e projeto de algoritmos que são amplamento utilizados por programadores.

   Veremos ainda alguns tipos abstratos de dados básicos 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.)

   Os algoritmos e 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 novos algoritmos e estruturas de dados. É pretenção desta disciplina fornecer aos estudantes elementos e técnicas que possam auxiliá-los a projetarem bons algoritmos e 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 110 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, P₁, P₂ e P₃. Todas as provas serão às terças-feiras. A primeira prova será no dia 18 de setembro, a segunda no dia ? de outubro, e a terceira no dia ? de novembro. A média mp = (P₁ + 2 P₂ + 2 P₃)/5 das provas representará 2/3 da nota final. Para que o aluno seja aprovado é necessário que mp seja pelo menos 5 (cinco).

Exercícios-programas

Durante o semestre desenvolveremos exercícios-programas. Cada exercício-programa valerá um certo número de pontos. A média mep das notas dos exercícios-programas representará 1/3 da nota final. Para que o aluno seja aprovado é necessário que mep seja pelo menos 5 (cinco).

Nota final

A nota final nf será calculada da através da execução da função nota_final(mp, mep).

   #define min(m,n) ((m) < (n) ? (m) : (n))
    
   float
   nota_final (float mp, float mep)
   {
     if (mp < 5 || mep < 5) return min(mp,mep);
     return (2*mp + mep)/3;
   } 

Normas de recuperação

Os alunos que ficaram com nota final nf maior ou igual a 3.0 e menor que 5.0 terão direito a fazer a recuperação. A Recuperação será feita da seguinte forma:

• se sua nota de provas durante o semestre foi menor que 5.0, então você deverá fazer uma prova no dia 18 de fevereiro de 2002.

• se sua nota de exercícios durante o semestre foi menor que 5.0, então você deverá entregar até o dia 18 de fevereiro de 2002 o exercício-programa de recuperação.

A nota de recuperação nr será dada por:

• se você fez apenas a prova, nr = nota da prova.
• se você fez apenas o exercício, nr = nota do exercício.
• se você fez ambos, nr = (nota da prova + nota do exercício)/2.

A nota final da disciplina para aqueles que fizerem recuperação será dada por (nf + 2*nr)/3.

5. Alguns tópicos que pretendemos cobrir

Pretendemos cobrir os tópicos elementares em projetos de algoritmos. Alguns destes tópicos (não necessariamente nesta ordem) são:

1. recursão;
2. busca em um vetor;
3. busca (binária) em vetor ordenado;
4. listas lineares: filas e pilhas;
5. listas encadeadas;
6. algoritmos de enumeração: backtracking;
7. busca de palavras em um texto;
8. algoritmos de ordenação: bublesort, heapsort, mergesort, ...
9. filas de prioridades (heaps);
Tudo isso regado a muita análise de algoritmos e invariantes.

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) e as notas de aulas de Projetos de Algoritmos do professor Paulo Feofiloff. Também estarei seguindo mais ou menos de perto o livro

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

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

http://www.ime.usp.br/~coelho/mac122/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 é Alexandre Murakami, e-mail murakami@linux.ime.usp.br. O Alexandre estará no plantão de dúvidas de 2as. e 4as. das 12:00 às 13:00, lá no CEC (acho que na sala 5 do CEC tem uma mesinha para monitores). As 3as. e 5as. o Manoel, monitor da turma do básico, estará no plantão de dúvidas.

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 122 no URL

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

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/mac122/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.