What's an algorithm? - David J. Malan

Votre cerveau peut résoudre des algorithmes - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

Traducteur: Pierre-Louis Bernard Relecteur: Elisabeth Buffard

What's an algorithm?

Qu'est ce qu'un algorithme ?

In computer science,

En informatique,

an algorithm is a set of instructions

un algorithme est un ensemble d'instructions

for solving some problem, step-by-step.

pour résoudre un problème étape après étape.

Typically, algorithms are executed by computers,

Généralement, les algorithmes sont exécutés par des ordinateurs

but we humans have algorithms as well.

mais les humains ont aussi des algorithmes.

For instance, how would you go about counting

Par exemple, comment feriez-vous

the number of people in a room?

pour compter le nombre de personnes dans une pièce ?

Well, if you're like me,

Eh bien, si vous êtes comme moi,

you probably point at each person,

vous désignez probablement chaque personne,

one at a time,

une à la fois,

and count up from 0:

et commencez à compter à partir de 0 :

1, 2, 3, 4 and so forth.

1, 2, 3, 4 et ainsi de suite.

Well, that's an algorithm.

Eh bien ça, c'est un algorithme.

In fact, let's try to express it

En fait, essayons de l'exprimer

a bit more formally in pseudocode,

de manière un peu plus formelle, en pseudocode

English-like syntax

that resembles a programming language.

une syntaxe presque française

qui ressemble à un langage de programmation

Let n equal 0.

Soit n égal 0.

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

Pour chaque personne dans la pièce, faire n = n + 1

How to interpret this pseudocode?

Comment interpréter ce pseudocode ?

Well, line 1 declares, so to speak,

Eh bien, la ligne 1 déclare, pour ainsi dire,

a variable called n

une variable appelée n

and initializes its value to zero.

et initialise sa valeur à zéro.

This just means that at the beginning of our algorithm,

Ça veut dire qu'au début de notre algorithme

the thing with which we're counting

la chose avec laquelle nous comptons

has a value of zero.

a une valeur de zéro.

After all, before we start counting,

Après tout, avant d'avoir commencé à compter,

we haven't counted anything yet.

on avait encore rien compté .

Calling this variable n is just a convention.

Appeler cette variable n est simplement une convention.

I could have called it almost anything.

J'aurais pu l'appeler presque n'importe comment.

Now, line 2 demarks the start of loop,

Maintenant, la ligne 2 marque le début de la boucle,

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

une séquence d'étapes qui se répète un certain nombre de fois.

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

Donc, dans notre exemple, l'étape que nous prenons

is counting people in the room.

c'est le comptage des personnes dans la salle.

Beneath line 2 is line 3,

Après la ligne 2 vient la ligne 3,

which describes exactly how we'll go about counting.

qui décrit exactement comment on va procéder.

The indentation implies that it's line 3

L'indentation sous-entend que c'est la ligne 3

that will repeat.

qui va se répéter.

So, what the pseudocode is saying

Donc, ce que dit le pseudocode,

is that after starting at zero,

c'est qu'après avoir commencé à zéro,

for each person in the room,

pour chaque personne dans la pièce,

we'll increase n by 1.

nous allons augmenter n de 1.

Now, is this algorithm correct?

Alors, cet algorithme est-il correct ?

Well, let's bang on it a bit.

Eh bien, jetons un coup d’œil là-dessus.

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

Est-ce que ça marche si il y a 2 personnes dans la salle ?

Let's see.

Voyons ça.

In line 1, we initialize n to zero.

À la ligne 1, nous initialisons n à zéro.

For each of these two people,

Pour chacune de ces deux personnes,

we then increment n by 1.

nous incrémentons n par 1.

So, in the first trip through the loop,

Dans le premier parcours à travers la boucle,

we update n from zero to 1,

nous mettons à jour n de zéro à 1,

on the second trip through that same loop,

lors du second parcours à travers cette même boucle,

we update n from 1 to 2.

nous mettons à jour n de 1 à 2.

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

Et donc, à la fin de cet algorithme, n vaut 2,

which indeed matches the number of people in the room.

ce qui correspond au nombre de personnes dans la salle.

So far, so good.

Pour l'instant ça va.

How about a corner case, though?

Cependant, si on poussait le raisonnement plus loin ?

Suppose that there are zero people in the room,

Supposons qu'il y a zéro personnes dans la salle,

besides me, who's doing the counting.

à part moi, qui fait le comptage..

In line 1, we again initialize n to zero.

À la ligne 1, nous initialisons à nouveau n à zéro.

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

Cependant, cette fois, la ligne 3 ne s'exécute pas du tout

since there isn't a person in the room,

puisqu'il n'y a personne dans la pièce,

and so, n remains zero,

et donc, n reste à zéro,

which indeed matches the number of people in the room.

ce qui correspond en effet au nombre de personnes dans la salle.

Pretty simple, right?

Assez simple, non ?

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

Mais compter les personnes une à une est plutôt inefficace, non ?

Surely, we can do better!

Bien sûr, nous pouvons faire mieux !

Why not count two people at a time?

Pourquoi ne pas les compter deux par deux ?

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

Au lieu de compter 1, 2, 3, 4, 5, 6, 7, 8 et ainsi de suite,

why not count

pourquoi ne pas compter

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

2, 4, 6, 8 etc ?

It even sounds faster, and it surely is.

Ça semble bien plus rapide, et ça l'est assurément.

Let's express this optimization in pseudocode.

Nous allons exprimer cette optimisation en pseudocode.

Let n equal zero.

Soit n égal zéro.

For each pair of people in room,

Pour chaque paire de personnes dans la salle,

set n = n + 2.

la valeur de n prend n + 2.

Pretty simple change, right?

C'est un changement assez simple, pas vrai ?

Rather than count people one at a time,

Plutôt que de compter les gens un par un,

we instead count them two at a time.

nous les comptons deux par deux.

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

Cet algorithme est donc deux fois plus vite que le dernier.

But is it correct?

Mais est-ce correct ?

Let's see.

Nous allons voir.

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

Est-ce que ça marche si il y a 2 personnes dans la salle ?

In line 1, we initialize n to zero.

À la ligne 1, nous initialisons n à zéro.

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

Pour cette paire de personnes, nous incrémentons n par 2.

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

Et donc, à la fin de cet algorithme, n vaut 2,

which indeed matches the number of people in the room.

ce qui, en effet, correspond au nombre de personnes dans la salle.

Suppose next that there are zero people in the room.

Supposons ensuite qu'il y a zéro personnes dans la salle.

In line 1, we initialize n to zero.

À la ligne 1, nous initialisons n à zéro.

As before, line 3 doesn't execute at all

Comme précédemment, la ligne 3 ne s'exécute pas du tout

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

car il n'y a aucune paire de personnes dans la pièce,

and so, n remains zero,

et donc, n reste à zéro,

which indeed matches the number of people in the room.

ce qui correspond en effet au nombre de personnes dans la salle.

But what if there are 3 people in the room?

Mais que se passe-t-il s'il y a 3 personnes dans la salle ?

How does this algorithm fair?

Comment s’exécute cet algorithme ?

Let's see.

Nous allons voir.

In line 1, we initialize n to zero.

À la ligne 1, nous initialisons n à zéro.

For a pair of those people,

Pour une paire de ces personnes,

we then increment n by 2,

nous incrémentons n par 2,

but then what?

mais alors quoi ?

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

Il n'y a pas une autre paire complète de personnes dans la salle,

so line 2 no longer applies.

par conséquent, la ligne 2 ne s'applique plus.

And so, by this algorithm's end,

Et donc, à la fin de cet algorithme,

n is still 2, which isn't correct.

n vaut encore 2, ce qui n'est pas correct.

Indeed this algorithm is said to be buggy

En effet, on dit que cet algorithme est buggé

because it has a mistake.

parce qu'il comporte une erreur.

Let's redress with some new pseudocode.

Nous allons réparer ça en apportant du pseudocode.

Let n equal zero.

Soit n égal zéro.

For each pair of people in room,

Pour chaque paire de personnes dans la salle,

set n = n + 2.

la valeur de n = n + 2.

If 1 person remains unpaired,

Si 1 personne reste non appariée,

set n = n + 1.

n prend la valeur n + 1.

To solve this particular problem,

Pour résoudre ce problème particulier,

we've introduced in line 4 a condition,

nous avons introduit à la ligne 4 une condition,

otherwise known as a branch,

qu'on appelle aussi une branche,

that only executes if there is one person

qui ne s'exécute que s'il y a une personne

we could not pair with another.

qu'on a pas pu apparier avec une autre.

So now, whether there's 1 or 3

Donc, maintenant, qu'il y ait 1, 3

or any odd number of people in the room,

ou tout nombre impair de personnes dans la salle,

this algorithm will now count them.

cet algorithme les comptera.

Can we do even better?

Pouvons-nous faire mieux encore ?

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

Eh bien, nous pourrions compter par 3, 4 ou même par 5 et 10,

but beyond that it's going to get

mais au-delà de ça, ça va devenir

a little bit difficult to point.

un peu plus difficile à pointer.

At the end of the day,

À la fin de la journée,

whether executed by computers or humans,

qu'ils soient exécuté par des ordinateurs ou par des humains,

algorithms are just a set of instructions

les algorithmes ne sont qu'un ensemble d'instructions

with which to solve problems.

permettant de résoudre les problèmes.

These were just three.

Ce n'en était que trois parmi tant d'autres.

What problem would you solve with an algorithm?

Quel problème pourriez-vous résoudre avec un algorithme ?