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