What's an algorithm? - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

Tradutor: Margarida Ferreira Revisora: Mafalda Ferreira

What's an algorithm?

O que é um algoritmo?

In computer science,

an algorithm is a set of instructions

Na informática, um algoritmo é um conjunto de instruções

for solving some problem, step-by-step.

para resolver um problema, passo a passo.

Typically, algorithms are executed by computers,

Habitualmente, os algoritmos são executados por computadores,

but we humans have algorithms as well.

mas as pessoas também têm algoritmos.

For instance, how would you go about counting

Por exemplo, como é que vocês contam o número de pessoas numa sala?

the number of people in a room?

Well, if you're like me,

Se forem como eu, provavelmente apontam para cada pessoa, uma por uma,

you probably point at each person,

one at a time,

and count up from 0:

e contam a partir do zero:

1, 2, 3, 4 and so forth.

1, 2, 3, 4, etc.

Well, that's an algorithm.

Isso é um algoritmo.

In fact, let's try to express it

Vamos tentar exprimi-lo

a bit more formally in pseudocode,

um pouco mais formalmente, em pseudocódigo,

English-like syntax

that resembles a programming language.

uma sintaxe no idioma, parecida com uma linguagem de programação.

Let n equal 0.

Vamos usar N igual a 0.

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

Para cada pessoa na sala, conjunto N = N + 1.

How to interpret this pseudocode?

Como interpretar este pseudocódigo?

Well, line 1 declares, so to speak,

A linha 1 declara, por assim dizer, uma variável N

a variable called n

and initializes its value to zero.

e inicializa o seu valor como zero.

This just means that at the beginning of our algorithm,

Isso significa que, no início do nosso algoritmo,

the thing with which we're counting

a coisa com que vamos contar tem um valor de zero.

has a value of zero.

After all, before we start counting,

Afinal, antes de começarmos a contar, ainda não contámos nada.

we haven't counted anything yet.

Calling this variable n is just a convention.

Chamar N a esta variável é apenas uma convenção.

I could have called it almost anything.

Podia ter-lhe chamado outra coisa qualquer.

Now, line 2 demarks the start of loop,

A linha 2 marca o início de um ciclo,

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

uma sequência de passos que vão repetir uma série de vezes.

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

No nosso exemplo, o passo que vamos fazer

is counting people in the room.

é contar as pessoas na sala.

Beneath line 2 is line 3,

Por baixo da linha 2 está a linha 3,

which describes exactly how we'll go about counting.

que descreve exatamente como vai continuar a contagem.

The indentation implies that it's line 3

A indentação implica que é a linha 3 que se vai repetir.

that will repeat.

So, what the pseudocode is saying

Assim, o que o pseudocódigo nos diz

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.

vamos aumentar N em mais um.

Now, is this algorithm correct?

Este algoritmo estará correto?

Well, let's bang on it a bit.

Vamos fazer uma verificação.

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

Funcionará, se estiverem duas pessoas na sala?

Let's see.

Vejamos.

In line 1, we initialize n to zero.

Na linha 1, começamos com N igual a zero.

For each of these two people,

Para cada uma dessas duas pessoas, aumentamos N em mais um.

we then increment n by 1.

So, in the first trip through the loop,

Assim, no primeiro passo do ciclo,

we update n from zero to 1,

atualizamos N de zero para 1.

on the second trip through that same loop,

No segundo passo do mesmo ciclo,

we update n from 1 to 2.

atualizamos N de 1 para 2.

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

Assim, no término deste algoritmo, N é igual a 2,

which indeed matches the number of people in the room.

o que condiz com o número de pessoas na sala.

So far, so good.

Até aqui, tudo bem.

How about a corner case, though?

Mas e se a situação for outra?

Suppose that there are zero people in the room,

Suponhamos que há zero pessoas na sala,

besides me, who's doing the counting.

para além de mim, que estou a fazer a contagem.

In line 1, we again initialize n to zero.

Na linha 1, inicializamos de novo com N igual a zero.

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

Mas, desta vez, a linha 3 não é executada

since there isn't a person in the room,

porque não há mais ninguém na sala.

and so, n remains zero,

Portanto, mantém-se em zero,

which indeed matches the number of people in the room.

o que condiz com o número de pessoas na sala.

Pretty simple, right?

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

É muito simples, não é?

Mas contar as pessoas, uma a uma, também é muito pouco eficaz.

Surely, we can do better!

Certamente, podemos fazer melhor.

Why not count two people at a time?

Podemos 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, etc.

why not count

porque é que não contamos 2, 4, 6, 8, etc.?

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

It even sounds faster, and it surely is.

Parece ser mais rápido e claro que é.

Let's express this optimization in pseudocode.

Vamos exprimir esta otimização em pseudocódigo.

Let n equal zero.

Vamos pôr N igual a zero.

For each pair of people in room,

Para cada par de pessoas na sala pomos N = N + 2.

set n = n + 2.

Pretty simple change, right?

É uma mudança simples.

Rather than count people one at a time,

Em vez de contarmos as pessoas, uma a uma,

we instead count them two at a time.

contamos duas pessoas de cada vez.

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

Este algoritmo é duas vezes mais rápido do que o anterior.

But is it correct?

Mas estará correto? Vejamos.

Let's see.

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

Funciona se houver duas pessoas na sala?

In line 1, we initialize n to zero.

Na linha 1, começamos com N igual a zero.

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

Para um par de pessoas, aumentamos N em mais 2.

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

Assim, no término do algoritmo, N é 2.

which indeed matches the number of people in the room.

o que condiz com o número de pessoas na sala.

Suppose next that there are zero people in the room.

Suponhamos agora que há zero pessoas na sala.

In line 1, we initialize n to zero.

Na linha 1, começamos com N igual a zero.

As before, line 3 doesn't execute at all

Tal como há bocado, a linha 3 não é executada

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

porque não há nenhum par de pessoas na sala,

and so, n remains zero,

portanto, mantém-se zero,

which indeed matches the number of people in the room.

o que condiz com o número de pessoas na sala.

But what if there are 3 people in the room?

E se houvesse três pessoas na sala?

How does this algorithm fair?

Como é que este algoritmo funciona?

Let's see.

Vejamos.

In line 1, we initialize n to zero.

Na linha 1, começamos com N igual a zero.

For a pair of those people,

Para um par de pessoas, aumentamos N em mais 2.

we then increment n by 2,

but then what?

E depois?

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

Não há outro par de pessoas na sala.

so line 2 no longer applies.

Por isso a linha 2 não pode ser aplicada.

And so, by this algorithm's end,

Assim, no término deste algoritmo,

n is still 2, which isn't correct.

N continua a ser 2, o que não está correto.

Indeed this algorithm is said to be buggy

Dizemos que este algoritmo é defeituoso porque tem um erro.

because it has a mistake.

Let's redress with some new pseudocode.

Tentemos com um novo pseudocódigo.

Let n equal zero.

Consideramos N igual a zero.

For each pair of people in room,

Para cada par de pessoas na sala,

set n = n + 2.

é N = N + 2.

If 1 person remains unpaired,

Se uma pessoa ficar sem par,

set n = n + 1.

será N = N + 1.

To solve this particular problem,

Para resolver este problema especial,

we've introduced in line 4 a condition,

introduzimos na linha 4 uma condição,

otherwise known as a branch,

que também é conhecida por ramificação,

that only executes if there is one person

que só se executa se houver uma só pessoa

we could not pair with another.

que não pode fazer par com outra.

So now, whether there's 1 or 3

Agora, quer haja uma ou três pessoas

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 não deixa de as contar.

Can we do even better?

Podemos melhorar ainda mais?

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

Podemos contar em grupos de três, de quatro ou de cinco ou dez,

but beyond that it's going to get

mas, para além disso,

a little bit difficult to point.

vai ser um pouco difícil de resolver.

At the end of the day,

whether executed by computers or humans,

Afinal de contas, quer sejam executados

algorithms are just a set of instructions

por computadores ou por pessoas,

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

with which to solve problems.

com os quais resolvemos problemas.

These were just three.

Estes foram apenas três.

What problem would you solve with an algorithm?

Que problema gostariam de resolver com um algoritmo?