What's an algorithm? - David J. Malan

Seu cérebro pode resolver algoritmos - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

Tradutor: Isabel Villan Revisor: Viviane Ferraz Matos

What's an algorithm?

O que é um algoritmo?

In computer science,

Em ciência da computação,

an algorithm is a set of instructions

um algoritmo é um conjunto de instruções

for solving some problem, step-by-step.

para resolver algum problema, passo a passo.

Typically, algorithms are executed by computers,

Geralmente, algoritmos são executados por computadores,

but we humans have algorithms as well.

mas, nós, humanos, também processamos algoritmos.

For instance, how would you go about counting

Por exemplo, como você contaria

the number of people in a room?

o número de pessoas em uma sala?

Well, if you're like me,

Bem, se você é como eu,

you probably point at each person,

provavelmente, você aponta a pessoa,

one at a time,

uma de cada vez,

and count up from 0:

e conta de zero em diante:

1, 2, 3, 4 and so forth.

1, 2, 3, 4 e assim por diante.

Well, that's an algorithm.

Bem, isso é um algoritmo.

In fact, let's try to express it

De fato, vamos tentar expressar isso

a bit more formally in pseudocode,

um pouco mais formalmente em pseudocódigo,

English-like syntax

that resembles a programming language.

um código com sintaxe parecida com o inglês

que lembra uma linguagem de programação.

Let n equal 0.

Faça n igual a 0.

For each person in room, set n = n + 1.

Para cada pessoa na sala, determine que n = n + 1.

How to interpret this pseudocode?

Como interpretar este pseudocódigo?

Well, line 1 declares, so to speak,

Bem, a linha 1 declara, digamos,

a variable called n

uma variável chamada n

and initializes its value to zero.

e inicia seu valor em zero.

This just means that at the beginning of our algorithm,

Isto significa apenas que no início de nosso algoritmo,

the thing with which we're counting

a coisa com a qual estamos contando,

has a value of zero.

tem o valor de zero.

After all, before we start counting,

Afinal, antes de começarmos a contar,

we haven't counted anything yet.

não contamos nada ainda.

Calling this variable n is just a convention.

Chamar essa variável de n é somente uma convenção.

I could have called it almost anything.

Eu poderia tê-la chamado de qualquer coisa.

Now, line 2 demarks the start of loop,

Agora, a linha dois demarca o início do circuito,

a sequence of steps that will repeat some number of times.

uma sequência de passos que se repetirão um número de vezes.

So, in our example, the step we're taking

Assim, em nosso exemplo, o passo que estamos dando

is counting people in the room.

é contar pessoas na sala.

Beneath line 2 is line 3,

Abaixo da linha 2 está a linha 3,

which describes exactly how we'll go about counting.

que descreve exatamente como iremos contar.

The indentation implies that it's line 3

O recuo significa que é a linha 3

that will repeat.

que se repetirá.

So, what the pseudocode is saying

Então, o que o pseudocódigo está dizendo

is that after starting at zero,

é que depois de começar em zero,

for each person in the room,

para cada pessoa na sala,

we'll increase n by 1.

somaremos 1 a n.

Now, is this algorithm correct?

Agora, este algoritmo está correto?

Well, let's bang on it a bit.

Bem, vamos trabalhar nele um pouco.

Does it work if there are 2 people in the room?

Ele funciona se há duas pessoas na sala?

Let's see.

Vejamos.

In line 1, we initialize n to zero.

Na linha 1, começamos com zero para n.

For each of these two people,

Para cada uma dessas duas pessoas,

we then increment n by 1.

acrescentamos 1 a n.

So, in the first trip through the loop,

Então, no primeiro passo pelo circuito,

we update n from zero to 1,

atualizamos n de zero para 1,

on the second trip through that same loop,

no segundo passo pelo mesmo circuito,

we update n from 1 to 2.

atualizamos n de 1 para 2.

And so, by this algorithm's end, n is 2,

Portanto, no final deste algoritmo, n é 2,

which indeed matches the number of people in the room.

que, de fato, é o número de pessoas na sala.

So far, so good.

Até aqui, tudo bem.

How about a corner case, though?

Que tal algo mais complicado?

Suppose that there are zero people in the room,

Suponha que não há pessoas na sala,

besides me, who's doing the counting.

além de mim, que estou fazendo a contagem.

In line 1, we again initialize n to zero.

Na linha 1, novamente iniciamos com zero para n.

This time, though, line 3 doesn't execute at all

Desta vez, entretanto, a linha 3 não se processa,

since there isn't a person in the room,

já que não há uma pessoa na sala,

and so, n remains zero,

e, portanto, n permanece zero,

which indeed matches the number of people in the room.

que, de fato, é o número de pessoas na sala.

Pretty simple, right?

Bem simples, certo?

But counting people one a time is pretty inefficient, too, no?

Mas contar pessoas uma de cada vez é bem ineficiente mesmo, não é?

Surely, we can do better!

Claro, podemos fazer melhor!

Why not count two people at a time?

Por que não contar duas pessoas de cada vez?

Instead of counting 1, 2, 3, 4, 5, 6, 7, 8, and so forth,

Em vez de contar 1, 2, 3, 4, 5, 6, 7, 8 e assim por diante,

why not count

por que não contar

2, 4, 6, 8, and so on?

2, 4, 6, 8 e assim por diante?

It even sounds faster, and it surely is.

Parece até mais rápido, e com certeza é.

Let's express this optimization in pseudocode.

Vamos expressar essa otimização em pseudocódigo.

Let n equal zero.

Deixamos n igual a zero.

For each pair of people in room,

Para cada par de pessoas na sala,

set n = n + 2.

determinamos que n = n + 2.

Pretty simple change, right?

Mudança bem simples, certo?

Rather than count people one at a time,

Ao invés de contar pessoas uma de cada vez,

we instead count them two at a time.

contamos aos pares.

This algorithm's thus twice as fast as the last.

Este algoritmo é, portanto, duas vezes mais rápido que o último.

But is it correct?

Mas, está correto?

Let's see.

Vejamos.

Does it work if there are 2 people in the room?

Ele funciona se há duas pessoas na sala?

In line 1, we initialize n to zero.

Na linha um, iniciamos com zero para n.

For that one pair of people, we then increment n by 2.

Para essa dupla de pessoas, acrescentamos 2 a n.

And so, by this algorithm's end, n is 2,

Então, no final deste algoritmo, n é 2,

which indeed matches the number of people in the room.

que, de fato, é o número de pessoas na sala.

Suppose next that there are zero people in the room.

A seguir, suponha que não há ninguém na sala.

In line 1, we initialize n to zero.

Na linha 1, começamos com zero para n.

As before, line 3 doesn't execute at all

Como anteriormente, a linha 3 não se processa

since there aren't any pairs of people in the room,

já que não há pares de pessoas na sala,

and so, n remains zero,

então, n permanece zero,

which indeed matches the number of people in the room.

que, de fato, é o número de pessoas na sala.

But what if there are 3 people in the room?

Mas, e se há 3 pessoas na sala?

How does this algorithm fair?

Como esse algoritmo se comporta?

Let's see.

Vejamos.

In line 1, we initialize n to zero.

Na linha 1, começamos com zero para n.

For a pair of those people,

Para uma dupla de pessoas,

we then increment n by 2,

acrescentamos 2 a n,

but then what?

mas, e aí?

There isn't another full pair of people in the room,

Não há um outro par de pessoas na sala,

so line 2 no longer applies.

então a linha 2 não se aplica mais.

And so, by this algorithm's end,

E, portanto, ao final do algoritmo,

n is still 2, which isn't correct.

n ainda é 2, o que não é correto.

Indeed this algorithm is said to be buggy

Na verdade, diz-se que esse algoritmo é falho

because it has a mistake.

porque contém um erro.

Let's redress with some new pseudocode.

Vamos corrigir com um novo pseudocódigo.

Let n equal zero.

Façamos n igual a zero.

For each pair of people in room,

Para cada par de pessoas na sala,

set n = n + 2.

determinamos n = n + 2.

If 1 person remains unpaired,

Se 1 pessoa permanece isolada,

set n = n + 1.

determinamos n = n + 1.

To solve this particular problem,

Para resolver este problema específico,

we've introduced in line 4 a condition,

introduzimos na linha 4 uma condição,

otherwise known as a branch,

também conhecida como ramal,

that only executes if there is one person

que só é executada se há uma pessoa

we could not pair with another.

que não formou par com outra.

So now, whether there's 1 or 3

Agora, se há 1 ou 3,

or any odd number of people in the room,

ou qualquer número ímpar de pessoas na sala,

this algorithm will now count them.

este algoritmo irá contá-las.

Can we do even better?

Podemos fazer melhor?

Well, we could count in 3's or 4's or even 5's and 10's,

Bem, poderíamos contar em grupos de 3, 4 ou mesmo 5 e 10,

but beyond that it's going to get

mas, além disso, vai ficar

a little bit difficult to point.

um pouco difícil apontar.

At the end of the day,

No fim das contas,

whether executed by computers or humans,

sejam executados por computadores ou por humanos,

algorithms are just a set of instructions

os algoritmos são apenas um conjunto de instruções

with which to solve problems.

com que resolvemos problemas.

These were just three.

Estes foram apenas três.

What problem would you solve with an algorithm?

Qual problema você resolveria com um algoritmo?