Tip:
Highlight text to annotate it
X
O que é um algoritmo?
Em ciência da computação,
um algoritmo é um conjunto de instruções
para resolver algum problema, passo a passo.
Geralmente, algoritmos são executados por computadores,
mas, nós, humanos, também processamos algoritmos.
Por exemplo, como você contaria
o número de pessoas em uma sala?
Bem, se você é como eu,
provavelmente, você aponta a pessoa,
uma de cada vez,
e conta de zero em diante:
1, 2, 3, 4 e assim por diante.
Bem, isso é um algoritmo.
De fato, vamos tentar expressar isso
um pouco mais formalmente em pseudocódigo,
um código com sintaxe parecida com o inglês
que lembra uma linguagem de programação.
Faça n igual a 0.
Para cada pessoa na sala, determine que n = n + 1.
Como interpretar este pseudocódigo?
Bem, a linha 1 declara, digamos,
uma variável chamada n
e inicia seu valor em zero.
Isto significa apenas que no início de nosso algoritmo,
a coisa com a qual estamos contando,
tem o valor de zero.
Afinal, antes de começarmos a contar,
não contamos nada ainda.
Chamar essa variável de n é somente uma convenção.
Eu poderia tê-la chamado de qualquer coisa.
Agora, a linha dois demarca o início do circuito,
uma sequência de passos que se repetirão um número de vezes.
Assim, em nosso exemplo, o passo que estamos dando
é contar pessoas na sala.
Abaixo da linha 2 está a linha 3,
que descreve exatamente como iremos contar.
O recuo significa que é a linha 3
que se repetirá.
Então, o que o pseudocódigo está dizendo
é que depois de começar em zero,
para cada pessoa na sala,
somaremos 1 a n.
Agora, este algoritmo está correto?
Bem, vamos trabalhar nele um pouco.
Ele funciona se há duas pessoas na sala?
Vejamos.
Na linha 1, começamos com zero para n.
Para cada uma dessas duas pessoas,
acrescentamos 1 a n.
Então, no primeiro passo pelo circuito,
atualizamos n de zero para 1,
no segundo passo pelo mesmo circuito,
atualizamos n de 1 para 2.
Portanto, no final deste algoritmo, n é 2,
que, de fato, é o número de pessoas na sala.
Até aqui, tudo bem.
Que tal algo mais complicado?
Suponha que não há pessoas na sala,
além de mim, que estou fazendo a contagem.
Na linha 1, novamente iniciamos com zero para n.
Desta vez, entretanto, a linha 3 não se processa,
já que não há uma pessoa na sala,
e, portanto, n permanece zero,
que, de fato, é o número de pessoas na sala.
Bem simples, certo?
Mas contar pessoas uma de cada vez é bem ineficiente mesmo, não é?
Claro, podemos fazer melhor!
Por que não contar duas pessoas de cada vez?
Em vez de contar 1, 2, 3, 4, 5, 6, 7, 8 e assim por diante,
por que não contar
2, 4, 6, 8 e assim por diante?
Parece até mais rápido, e com certeza é.
Vamos expressar essa otimização em pseudocódigo.
Deixamos n igual a zero.
Para cada par de pessoas na sala,
determinamos que n = n + 2.
Mudança bem simples, certo?
Ao invés de contar pessoas uma de cada vez,
contamos aos pares.
Este algoritmo é, portanto, duas vezes mais rápido que o último.
Mas, está correto?
Vejamos.
Ele funciona se há duas pessoas na sala?
Na linha um, iniciamos com zero para n.
Para essa dupla de pessoas, acrescentamos 2 a n.
Então, no final deste algoritmo, n é 2,
que, de fato, é o número de pessoas na sala.
A seguir, suponha que não há ninguém na sala.
Na linha 1, começamos com zero para n.
Como anteriormente, a linha 3 não se processa
já que não há pares de pessoas na sala,
então, n permanece zero,
que, de fato, é o número de pessoas na sala.
Mas, e se há 3 pessoas na sala?
Como esse algoritmo se comporta?
Vejamos.
Na linha 1, começamos com zero para n.
Para uma dupla de pessoas,
acrescentamos 2 a n,
mas, e aí?
Não há um outro par de pessoas na sala,
então a linha 2 não se aplica mais.
E, portanto, ao final do algoritmo,
n ainda é 2, o que não é correto.
Na verdade, diz-se que esse algoritmo é falho
porque contém um erro.
Vamos corrigir com um novo pseudocódigo.
Façamos n igual a zero.
Para cada par de pessoas na sala,
determinamos n = n + 2.
Se 1 pessoa permanece isolada,
determinamos n = n + 1.
Para resolver este problema específico,
introduzimos na linha 4 uma condição,
também conhecida como ramal,
que só é executada se há uma pessoa
que não formou par com outra.
Agora, se há 1 ou 3,
ou qualquer número ímpar de pessoas na sala,
este algoritmo irá contá-las.
Podemos fazer melhor?
Bem, poderíamos contar em grupos de 3, 4 ou mesmo 5 e 10,
mas, além disso, vai ficar
um pouco difícil apontar.
No fim das contas,
sejam executados por computadores ou por humanos,
os algoritmos são apenas um conjunto de instruções
com que resolvemos problemas.
Estes foram apenas três.
Qual problema você resolveria com um algoritmo?