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 é conhecimento de técnicas básicas de programação que são vistos em MAC 110 Introdução à Computação.

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 quintas-feiras. A primeira prova será no dia 29 de setembro, a segunda no dia 1 de dezembro e a terceira no dia 8 de dezembro. A média das provas será mp = max{(P₁ + 2 P₂)/3, (P₁ + 2 P₃)/3, (P₂ + P₃)/2}. Essa média representará 60% 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á 40% 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 0.6*mp +0.4*mep;
   } 

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 prova de recuperação. A prova de recuperação será feita no dia 15 de dezembro. A nota final da disciplina para aqueles que fizerem recuperação será dada por (nf + 2*nr)/3, onde nr é a nota da prova de recuperação.
Note que não haverá exercício-programa de recuperação. Quem ficar de recuperação devido somente a média de exercícios-programas também deverá fazer a prova de recuperação.

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);

Para descrevermos as estruturas de dados e os algoritmos que manipulam estas estruturas faremos uso da linguagem de programação C.