2.3 um Algoritmo Computacional Simples

EXERCÍCIO 2.1

Escreva um algoritmo para fritar um ovo. Se não souber, escreva mesmo assim e depois pergunte a alguém que saiba. Houve

muita diferença? Você esqueceu algum detalhe?

 

EXERCÍCIO 2.2

Imagine que você vai ensinar a uma criança de 6 anos, já alfabetizada, a procurar uma palavra no dicionário. Escreva um passo a

passo de suas instruções.

 

Ada, a primeira programadora

Ada Lovelace é considerada a primeira pessoa que escreveu um algoritmo para ser processado por máquina. Nascida em 1815, trabalhou com Charles Babbage quando este estava desenvolvendo a sua máquina analítica, uma das primeiras ideias de construção de computadores. Entre os anos de 1842 e 1843, Ada escreveu o que é considerado o primeiro algoritmo computacional, descrevendo como calcular a Sequência de Bernoulli por intermédio da máquina desenvolvida por Babbage. Infelizmente, a máquina de Babbage não chegou a ser construída no decorrer de sua vida.

 

Figura 2.2 Ada Lovelace. Fonte: Wikimedia Commons.

 

2.3 UM ALGORITMO COMPUTACIONAL SIMPLES

O Coelho Branco pôs os óculos: “Por onde devo começar? Por favor, Majestade.”, perguntou. “Comece pelo início”, disse o rei com muita gravidade, “vá até o final, então pare.” Lewis Carroll, Alice no País das Maravilhas, 1865.

Vamos tentar pensar “algoritmicamente”. Pensar algoritmicamente aqui é o mesmo que pensar com as limitações de um computador. Imagine que você tenha que procurar o significado da palavra “pneumoultramicroscopicossilicovulcanoconitico” em um dicionário. Sei que em tempos atuais dicionários de papel estão em desuso, mas façamos este exercício mental, mesmo que você não utilize mais dicionários em papel.

Os computadores são bons em executar tarefas repetitivas. Para tanto temos de descobrir um

padrão de comportamento e, em seguida, especificar esse padrão de modo que o computador possa executá-lo. Lembre-se: computadores não têm inteligência e, portanto, nada sabem sobre a organização de dicionários. Precisamos ensinar-lhes tudo.

Vamos começar com uma solução ruim, porém extremamente simples, para ensinar a um

computador como achar uma palavra em um dicionário. A maneira mais simples e menos inteligente de fazer esta busca é olhar palavra por palavra, desde a primeira até encontrarmos a palavra procurada. Se chegarmos ao final do dicionário é porque este não contém uma definição para a palavra, que talvez não exista em nossa língua. Meu primeiro passo é escrever uma solução em prosa, sem me preocupar com detalhes. Minha solução poderia ser:

Leia cada palavra do dicionário até encontrar a palavra procurada ou não restarem

mais palavras a serem lidas. Se encontrar a palavra, imprima seu significado.

Esta primeira solução é apenas um aquecimento. Serve para você pensar em como resolver seu

problema, sem entrar em detalhes. Neste ponto você se preocupa apenas em esboçar uma solução. Esta solução ainda não é um algoritmo computacional; não tem detalhes suficientes para poder ser traduzida em uma linguagem de programação. Não tente resolver o problema de uma vez. Pode parecer perda de tempo começar de maneira tão abstrata e depois ir refinando a solução, com mais detalhes. Afinal você poderia pensar desde já em vários aspectos importantes da solução, mas eu lhe asseguro de que suas chances de sucesso serão bem maiores se você seguir este método.

Vamos em seguida especificar melhor o que queremos. Quais detalhes ainda faltam? Você imagina

que “Ler uma palavra” é algo que o computador saiba fazer. Se não souber, teremos de detalhar este passo no futuro, mas o que quer dizer “cada palavra”? Precisamos solicitar ao computador que leia a primeira palavra, depois a segunda, depois a terceira, e assim por diante até encontrar a palavra desejada ou o final da lista de palavras. Nosso computador é como uma criança com um vocabulário limitado a quem temos de ensinar o significado de cada comando. Assim, detalhamos nossa solução.

Leia a primeira palavra do dicionário. Se esta palavra for a palavra procurada, i

mprima seu significado e termine. Se não for, leia a palavra seguinte até encontr

ar a palavra procurada ou não existirem mais palavras a serem lidas.

Nesse ponto, nossa prosa está mais próxima de um algoritmo. Mas ainda faltam detalhes para um

computador. Vamos agora dividir em passos.

Algoritmo que busca a definição de uma palavra em um dicionário:

Passo 1: Leia a primeira palavra do dicionário.

Passo 2: Se for a palavra procurada, imprima a definição e termine.

Passo 3: Se for a última palavra, imprima “Palavra não existe” e termine.

Passo 4: Leia a próxima palavra.

Passo 5: Volte para o passo 2.

Este algoritmo seria a forma de solução a que intuitivamente poderíamos chegar. Apesar de correta,

não é a melhor forma de solução computacional. Quando um computador tiver de repetir uma mesma tarefa, é melhor indicarmos isso de imediato, antes dos comandos que serão repetidos. No algoritmo apresentado, apenas no passo 5 aparece uma ordem de repetição, na forma de um desvio do fluxo de execução do algoritmo. Nos primórdios da Computação era comum usarmos comandos como este do passo 5. Com o aumento da complexidade dos programas, notou-se que comandos que desviam o fluxo de execução criavam um código difícil de corrigir, pois não podemos ter certeza do local em que o programa está executando em cada momento. Em nosso exemplo simples, isto não é evidente, mas imagine um programa com milhares de linhas de código e centenas de desvios. Criou-se até um termo pejorativo para este tipo de código: código espaguete. A solução encontrada foi usar blocos de comandos que são repetidos de acordo com uma condição. Com isto controlamos melhor o fluxo de execução de um algoritmo e sempre sabemos qual parte do código está sendo executada. É a chamada Programação Estruturada. Vamos modificar nosso algoritmo, antecipando o comando de repetição e detalhando melhor cada passo.

Algoritmo que busca a definição de uma palavra em um dicionário:

Passo 1: Leia a primeira palavra do dicionário.

Passo 2: Repita:

Passo 2.1: Se a palavra lida for a palavra procurada, faça:

Passo 2.1.1: Imprima a definição

Passo 2.1.2: Termine a execução do algoritmo.

Passo 2.2: Se for a última palavra:

Passo 2.2.1: Imprima “Palavra não existe”

Passo 2.2.2: Termine a execução do algoritmo.

Passo 2.2: Leia a próxima palavra.

Esta forma de apresentar um algoritmo ainda é visualmente confusa. Para melhorar seu aspecto, foi

convencionado que subpassos como 2.1 ou 2.1.1 seriam identados, ou seja, vamos deslocar seu início na linha para que visualmente possamos identificar os blocos de execução. Vejamos como ficaria:

Algoritmo que busca a definição de uma palavra em um dicionário:

Leia a primeira palavra do dicionário.

Repita:

Se a palavra lida for a palavra procurada:

Imprima a definição

Termine a execução do algoritmo.

Se for a última palavra:

Imprima “Palavra não existe”

Termine a execução do algoritmo.

Leia a próxima palavra.

Cada vez que um passo do algoritmo é deslocado na coluna da linha, quer dizer que este comando

é um subpasso do passo anterior que começa em uma coluna menor. Esta é a forma usual de apresentar algoritmos. Desta maneira, não precisamos numerar cada passo e visualmente identificamos os blocos de execução.

Perceba que a solução apresentada não é boa. Não usamos o fato do dicionário ser organizado

alfabeticamente e podemos fazer melhor. Mas esta solução é simples o suficiente para podermos apresentar alguns conceitos da especificação de algoritmos. Na próxima seção, apresento maneiras de formalizar a sua escrita.

Dica 2.4 – Comece a solução com uma ideia abstrata e depois re ne.

 

Este exemplo ensina algo importante: quando for pensar em uma solução algorítmica para um problema, comece com uma ideia

bem abstrata e, aos poucos, aproxime sua ideia do que um computador pode fazer, auxiliado por uma linguagem de programação.

Somente quando o algoritmo tiver detalhamento su ciente, implemente-o com uma linguagem de programação.

 

EXERCÍCIO 2.3

Como seria o algoritmo desta seção se levarmos em conta que um dicionário é organizado alfabeticamente? Escreva uma nova

versão considerando esta característica.

 

EXERCÍCIO 2.4

Imagine uma máquina que possua somente as operações aritméticas de soma e subtração. Escreva um algoritmo para fazer

uma multiplicação.