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\u2dco naquele ano, pois tambe´m usou o truque de aquecer
2.3. CONCLUSA\u2dcO 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\u2c6nio.
2.3 Conclusa\u2dco
Mesmo para um problema simples existem diversas soluc¸o\u2dces. A escolha da melhor
depende de va´rios fatores. Por exemplo, se a resposta deve ser exata ou na\u2dco ou se os
conhecimentos pre´vios necessa´rios esta\u2dco dispon´\u131veis, e assim por diante.
E´ importante notar que somente apo´s uma se´rie de considerac¸o\u2dces e´ poss´\u131vel escolher
a melhor te´cnica e somente em seguida executar a tarefa.
Algumas soluc¸o\u2dces existem a noc¸a\u2dco de paralelismo. Hoje em dia os computadores
ve\u2c6m 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\u2dco e depois tentar juntar os resultados com mais alguma operac¸a\u2dco
simples.
No caso da fo´rmula 1 isto funcionou, mas em geral na\u2dco e´ verdade. Infelizmente
existe o problema da depende\u2c6ncia de dados. Por exemplo, o meca\u2c6nico que vai colocar
a roda nova so´ pode trabalhar depois que o outro tirou a roda velha. Em problemas
com alto grau de depende\u2c6ncia, paralelizar e´ complicado.1.
1Na\u2dco se estudara\u2dco algoritmos paralelos nesta disciplina.
14 CAPI´TULO 2. SOBRE PROBLEMAS E SOLUC¸O\u2dcES
Cap´\u131tulo 3
Sobre algoritmos e programas
Apo´s o estudo do problema, ana´lise das diversas possibilidades de soluc¸a\u2dco e a escolha
da melhor delas, cabe agora a tarefa de escrever um programa que implemente esta
soluc¸a\u2dco. Antes, contudo, e´ preciso saber a diferenc¸a entre um algoritmo em um
programa. Isto sera´ discutido neste cap´\u131tulo.
3.1 O que e´ um algoritmo?
Um algoritmo e´ uma seque\u2c6ncia extremamente precisa de instruc¸o\u2dces que, quando lida
e executada por uma outra pessoa, produz o resultado esperado, isto e´, a soluc¸a\u2dco de
um problema. Esta seque\u2c6ncia de instruc¸o\u2dces e´ nada mais nada menos que um registro
escrito da seque\u2c6ncia de passos necessa´rios que devem ser executados para manipular
informac¸o\u2dces, 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\u2dco havera´ necessidade de se redescobrir a soluc¸a\u2dco 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\u2dco, mas atrave´s de instruc¸o\u2dces precisas, de maneira
que na\u2dco haja erros durante o processo. Queremos um algoritmo para a soluc¸a\u2dco 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´\u131sticas bastante
interessantes do texto. Em primeiro lugar, a pessoa que escreveu a receita na\u2dco e´
15
16 CAPI´TULO 3. SOBRE ALGORITMOS E PROGRAMAS
necessariamente a mesma pessoa que vai fazer o bolo. Logo, podemos estabelecer,
sem preju´\u131zo, que foi escrita por um mas sera´ executada por outro.
Outras caracter´\u131sticas interessantes que esta\u2dco impl´\u131citas sa\u2dco as seguintes:
\u2022 as frases sa\u2dco instruc¸o\u2dces no modo imperativo: bata isso, unte aquilo. Sa\u2dco ordens,
na\u2dco sugesto\u2dces. Quem segue uma receita obedece quem a escreveu;
\u2022 as instruc¸o\u2dces esta\u2dco na forma sequencial: apenas uma pessoa executa. Na\u2dco exis-
tem ac¸o\u2dces simulta\u2c6neas.
\u2022 existe uma ordem para se executar as instruc¸o\u2dces: primeiro bata a manteiga e
o ac¸ucar; depois junte as gemas, uma a uma, ate´ acabar os ovos; em seguida
adicione o leite.
\u2022 algumas instruc¸o\u2dces na\u2dco sa\u2dco executadas imediatamente, e´ preciso entrar em um
modo de repetic¸a\u2dco de um conjunto de outras instruc¸o\u2dces: enquanto houver ovos
na\u2dco usados, junte mais uma gema. So´ pare quando tiver usado todos os ovos.
\u2022 algumas outras instruc¸o\u2dces na\u2dco foram mencionadas, mas sa\u2dco 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.
\u2022 algumas instruc¸o\u2dces, ou conjunto de instruc¸o\u2dces, 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\u2dco, qualquer ser humano bem treinado
em cozinha conseguiria fazer um bolo de chocolate razoa´vel com as instruc¸o\u2dces acima,
pois todas as receitas seguem o mesmo padra\u2dco. As convenc¸o\u2dces que esta\u2dco impl´\u131citas
no algoritmo sa\u2dco conhecidas de qualquer cozinheiro, pois seguem um formato padra\u2dco.
O formato padra\u2dco para algoritmos que vamos considerar e´ o seguinte:
\u2022 as instruc¸o\u2dces sera\u2dco escritas uma em cada linha;
\u2022 as instruc¸o\u2dces sera\u2dco executadas uma a uma, da primeira ate´ a u´ltima linha,
nesta ordem, a menos que o pro´prio algoritmo tenha instruc¸o\u2dces que alterem este
comportamento;
\u2022 em cada linha, uma instruc¸a\u2dco faz somente uma coisa;
\u2022 tudo o que esta´ impl´\u131cito devera´ ser explicitado.
A figura 3.1 ilustra a receita de bolo de chocolate escrita dentro deste formato
padra\u2dco.
3.1. O QUE E´ UM ALGORITMO? 17
Algoritmo para fazer um bolo de chocolate.
in\u131´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\u2dces que so-
mente os iniciados decifram:
\u2022 \u201cadicione aos poucos\u201d;
\u2022 \u201cmisturando delicadamente\u201d;
\u2022 \u201cquando o creme fica homoge\u2c6neo?\u201d. . .
No caso do computador a situac¸a\u2dco e´ pior ainda, pois trata-se de um circuito
eletro\u2c6nico, de uma ma´quina. Por este motivo, as instruc¸o\u2dces devem ser precisas e
organizadas.
Um algoritmo feito para um computador executar deve tornar expl´\u131cito todas as
informac¸o\u2dces impl´\u131citas. Tambe´m deve evitar o uso de frases amb´\u131guas ou imprecisas
e deve ser o mais detalhado poss´\u131vel. Tambe´m na\u2dco pode ter frases de significado
desconhecido.
Na pro´xima sec¸a\u2dco 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\u2dco em alguma