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