What's an algorithm? - David J. Malan

Il cervello può risolvere algoritmi - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

Traduttore: Claudio Dinapoli Revisore: Anna Cristiana Minoli

What's an algorithm?

Cos'è un algoritmo?

In computer science,

Nella scienza informatica,

an algorithm is a set of instructions

un algoritmo è una serie di istruzioni

for solving some problem, step-by-step.

per risolvere, passo dopo passo, alcuni problemi.

Typically, algorithms are executed by computers,

In genere gli algoritmi sono eseguiti da computer,

but we humans have algorithms as well.

ma anche noi esseri umani abbiamo in nostri algoritmi.

For instance, how would you go about counting

Ad esempio: come approcci il problema di contare

the number of people in a room?

il numero di persone in una stanza?

Well, if you're like me,

Be', se tu fossi come me,

you probably point at each person,

probabilmente indicheresti ciascun presente,

one at a time,

uno alla volta,

and count up from 0:

e conteresti a partire da 0:

1, 2, 3, 4 and so forth.

1, 2, 3, 4 eccetera eccetera.

Well, that's an algorithm.

Bene, quello è un algoritmo.

In fact, let's try to express it

Infatti, cerchiamo di esprimerlo

a bit more formally in pseudocode,

un po' più formalmente come un pseudocodice,

English-like syntax

that resembles a programming language.

una sintassi simile al lunguaggio umano

con le apparenze di un linguaggio di programmazione.

Let n equal 0.

Ammettiamo n uguale a 0.

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

Per ciascuna persona nella stanza, impostiamo n = n + 1.

How to interpret this pseudocode?

Come si interpreta questo pseudocodice?

Well, line 1 declares, so to speak,

Be', la linea 1 dichiara, per dire,

a variable called n

una variabile chiamata n

and initializes its value to zero.

a cui assegniamo un valore pari a zero.

This just means that at the beginning of our algorithm,

Questo significa solo che all'inizio del nostro algoritmo

the thing with which we're counting

la cosa con cui stiamo contando

has a value of zero.

parte dal valore zero.

After all, before we start counting,

Dopotutto, prima di iniziare a contare,

we haven't counted anything yet.

non abbiamo ancora contato nulla.

Calling this variable n is just a convention.

Chiamare questa variabile 'n' è solo una consuetudine.

I could have called it almost anything.

Avrei potuto assegnargli quasi qualsiasi nome.

Now, line 2 demarks the start of loop,

Ora, la linea 2 demarca l'inizio di una istruzione ripetuta, un loop,

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

una sequenza di passaggi che si ripeteranno un tot di volte.

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

Quindi, ad esempio, il passaggio che stiamo affrontando

is counting people in the room.

è contare le persone nella stanza.

Beneath line 2 is line 3,

Al di sotto della linea 2 c'è la linea 3,

which describes exactly how we'll go about counting.

che descrive in maniera precisa come inizieremo il conteggio.

The indentation implies that it's line 3

La rientranza implica che è la linea 3

that will repeat.

ad essere ripetuta.

So, what the pseudocode is saying

Quindi, lo pseudocodice sta dicendo

is that after starting at zero,

che dopo essere partiti con 0,

for each person in the room,

per ciascuna persona nella stanza,

we'll increase n by 1.

accresceremo il valore di n di 1.

Now, is this algorithm correct?

Ora: l'algoritmo è corretto?

Well, let's bang on it a bit.

Be', discutiamone un po'.

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

Funziona se ci sono due persone nella stanza?

Let's see.

Vediamo.

In line 1, we initialize n to zero.

Nella linea 1 impostiamo n sullo zero.

For each of these two people,

Per ciascuna di queste 2 persone,

we then increment n by 1.

incrementiamo n di 1.

So, in the first trip through the loop,

Quindi, al primo giro del loop

we update n from zero to 1,

aggiorniamo n da zero a 1,

on the second trip through that same loop,

nel secondo giro del medesimo loop,

we update n from 1 to 2.

aggiorniamo n da 1 a 2.

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

E in questo modo, con la fine dell'algoritmo, n è 2,

which indeed matches the number of people in the room.

che davvero rispecchia il numero di persone nella stanza.

So far, so good.

Fin qui ci siamo con i conti.

How about a corner case, though?

E se introduciamo un caso limite?

Suppose that there are zero people in the room,

Supponiamo che ci siano zero persone nella stanza,

besides me, who's doing the counting.

oltre a me che sto contando.

In line 1, we again initialize n to zero.

Nella linea 1, di nuovo impostiamo n con il valore 0.

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

Questa volta, tuttavia, la linea 3 non viene eseguita

since there isn't a person in the room,

dato che non c'è una persona nella stanza,

and so, n remains zero,

e quindi, n rimane zero,

which indeed matches the number of people in the room.

che è davvero il numero di persone nella stanza.

Pretty simple, right?

Piuttosto semplice, vero?

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

Ma contare le persone una alla volta è anche piuttosto inefficiente, no?

Surely, we can do better!

Certamente, e possiamo fare di meglio!

Why not count two people at a time?

Perché non contare le persone due alla volta?

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

Invece di contare 1, 2, 3, 4, 5, 6, 7, 8, e così via,

why not count

perché non contare

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

2, 4, 6, 8, e via dicendo?

It even sounds faster, and it surely is.

Suona anche più veloce, e di sicuro lo è.

Let's express this optimization in pseudocode.

Ora esprimiamo questa ottimizzazione in pseudocodice.

Let n equal zero.

Impostiamo n con il valore zero.

For each pair of people in room,

Per ciascuna coppia di persone nella stanza,

set n = n + 2.

impostiamo n = n + 2.

Pretty simple change, right?

Una modifica piuttosto semplice, vero?

Rather than count people one at a time,

Invece di contare le persone una alla volta

we instead count them two at a time.

le contiamo due alla volta.

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

Questo algoritmo è quindi due volte più veloce del precedente.

But is it correct?

Ma può funzionare?

Let's see.

Vediamo.

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

Funziona se ci sono 2 persone nella stanza?

In line 1, we initialize n to zero.

Nella linea 1 impostiamo n su 0.

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

Per quell'unica coppia di persone, incrementiamo n di 2.

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

E quindi, con la fine di questo algoritmo, n è 2,

which indeed matches the number of people in the room.

che è davvero il numero di persone nella stanza.

Suppose next that there are zero people in the room.

Supponiamo ora che ci siano zero persone nella stanza.

In line 1, we initialize n to zero.

Nella linea 1, impostiamo n col valore 0.

As before, line 3 doesn't execute at all

Come prima, la linea tre non viene affatto eseguita,

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

dato che non c'è alcuna coppia di persone nella stanza,

and so, n remains zero,

e quindi n rimane 0,

which indeed matches the number of people in the room.

che rispecchia davvero il numero di persone nella stanza.

But what if there are 3 people in the room?

Ma se ci sono 3 persone nella stanza?

How does this algorithm fair?

Come si comporta questo algoritmo?

Let's see.

Vediamo.

In line 1, we initialize n to zero.

Nella linea 1, impostiamo n con il valore 0.

For a pair of those people,

Per una coppia di quelle persone,

we then increment n by 2,

incrementiamo n di 2,

but then what?

e poi cosa accade?

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

Non c'è un'altra coppia completa nella stanza,

so line 2 no longer applies.

quindi la linea 2 non si applica più.

And so, by this algorithm's end,

E quindi, con questa fine dell'algoritmo,

n is still 2, which isn't correct.

n è ancora 2, che non è il valore corretto.

Indeed this algorithm is said to be buggy

Questo algoritmo si dice che ha un bug

because it has a mistake.

perché contiene un errore.

Let's redress with some new pseudocode.

Ripariamolo con un po' di nuovo pseudocodice.

Let n equal zero.

Impostiamo n con il valore 0.

For each pair of people in room,

Per cuascuna coppia nella stanza,

set n = n + 2.

impostiamo n = n + 2.

If 1 person remains unpaired,

se 1 persona rimane senza coppia,

set n = n + 1.

impostiamo n = n + 1.

To solve this particular problem,

Per risolvere questo particolare problema,

we've introduced in line 4 a condition,

abbiamo introdotto nella linea 4 una condizione,

otherwise known as a branch,

altrimenti conosciuta come diramazione

that only executes if there is one person

che viene eseguita se c'è una persona

we could not pair with another.

che non ptoremmo accoppiare con un'altra.

So now, whether there's 1 or 3

Adesso, quindi, se c'è 1 o 3

or any odd number of people in the room,

o un qualsiasi numero dispari di persone nella stanza,

this algorithm will now count them.

questo algoritmo li conterà.

Can we do even better?

Possiamo fare ancora meglio?

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

Be', potremmo contare 3, 4, 5 o anche 10 alla volta,

but beyond that it's going to get

ma oltre sarebbe

a little bit difficult to point.

un po' difficile da indicare.

At the end of the day,

Alla fine della giornata

whether executed by computers or humans,

che sia eseguito da computer o da esseri umani,

algorithms are just a set of instructions

gli algortismi sono solo una serie di istruzioni

with which to solve problems.

con cui risolvere i problemi.

These were just three.

Questi erano solo tre.

What problem would you solve with an algorithm?

Quale problema risolveresti con un algoritmo?