apostila

feito.

Hoje em dia se trocam os quatro pneus de um carro de fo´rmula 1, com direito a
completar o tanque de gasolina, em cerca de 6 segundos.

Ah, o tal piloto foi campea˜o naquele ano, pois tambe´m usou o truque de aquecer

2.3. CONCLUSA˜O 13

os pneus antes da prova e andar com o carro contendo metade da gasolina, ja´ que ele
ia ter que parar nos boxes de qualquer maneira para trocar os pneus. . . O cara e´ um
geˆnio.

2.3 Conclusa˜o

Mesmo para um problema simples existem diversas soluc¸o˜es. A escolha da melhor
depende de va´rios fatores. Por exemplo, se a resposta deve ser exata ou na˜o ou se os
conhecimentos pre´vios necessa´rios esta˜o dispon´ıveis, e assim por diante.

E´ importante notar que somente apo´s uma se´rie de considerac¸o˜es e´ poss´ıvel escolher
a melhor te´cnica e somente em seguida executar a tarefa.

Algumas soluc¸o˜es existem a noc¸a˜o de paralelismo. Hoje em dia os computadores
veˆm com va´rios nu´cleos de processamento e sempre existe a chance de se tentar quebrar
um problema em va´rios outros menores e deixar que va´rios processadores resolvam
seus pedac¸os de soluc¸a˜o e depois tentar juntar os resultados com mais alguma operac¸a˜o
simples.

No caso da fo´rmula 1 isto funcionou, mas em geral na˜o e´ verdade. Infelizmente
existe o problema da dependeˆncia de dados. Por exemplo, o mecaˆnico que vai colocar
a roda nova so´ pode trabalhar depois que o outro tirou a roda velha. Em problemas
com alto grau de dependeˆncia, paralelizar e´ complicado.1.

1Na˜o se estudara˜o algoritmos paralelos nesta disciplina.

14 CAPI´TULO 2. SOBRE PROBLEMAS E SOLUC¸O˜ES

Cap´ıtulo 3

Sobre algoritmos e programas

Apo´s o estudo do problema, ana´lise das diversas possibilidades de soluc¸a˜o e a escolha
da melhor delas, cabe agora a tarefa de escrever um programa que implemente esta
soluc¸a˜o. Antes, contudo, e´ preciso saber a diferenc¸a entre um algoritmo em um
programa. Isto sera´ discutido neste cap´ıtulo.

3.1 O que e´ um algoritmo?

Um algoritmo e´ uma sequeˆncia extremamente precisa de instruc¸o˜es que, quando lida
e executada por uma outra pessoa, produz o resultado esperado, isto e´, a soluc¸a˜o de
um problema. Esta sequeˆncia de instruc¸o˜es e´ nada mais nada menos que um registro
escrito da sequeˆncia de passos necessa´rios que devem ser executados para manipular
informac¸o˜es, ou dados, para se chegar na resposta do problema.

Isto serve por dois motivos: o primeiro e´ que atrave´s do registro se garante que
na˜o havera´ necessidade de se redescobrir a soluc¸a˜o quando muito tempo tiver passado
e todos tiverem esquecido do problema; o outro motivo e´ que, as vezes, queremos
que outra pessoa execute a soluc¸a˜o, mas atrave´s de instruc¸o˜es precisas, de maneira
que na˜o haja erros durante o processo. Queremos um algoritmo para a soluc¸a˜o do
problema.

Uma receita de bolo de chocolate e´ um bom exemplo de um algoritmo (a lista de
ingredientes e as quantidades foram omitidas, bem como a receita da cobertura):

Bata em uma batedeira a manteiga e o ac¸u´car. Junte as gemas uma a uma

ate´ obter um creme homoge^neo. Adicione o leite aos poucos. Desligue a

batedeira e adicione a farinha de trigo, o chocolate em po´, o fermento

e reserve. Bata as claras em neve e junte-as a` massa de chocolate

misturando delicadamente. Unte uma forma retangular pequena

com manteiga e farinha e leve para assar em forno me´dio pre´-aquecido

por aproximadamente 30 minutos. Desenforme o bolo ainda

quente e reserve.

Este e´ um bom exemplo de algoritmo pois podemos extrair caracter´ısticas bastante
interessantes do texto. Em primeiro lugar, a pessoa que escreveu a receita na˜o e´

15

16 CAPI´TULO 3. SOBRE ALGORITMOS E PROGRAMAS

necessariamente a mesma pessoa que vai fazer o bolo. Logo, podemos estabelecer,
sem preju´ızo, que foi escrita por um mas sera´ executada por outro.

Outras caracter´ısticas interessantes que esta˜o impl´ıcitas sa˜o as seguintes:

• as frases sa˜o instruc¸o˜es no modo imperativo: bata isso, unte aquilo. Sa˜o ordens,
na˜o sugesto˜es. Quem segue uma receita obedece quem a escreveu;

• as instruc¸o˜es esta˜o na forma sequencial: apenas uma pessoa executa. Na˜o exis-
tem ac¸o˜es simultaˆneas.

• existe uma ordem para se executar as instruc¸o˜es: primeiro bata a manteiga e
o ac¸ucar; depois junte as gemas, uma a uma, ate´ acabar os ovos; em seguida
adicione o leite.

• algumas instruc¸o˜es na˜o sa˜o executadas imediatamente, e´ preciso entrar em um
modo de repetic¸a˜o de um conjunto de outras instruc¸o˜es: enquanto houver ovos
na˜o usados, junte mais uma gema. So´ pare quando tiver usado todos os ovos.

• algumas outras instruc¸o˜es na˜o foram mencionadas, mas sa˜o obviamente ne-
cessa´rias que ocorram: e´ preciso separar as gemas das claras antes de comec¸ar
a tarefa de se fazer o bolo, assim como e´ preciso ainda antes quebrar os ovos.

• algumas instruc¸o˜es, ou conjunto de instruc¸o˜es, podem ter a ordem invertida:
pode-se fazer primeiro a massa e depois a cobertura, ou vice-e-versa. Mas nunca
se pode colocar no forno a assadeira antes de se chegar ao te´rmino do preparo
da massa.

Mesmo levando estas coisas em considerac¸a˜o, qualquer ser humano bem treinado
em cozinha conseguiria fazer um bolo de chocolate razoa´vel com as instruc¸o˜es acima,
pois todas as receitas seguem o mesmo padra˜o. As convenc¸o˜es que esta˜o impl´ıcitas
no algoritmo sa˜o conhecidas de qualquer cozinheiro, pois seguem um formato padra˜o.

O formato padra˜o para algoritmos que vamos considerar e´ o seguinte:

• as instruc¸o˜es sera˜o escritas uma em cada linha;
• as instruc¸o˜es sera˜o executadas uma a uma, da primeira ate´ a u´ltima linha,

nesta ordem, a menos que o pro´prio algoritmo tenha instruc¸o˜es que alterem este
comportamento;

• em cada linha, uma instruc¸a˜o faz somente uma coisa;
• tudo o que esta´ impl´ıcito devera´ ser explicitado.

A figura 3.1 ilustra a receita de bolo de chocolate escrita dentro deste formato
padra˜o.

3.1. O QUE E´ UM ALGORITMO? 17

Algoritmo para fazer um bolo de chocolate.

inı´cio

Providencie todos os ingredientes da receita.

Providencie uma forma pequena.

Ligue o forno em temperatura me´dia.

Coloque a menteiga na batedeira.

Coloque o ac¸ucar na batedeira.

Ligue a batedeira.

Enquanto um creme homoge^neo n~ao for obtido, junte mais uma gema.

Adicione aos poucos o leite.

Desligue a batedeira.

Adicione a farinha de trigo.

Adicione o chocolate em po´.

Adicione o fermento.

Reserve a massa obtida em um lugar tempora´rio.

Execute o algoritmo para obter as claras em neve.

Junte as claras em neve a` massa de chocolate que estava reservada.

Misture esta massa delicadamente.

Execute o algoritmo para untar a forma com manteiga e farinha.

Coloque a forma no forno.

Espere 30 minutos.

Tire a forma do forno.

Desenforme o bolo ainda quente.

Separe o bolo em um lugar tempora´rio.

Fac¸a a cobertura segundo o algoritmo de fazer cobertura.

Coloque a cobertura no bolo.

fim.

Figura 3.1: Algoritmo para fazer bolo de chocolate.

Infelizmente, nem todos conseguem fazer o bolo, pois existem instruc¸o˜es que so-
mente os iniciados decifram:

• “adicione aos poucos”;
• “misturando delicadamente”;
• “quando o creme fica homogeˆneo?”. . .
No caso do computador a situac¸a˜o e´ pior ainda, pois trata-se de um circuito

eletroˆnico, de uma ma´quina. Por este motivo, as instruc¸o˜es devem ser precisas e
organizadas.

Um algoritmo feito para um computador executar deve tornar expl´ıcito todas as
informac¸o˜es impl´ıcitas. Tambe´m deve evitar o uso de frases amb´ıguas ou imprecisas
e deve ser o mais detalhado poss´ıvel. Tambe´m na˜o pode ter frases de significado
desconhecido.

Na pro´xima sec¸a˜o vamos desenvolver melhor este tema.

18 CAPI´TULO 3. SOBRE ALGORITMOS E PROGRAMAS

3.2 O que e´ um programa?

Um programa e´ a codificac¸a˜o em alguma