Qu'est-ce qu'un algorithme? - David J. Malan

Qu'est ce qu'un algorithme ? En informatique, un algorithme est un ensemble d'instructions pour résoudre un problème étape après étape. Généralement, les algorithmes sont exécutés par des ordinateurs mais les humains ont aussi des algorithmes. Par exemple, comment feriez-vous pour compter le nombre de personnes dans une pièce ? Eh bien, si vous êtes comme moi, vous désignez probablement chaque personne, une à la fois, et commencez à compter à partir de 0 : 1, 2, 3, 4 et ainsi de suite. Eh bien ça, c'est un algorithme. En fait, essayons de l'exprimer de manière un peu plus formelle, en pseudocode une syntaxe presque française qui ressemble à un langage de programmation Soit n égal 0. Pour chaque personne dans la pièce, faire n = n + 1 Comment interpréter ce pseudocode ? Eh bien, la ligne 1 déclare, pour ainsi dire, une variable appelée n et initialise sa valeur à zéro. Ça veut dire qu'au début de notre algorithme la chose avec laquelle nous comptons a une valeur de zéro. Après tout, avant d'avoir commencé à compter, on avait encore rien compté . Appeler cette variable n est simplement une convention. J'aurais pu l'appeler presque n'importe comment. Maintenant, la ligne 2 marque le début de la boucle, une séquence d'étapes qui se répète un certain nombre de fois. Donc, dans notre exemple, l'étape que nous prenons c'est le comptage des personnes dans la salle. Après la ligne 2 vient la ligne 3, qui décrit exactement comment on va procéder. L'indentation sous-entend que c'est la ligne 3 qui va se répéter. Donc, ce que dit le pseudocode, c'est qu'après avoir commencé à zéro, pour chaque personne dans la pièce, nous allons augmenter n de 1. Alors, cet algorithme est-il correct ? Eh bien, jetons un coup d’œil là-dessus. Est-ce que ça marche si il y a 2 personnes dans la salle ? Voyons ça. À la ligne 1, nous initialisons n à zéro. Pour chacune de ces deux personnes, nous incrémentons n par 1. Dans le premier parcours à travers la boucle, nous mettons à jour n de zéro à 1, lors du second parcours à travers cette même boucle, nous mettons à jour n de 1 à 2. Et donc, à la fin de cet algorithme, n vaut 2, ce qui correspond au nombre de personnes dans la salle. Pour l'instant ça va. Cependant, si on poussait le raisonnement plus loin ? Supposons qu'il y a zéro personnes dans la salle, à part moi, qui fait le comptage.. À la ligne 1, nous initialisons à nouveau n à zéro. Cependant, cette fois, la ligne 3 ne s'exécute pas du tout puisqu'il n'y a personne dans la pièce, et donc, n reste à zéro, ce qui correspond en effet au nombre de personnes dans la salle. Assez simple, non ? Mais compter les personnes une à une est plutôt inefficace, non ? Bien sûr, nous pouvons faire mieux ! Pourquoi ne pas les compter deux par deux ? Au lieu de compter 1, 2, 3, 4, 5, 6, 7, 8 et ainsi de suite, pourquoi ne pas compter 2, 4, 6, 8 etc ? Ça semble bien plus rapide, et ça l'est assurément. Nous allons exprimer cette optimisation en pseudocode. Soit n égal zéro. Pour chaque paire de personnes dans la salle, la valeur de n prend n + 2. C'est un changement assez simple, pas vrai ? Plutôt que de compter les gens un par un, nous les comptons deux par deux. Cet algorithme est donc deux fois plus vite que le dernier. Mais est-ce correct ? Nous allons voir. Est-ce que ça marche si il y a 2 personnes dans la salle ? À la ligne 1, nous initialisons n à zéro. Pour cette paire de personnes, nous incrémentons n par 2. Et donc, à la fin de cet algorithme, n vaut 2, ce qui, en effet, correspond au nombre de personnes dans la salle. Supposons ensuite qu'il y a zéro personnes dans la salle. À la ligne 1, nous initialisons n à zéro. Comme précédemment, la ligne 3 ne s'exécute pas du tout car il n'y a aucune paire de personnes dans la pièce, et donc, n reste à zéro, ce qui correspond en effet au nombre de personnes dans la salle. Mais que se passe-t-il s'il y a 3 personnes dans la salle ? Comment s’exécute cet algorithme ? Nous allons voir. À la ligne 1, nous initialisons n à zéro. Pour une paire de ces personnes, nous incrémentons n par 2, mais alors quoi ? Il n'y a pas une autre paire complète de personnes dans la salle, par conséquent, la ligne 2 ne s'applique plus. Et donc, à la fin de cet algorithme, n vaut encore 2, ce qui n'est pas correct. En effet, on dit que cet algorithme est buggé parce qu'il comporte une erreur. Nous allons réparer ça en apportant du pseudocode. Soit n égal zéro. Pour chaque paire de personnes dans la salle, la valeur de n = n + 2. Si 1 personne reste non appariée, n prend la valeur n + 1. Pour résoudre ce problème particulier, nous avons introduit à la ligne 4 une condition, qu'on appelle aussi une branche, qui ne s'exécute que s'il y a une personne qu'on a pas pu apparier avec une autre. Donc, maintenant, qu'il y ait 1, 3 ou tout nombre impair de personnes dans la salle, cet algorithme les comptera. Pouvons-nous faire mieux encore ? Eh bien, nous pourrions compter par 3, 4 ou même par 5 et 10, mais au-delà de ça, ça va devenir un peu plus difficile à pointer. À la fin de la journée, qu'ils soient exécuté par des ordinateurs ou par des humains, les algorithmes ne sont qu'un ensemble d'instructions permettant de résoudre les problèmes. Ce n'en était que trois parmi tant d'autres. Quel problème pourriez-vous résoudre avec un algorithme ?