Aperçu de la leçon
Les participant(e)s vont comprendre ce qu’est un algorithme, pourquoi les algorithmes sont importants et comment ils sont utilisés dans la vie quotidienne et en informatique.
Les participant(e)s vont comprendre ce qu’est un algorithme, pourquoi les algorithmes sont importants et comment ils sont utilisés dans la vie quotidienne et en informatique.
Prêt(e)s ?
Commencer la leçon
Vous êtes-vous déjà demandé comment votre restaurant préféré fait votre plat favori à la perfection à chaque fois ? Ou comment Siri ou Alexa peuvent répondre à une question que vous posez ? Comment fonctionnent les voitures autonomes ? Croyez-le ou non, tous ces éléments ont une chose en commun : les algorithmes.
Un algorithme est un ensemble clairement défini d’instructions étape par étape pour résoudre un problème ou accomplir une tâche.
Projetez cette définition, le premier point du document « Qu’est-ce qu’un algorithme ? », sur un écran. Distribuez le document « Qu’est-ce qu’un algorithme ? » .
Les algorithmes se présentent sous la forme de mots, de programmes informatiques ou de codes, voire de recettes. Certains algorithmes consistent en de simples tâches, instructions ou processus que vous utilisez dans votre vie quotidienne.
Par exemple, pour vous réveiller le matin, vous pouvez sortir du lit, aller dans la salle de bains et ouvrir le robinet d’eau froide, le laisser couler pendant 30 secondes, vous asperger le visage d’eau trois fois et vous sécher avec une serviette.
Notez ici que ce sont là des étapes pour accomplir une tâche et qu’elles sont très claires et détaillées. Par exemple, on mentionne le temps pendant lequel le robinet est ouvert et le nombre de fois où l’on s’asperge le visage d’eau.
Un autre exemple d’algorithme est la recette de vos biscuits préférés dont les instructions sont clairement données, étape par étape.
Mais toutes les routines/recettes ne sont pas des algorithmes. Nous verrons cela bientôt !
Vous avez travaillé avec des algorithmes dans chaque cours de mathématiques que vous avez suivi. À l’école, vous avez appris les algorithmes d’addition, de soustraction, de multiplication et de division. En géométrie, vous calculez les surfaces des formes géométriques à l’aide d’algorithmes. Par exemple, lorsque vous calculez la surface d’un rectangle, vous utilisez un algorithme simple qui multiplie la longueur du rectangle par sa largeur.
Le concept d’algorithme existe depuis très longtemps. En fait, les premiers algorithmes mathématiques connus au monde ont été créés par les Babyloniens sur des tablettes d’argile il y a près de 4 000 ans.
Le mot « algorithme » lui-même provient du nom d’un mathématicien perse du neuvième siècle, Muhammad ibn Mūsā al-Khwārizmī (une prononciation peut être trouvée entre 0:18 et 0:20 dans la vidéo qui suit), connu pour son travail d’explication des procédures étape par étape pour résoudre les problèmes mathématiques.
N’hésitez pas à projeter sur un écran de projection l’image d’une statue de Muhammad ibn Mūsā al-Khwārizmī (en latin, « Algoritmi ») dans sa ville natale de Khiva, en Ouzbékistan.
De nos jours, on trouve des algorithmes partout. Ils sont présents sur nos appareils mobiles, nos ordinateurs portables, nos automobiles, nos appareils ménagers et même nos jouets ! Ces algorithmes sont des algorithmes informatiques.
En informatique, un algorithme est une séquence d’instructions précises qui indiquent à un ordinateur comment résoudre un problème ou accomplir une tâche.
Nous remarquons donc que la définition d’un algorithme et celle d’un algorithme informatique sont fondamentalement les mêmes. La principale différence est que les algorithmes informatiques fonctionnent sur des ordinateurs.
Examinons de plus près les algorithmes en explorant leurs caractéristiques et leurs propriétés. Nous allons pour cela nous intéresser à un algorithme représenté par une recette, étant entendu que les caractéristiques et les propriétés que nous allons examiner s’appliquent également aux algorithmes informatiques.
C’est une recette très amusante à faire pour vous et vos ami(e)s !
Distribuez le document « Recette » aux participants. Regroupez les participant(e)s en binômes. Demandez aux participant(e)s de discuter en binômes : Cette recette est-elle un algorithme ? Pourquoi ? Donnez-leur 10 minutes pour faire cet exercice. Rappelez aux participant(e)s que les étapes doivent être clairement énoncées afin que tout le monde puisse réaliser la recette.
La recette n’est pas un algorithme pour deux raisons essentielles. Tout d’abord, certaines étapes sont ambiguës (par exemple, dans la recette, la durée de cuisson des pois chiches n’est pas indiquée). En outre, pour certains des ingrédients, les quantités spécifiques nécessaires ne sont pas indiquées. Le processus expliqué dans les étapes n’est pas non plus très efficace : la deuxième étape invite à s’éloigner de la recette et à regarder une émission de télévision pendant une demi-heure. Comme nous allons bientôt l’apprendre, si l’efficacité d’un algorithme n’est pas une exigence absolue, elle est idéale et, dans certains cas, peut être d’une importance capitale.
Voyons un peu à quoi ressemble cette recette en tant qu’algorithme !
Il est important de noter qu’un algorithme présente plusieurs caractéristiques essentielles.
Notez les caractéristiques suivantes en gras sur un paper-board ou un tableau d’affichage.
Tout d’abord, l’objectif de l’algorithme doit être bien défini. Par exemple, si l’objectif de notre exemple de recette avait été « Préparer beaucoup de houmous », nous ne saurions pas comment atteindre cet objectif.
Deuxièmement, les instructions étape par étape doivent être clairement données. Si la recette figurant sur votre document était un algorithme, n’importe qui devrait pouvoir respecter les quantités exactes d’ingrédients nécessaires et suivre les étapes de la préparation correcte du houmous, comme le temps nécessaire pour mixer les pois chiches.
Toutefois, lorsqu’on suit une recette, on peut faire preuve d’une certaine souplesse. Ainsi, le temps nécessaire pour mixer le houmous peut varier selon l’avis de la personne qui le prépare (en fonction de la consistance du mélange par exemple). Il serait donc plus approprié que la recette indique une fourchette de temps pour mixer le mélange. Cependant, contrairement aux humains, un algorithme informatique doit suivre un ensemble précis d’instructions pour accomplir une tâche.
Et troisièmement, l’algorithme doit être correct.
Non, nous pouvons facilement ajuster la quantité d’ingrédients afin de pouvoir saisir n’importe quel nombre de portions, d’une portion individuelle à 8, 9, 20, ou autant que nécessaire !
Si l’efficacité d’un algorithme n’est pas absolument nécessaire, elle peut dans certaines situations être d’une importance capitale. De manière générale, l’efficacité qualifie les situations dans lesquelles des ressources telles que les matériaux, la main-d’œuvre ou le temps sont bien utilisées, sans être gaspillées. Dans le cas des algorithmes informatiques, l’efficacité fait généralement référence au temps nécessaire à la réalisation de l’algorithme ou à l’espace (c’est-à-dire la mémoire) que l’algorithme occupe sur un ordinateur. Mais, dans la recette de houmous de votre document, nous constatons une utilisation inefficace des ressources (c'est-à-dire de l'argent et du stockage) lorsque nous voyons que les ingrédients nécessitent une quantité excessive de pois chiches.
Pour le chef de cuisine d’un restaurant populaire et très fréquenté, l’efficacité de la recette revêt une importance particulière ! Et dans l'exemple de recette figurant sur votre document, faire une pause pour aller regarder votre émission de télévision préférée ajoute non seulement du temps à la préparation, mais cela pourrait aussi s’avérer désastreux.
Vous remarquerez également qu’en haut de la recette, j’ai indiqué un résultat ou un objectif : la recette doit permettre d’obtenir 3 à 4 portions de houmous.
Pour retranscrire ces caractéristiques aux algorithmes informatiques, voyons à nouveau comment nous décrivons les algorithmes exécutés sur des ordinateurs. [Lisez le deuxième point du document « Qu’est-ce qu’un algorithme ? ».]
Projetez cette définition, le deuxième point du document « Qu’est-ce qu’un algorithme ? », sur un écran.
Une autre façon de considérer les algorithmes informatiques est [Lisez le troisième point du document « Qu’est-ce qu’un algorithme ? ».]
Projetez cette définition, le troisième point du document « Qu’est-ce qu’un algorithme ? » sur un écran.
Comme nous venons de l’apprendre, l’efficacité est une caractéristique souhaitable d’un algorithme. Cela inclut, entre autres, le temps nécessaire à l’ordinateur pour exécuter l’algorithme.
Mais l’essentiel pour les algorithmes informatiques est que le problème ou la tâche soit bien défini(e) et que les instructions étape par étape soient données avec précision et puissent être exécutées par un ordinateur. Les algorithmes informatiques ne sauraient fonctionner avec des instructions et des objectifs vagues.
La nature des algorithmes informatiques (comme le montre la troisième définition du document « Qu’est-ce qu’un algorithme ? ») est qu’une entrée ou un ensemble d’entrées, en rapport avec l’objectif de l’algorithme, produit, au moyen d’une séquence d’instructions informatiques exécutables, une ou plusieurs sorties qui tentent de résoudre le problème correctement.
Voici quelques exemples d’algorithmes informatiques que vous pourriez rencontrer.
Lorsque vous êtes dans une voiture, toute une série d’algorithmes informatiques sont à l’œuvre. Par exemple, les capteurs détectent les données entrantes telles que les kilomètres parcourus et l’essence consommée, et calculent le kilométrage (c’est-à-dire le résultat). Lorsque vous introduisez une adresse dans Google Maps (l’entrée), Google Maps produit une sortie indiquant l’itinéraire le plus court. Lorsque vous posez une question à Siri, Alexa, Zuri ou Google Assistant (l’entrée), ces systèmes (avec un peu de chance !) fournissent une réponse utile (la sortie). Et lorsque vous recherchez quelque chose en ligne sur un moteur de recherche, comme Google, le texte que vous saisissez produit une liste des sites web les plus pertinents.
Aujourd’hui, on trouve des algorithmes informatiques partout. Ils sont présents sur les appareils mobiles, les ordinateurs portables, les voitures et les appareils ménagers qu’on utilise au quotidien. Les algorithmes, qu’ils vous aident à préparer vos biscuits préférés ou qu’ils répondent à vos recherches en ligne, sont partout autour de nous.
Dans le désordre, les algorithmes à la rescousse !
Assemblez les gobelets blancs numérotés dans l’ordre suivant sur la table devant vous, du premier au dernier : 64, 23, 5, 98, 125, 110, 28 et 37.
Référez-vous à l’image N°1 de tri à bulles du document.
Explorons un type spécifique d’algorithme, appelé algorithme de tri. Le « tri » consiste généralement à classer une liste d’éléments dans un ordre numérique ou alphabétique. Il existe de nombreux exemples de cas où il est vraiment important d’avoir les choses dans un ordre spécifique, comme dans la liste de contacts d’un téléphone portable.
Les algorithmes de tri constituent une famille fondamentale d’algorithmes en informatique, avec un large éventail d’applications. Lorsque l’Organisation mondiale de la santé, par exemple, recueille la fréquence (c’est-à-dire le taux) d’une certaine maladie dans des centaines de régions du monde, des algorithmes de tri informatique organisent systématiquement les données par ordre croissant ou décroissant pour les tableaux, les représentations graphiques et l’analyse des données.
Prenons d’autres exemples d’algorithmes de tri. Chaque fois que vous effectuez une recherche en ligne à l’aide d’un moteur de recherche comme Google, votre recherche est traitée par de nombreux algorithmes sophistiqués, avec des algorithmes de tri intégrés au processus. Et lorsque vous allez en ligne pour trouver le meilleur restaurant de waakye près de chez vous, des algorithmes informatiques, sur des sites web tels que TripAdvisor, trient ces restaurants de waakye en fonction de leur proximité et des évaluations fournies par les utilisateurs du site web.
Examinons deux algorithmes de tri informatique. L’un d’eux est connu sous le nom de « tri à bulles ». L’autre est un tri fusion, basé sur la stratégie qui consiste à diviser pour mieux régner.
Projetez sur un écran la définition suivante du tri à bulles.
Un tri à bulles est un algorithme de tri simple qui parcourt de manière répétée une liste d’éléments, compare les éléments adjacents et les échange s’ils ne sont pas dans le bon ordre. Ce processus est répété jusqu’à ce que tous les éléments soient triés.
Je vais maintenant faire une démonstration de tri à bulles avec ces huit gobelets numérotés devant moi. Mon objectif est de trier ces gobelets par ordre croissant. Commencez par la paire de gobelets numérotés 64 et 23.
Comparons les deux premiers gobelets : 64 et 23.
Ils ne sont pas dans l’ordre : 23 est inférieur à 64. Il faut donc intervertir ces deux gobelets pour que 23 vienne avant 64.
Référez-vous à l’image N°2 de tri à bulles du document.
Maintenant, regardons la prochaine paire de gobelets adjacents, numérotés 64 et 5. Comme 5 est inférieur à 64, les gobelets ne sont pas dans l’ordre, je vais donc les intervertir.
Référez-vous à l’image N°3 de tri à bulles du document.
Ensuite, comparons la paire adjacente de 64 et 98. Comme la paire est dans l’ordre, je n’intervertirai pas ces deux-là.
Ensuite, je vais comparer la paire adjacente de 98 et 125. Comme précédemment, puisque la paire est dans l’ordre, je n’intervertirai pas ces gobelets.
Continuons comme cela avec la prochaine paire adjacente, les gobelets numérotés 125 et 110, que je vais donc intervertir.
Référez-vous à l’image N°4 de tri à bulles du document.
Ensuite, je vais intervertir les gobelets numérotés 125 et 28.
Référez-vous à l’image N°5 de tri à bulles du document.
Et enfin, je vais échanger la paire de gobelets 125 et 37.
Référez-vous à l’image N°6 de tri à bulles du document.
Nous pouvons voir que les gobelets ne sont toujours pas en ordre croissant. Mais notons quelques éléments.
D’abord, j’ai fait sept comparaisons de paires de chiffres.
Deuxièmement, le gobelet le plus grand de cette liste, le 125, a été déplacé à la fin de la rangée, là où il devrait être. Ce numéro est passé à la fin de la liste.
Je vais répéter ce processus en revenant aux deux premiers gobelets de la rangée, numérotées 23 et 5.
Cette fois, comparons les gobelets ensemble, en décidant à chaque fois si on les intervertit ou non.
Au fur et à mesure que vous avancez le long de la rangée, demandez aux participant(e)s s’ils (elles) pensent que vous devez ou non intervertir les gobelets en leur demandant : « On intervertit ou pas ? » En recommençant une deuxième fois, on obtient la disposition suivante des gobelets : 5, 23, 64, 98, 28, 37, 110 et 125. Faites remarquer aux participant(e)s que, cette fois, nous n’avons eu à faire que six comparaisons, car nous savions, grâce à la première série de comparaisons, que 125 était le plus grand nombre. Nous n’avons donc pas eu besoin de comparer le 110 et le 125.
Les gobelets ne sont toujours pas dans l’ordre, mais le deuxième plus grand nombre (110) se trouve maintenant juste avant le premier, 125, comme il se doit.
Comme les gobelets ne sont toujours pas dans l’ordre, nous devons parcourir à nouveau la rangée. Une fois encore, nous commençons par le début, avec les gobelets numérotées 5 et 23. Au fur et à mesure que vous avancez le long de la rangée, demandez aux participant(e)s s’ils (elles) pensent que vous devez ou non intervertir les gobelets en leur demandant : « On intervertit ou pas ? » En passant une troisième fois, on obtient la disposition suivante des gobelets : 5, 23, 64, 28, 37, 98, 110 et 125.
Seules cinq comparaisons ont été effectuées car, dès le deuxième tour, nous savions que les deux plus grands nombres de la série (110 et 125) étaient correctement placés à la fin. Nous n’avons donc pas eu besoin de comparer 98 et 110 ou 110 et 125.
Nous faisons des progrès, mais les gobelets ne sont toujours pas en ordre croissant. Je sais que ça semble prendre une éternité ! Mais les ordinateurs sont beaucoup plus rapides que les gens, et nous verrons très bientôt un moyen plus rapide d’ordonner ces chiffres !
Maintenant, parcourons à nouveau la rangée en utilisant le même processus. Comme précédemment, nous allons revenir au début de la rangée, avec les gobelets numérotés 5 et 23.
Au fur et à mesure que vous avancez le long de la rangée, demandez aux participant(e)s s’ils (elles) pensent que vous devez ou non intervertir les gobelets en leur demandant : « On intervertit ou pas ? » En procédant une quatrième fois, on obtient la disposition suivante des gobelets : 5, 23, 28, 37, 64, 98, 110 et 125. Faites remarquer aux participant(e)s que, cette fois, nous n’avons effectué que quatre comparaisons. Dès le troisième tour, nous savions que les trois plus grands nombres de la série (98, 110 et 125) étaient correctement placés à la fin. Nous n’avons donc pas eu besoin de comparer les paires 64 et 98, 98 et 110, et 110 et 125.
Maintenant les gobelets sont en ordre croissant !
Référez-vous à l’image N°7 de tri à bulles du document.
Ce tri a nécessité 22 comparaisons [calculé en totalisant 7 comparaisons (premier tour) + 6 comparaisons (deuxième tour) + 5 comparaisons (troisième tour) + 4 comparaisons (quatrième tour)].
Supposons que chaque comparaison prenne une seconde. Alors, le temps nécessaire pour effectuer ce tri serait de 22 secondes.
Maintenant, supposons que quelqu’un nous remette une liste de 1 000 chiffres à trier par ordre croissant. Dans ce cas, le tri à bulles peut nécessiter près d’un demi-million de comparaisons. Cela nous prendrait 5,8 jours à compléter, sans faire de pause !
Cependant, l’exécution de cet algorithme sur un ordinateur, avec une liste non ordonnée de huit chiffres (comme dans notre exemple) permettrait d’ordonner la liste presque instantanément !
Mais avec une liste non ordonnée de 1 000 chiffres, l’algorithme prendrait quelques minutes, ce qui est en fait très long pour un ordinateur.
Le tri à bulles est simple mais pas efficace. De nombreux autres algorithmes informatiques effectuent un tri plus rapide et plus efficace. L’un d’entre eux est le tri fusion.
La stratégie qui sous-tend le tri fusion est celle du « diviser pour mieux régner », une approche utilisée dans de nombreux algorithmes informatiques, mais aussi pour résoudre des problèmes en général.
Diviser pour régner consiste à faciliter la résolution d’un problème en le divisant en versions plus simples que l’on va résoudre, puis à combiner ces versions pour résoudre le problème de départ.
Imaginons un tri fusion avec nos huit gobelets numérotés.
Réorganisez les gobelets de manière à ce qu’ils soient présentés dans le même ordre qu’au début de cette activité : 64, 23, 5, 98, 125, 110, 28 et 37.
Référez-vous à l’image N°1 de tri à bulles du document.
La première partie du tri fusion consiste à « diviser ».
Projetez sur un écran le diagramme « Tri fusion - Première étape : Diviser ».
Reportez-vous à la première étape : Diagramme « Diviser ».
En regardant ce diagramme, nous allons prendre les gobelets devant nous et si nous faisons les subdivisions illustrées dans le diagramme, nous nous retrouverons avec les huit gobelets séparés [indiqués dans la ligne « Huit listes »].
Posez les huit gobelets séparément.
Maintenant, au lieu d’une liste de huit éléments (c’est-à-dire des chiffres), nous nous retrouvons avec huit listes d’un élément. Chacune de ces listes d’un élément est triée vu qu’elle ne contient qu’un seul chiffre. Nous avons divisé le problème en parties aussi petites que possible.
La deuxième partie du tri fusion consiste à « régner ».
Projetez sur un écran le diagramme « Tri fusion - Deuxième étape : Régner ».
Reportez-vous à la deuxième étape : Diagramme « Régner ».
Nous voyons sur le diagramme que nous prenons d’abord les huit listes triées pour les fusionner en quatre paires ordonnées.
Faisons la démonstration avec les deux premiers gobelets.
Nous fusionnons la liste à numéro unique 64 avec la liste à numéro unique 23 en retirant d’abord le gobelet numéroté le plus petit, 23.
Placez le gobelet 23 devant le gobelet 64.
Ensuite, il ne reste que la liste à numéro unique 64. On va prendre ce gobelet et le placer à côté du 23.
Ensuite, placez le gobelet 64 à côté du gobelet 23.
Nous allons répéter ce processus pour les gobelets restants.
En poursuivant de la sorte, nous nous retrouverons avec quatre listes étant toutes ordonnées.
Placez les gobelets dans la disposition prévue dans la rangée « Quatre listes » du Tri fusion - Deuxième étape : Diagramme « Régner ».
Maintenant, nous allons fusionner les deux premières paires ordonnées pour créer une seule liste de quatre gobelets ordonnés.
Laissez-moi vous montrer comment procéder.
Tout d’abord, nous examinons les premiers gobelets de chaque paire (23 et 5). On prend le gobelet numéroté le plus petit. Dans ce cas, il s’agira du gobelet 5.
Placez ce gobelet devant les autres.
Ensuite, dans les deux listes restantes [la liste avec 23 et 64 et la liste avec 98, en notant que le 5 a été supprimé à l’étape précédente], regardons à nouveau le premier gobelet dans chacune de ces deux listes.
On prendra le gobelet avec le plus petit numéro. Dans ce cas, c’est le 23.
Sortez le gobelet numéro 23 et placez-le à côté du 5.
Maintenant, nous nous retrouvons avec deux listes ayant un numéro chacune.
Nous allons prendre le plus petit nombre de ces deux listes, qui est 64, et le placer à côté de 23. [Prenez le gobelet numéro 64 et placez-le à côté du 23.]
Enfin, nous placerons le dernier gobelet, le numéro 98, à côté du 64.
Sortez le gobelet numéro 98 et placez-le à côté du 64.
Maintenant, nous avons une liste de quatre gobelets numérotés qui sont ordonnés.
Nous allons ensuite répéter le même processus avec ces deux paires de gobelets. (Montrez les paires de gobelets numéros 110 et 125, et 28 et 37.)
N’allez pas jusqu’au bout de la démarche. Indiquez plutôt quel serait le résultat final en montrant la façon dont les gobelets numéros 110 et 125, et 28 et 37 seraient fusionnés, comme indiqué dans la ligne « Deux listes » du Tri fusion - Deuxième étape : Diagramme « Régner ».
Enfin, comme le montre le schéma, nous avons deux listes ordonnées. Maintenant, nous allons fusionner ces deux listes. L’approche sera la même que celle utilisée précédemment (où nous avons fusionné quatre listes en deux listes).
Montrez la ligne « Quatre listes » et la ligne « Deux listes » du tri fusion - Deuxième étape : Diagramme « Régner ».
Notre liste de gobelets numérotés est maintenant ordonnée !
Montrez la ligne « Un, liste triée » de la deuxième étape du tri fusion : Diagramme « Régner ».
Le problème est résolu !
Ce tri fusion a nécessité 15 comparaisons, contre 22 comparaisons dans notre exemple de tri à bulles.
Le tri fusion l’emporte !
Lorsque l’on exécute le tri à bulles et le tri fusion sur un ordinateur pour une liste contenant des milliers de chiffres, le tri fusion prend quelques fractions de seconde, alors que le temps d’exécution du tri à bulles se compte en minutes. Le tri fusion est nettement plus efficace que le tri à bulles.
Dans cette activité, nous avons vu deux façons, parmi tant d’autres, dont les ordinateurs trient les données.
Il n’est pas rare que plusieurs algorithmes accomplissent la même tâche. Toutefois, certains algorithmes sont plus rapides et plus efficaces que d’autres, comme nous l’avons vu dans le cas du tri fusion (diviser pour mieux régner), par opposition au tri à bulles (simple mais long).
Les algorithmes de tri constituent une importante famille d’algorithmes informatiques ayant de nombreuses applications utiles.
Parmi les autres familles d’algorithmes, citons les algorithmes de recherche, les algorithmes de calcul d’itinéraire utilisés par les systèmes GPS et les algorithmes de cryptographie qui sécurisent les messages sur Internet.
Ces dernières années, vous avez peut-être entendu parler des algorithmes d’apprentissage automatique de l’IA et vous les avez très probablement rencontrés. Ces algorithmes sont différents des algorithmes traditionnels et programmables des ordinateurs. Ce qui est important dans les algorithmes d’apprentissage automatique de l’IA, c’est que ces derniers apprennent (s’entraînent) par eux-mêmes à partir de données, et de beaucoup de données, dans le but d’optimiser leurs réponses. L’apprentissage automatique de l’IA intervient lorsque Facebook
identifie vos photos, que Google Assistant répond à vos questions et que des voitures autonomes apparaissent sur les routes, pour ne citer que quelques exemples.
Examinons un problème qui repousse les limites de la pensée algorithmique depuis plus de 2 000 ans : la recherche de nombres premiers.
Pour rappel, un nombre premier est simplement un nombre entier supérieur à 1 dont les seuls diviseurs sont 1 et lui-même. Par exemple, 2, 3, 5, 7 et 11 sont des nombres premiers.
Le nombre 6, par exemple, n’est pas un nombre premier, puisque 6 est divisible par 1, 2, 3 et 6. Le nombre 15 n’est pas non plus un nombre premier : il est divisible par 1, 3, 5 et 15.
Les nombres premiers sont, en fait, les éléments constitutifs de notre système numérique et, aujourd’hui, ils jouent un rôle important dans la cryptographie et la sécurité sur Internet.
La sécurisation des transactions sur Internet, comme l’achat d’articles avec une carte de crédit, repose sur le cryptage (c’est-à-dire la science du codage des messages) avec de très grands nombres premiers comportant des centaines, voire des milliers de chiffres.
Bien qu’il existe un nombre infini de nombres premiers, il est assez difficile de trouver de très grands nombres premiers.
Examinons un problème plus simple : trouver tous les nombres premiers jusqu’à 100, avec un exercice amusant à faire en binôme.
Distribuez le document « Algorithmes en prime time » et des stylos ou crayons.
Représentons les nombres entiers jusqu’à 100 par ordre croissant en utilisant le tableau de 10 par 10 présenté sur votre document.
Barrez le 1, puis tous les nombres pairs : les multiples de 2 (c’est-à-dire les nombres divisibles par 2), à l’exception du 2. Ensuite, entourez 2, qui est un nombre premier.
Maintenant, en travaillant par deux, je voudrais que vous preniez les 15 prochaines minutes pour identifier tous les nombres premiers restants jusqu’à 100. Pendant cet exercice, écrivez sur votre document les étapes que vous suivez pour identifier ces nombres premiers. Veillez à commencer votre algorithme en écrivant les étapes dont nous venons de discuter ensemble (par exemple : représenter d’abord les entiers de 1 à 100 dans un tableau de 10 par 10 par ordre croissant).
Cet algorithme doit permettre à un(e) de vos ami(e)s de trouver, sans votre aide, tous les nombres premiers jusqu’à 100 en suivant les mêmes étapes.
Pour commencer, écrivez d’abord votre objectif sur le document.
Après avoir noté les étapes de votre algorithme, indiquez également ci-dessous les données d’entrée et de sortie de votre algorithme.
J’aimerais que vous gardiez à l’esprit certaines choses pendant que vous faites cet exercice.
Regroupez les participant(e)s en binômes. Prévoyez 15 minutes pour cet exercice.
Reprenons ensemble. Voici une façon de formuler les étapes de cet algorithme.
Projetez sur un écran l’algorithme de « Algorithmes en prime time : Exemplaire de l’enseignant(e) » (commençant par le « But » et se terminant par « Cet algorithme est connu sous le nom de crible d’Eratosthène »). Maintenez cette projection jusqu’à ce que vous atteigniez la prochaine projection d’un code Python du crible d’Eratosthène.
L’algorithme que vous venez d’écrire est très célèbre. Il est connu sous le nom de « crible d’Eratosthène », mis au point par le mathématicien grec Eratosthène en 240 avant Jésus-Christ.
Nous pouvons modifier cette quatrième étape [indiquer la quatrième étape du document « Algorithmes en prime time : exemplaire de l’enseignant(e) »] pour indiquer que nous pouvons nous arrêter au nombre 11, le premier nombre premier dont le carré (c’est-à-dire le produit de 11 x 11) est supérieur à 100.
Puis, sur le document « Algorithmes en prime time : exemplaire de l’enseignant(e) », montrez l’entrée de 100.
Nous pouvons en fait entrer n’importe quel nombre entier positif et modifier l’algorithme en conséquence pour trouver tous les nombres premiers jusqu’à ce nombre entier.
Supposons qu’au lieu d’entrer 100, notre entrée soit 1 000. Nous pourrions utiliser le crible d’Eratosthène pour trouver tous les nombres premiers jusqu’à 1 000 en utilisant du papier et un crayon. Cela nous prendrait beaucoup de temps. Mais, un ordinateur pourrait exécuter les étapes de cet algorithme presque instantanément !
Le crible d’Eratosthène écrit en langage de programmation Python (ou dans n’importe quel langage de programmation) est capable de calculer tous les nombres premiers jusqu’à 1 000 en une fraction de seconde.
Mais si vous essayez de trouver de très grands nombres premiers, comportant des centaines ou des milliers de chiffres, qui jouent un rôle important dans la cryptographie et la sécurité sur
Internet, l’algorithme informatique du crible d’Ératosthène devient très inefficace.
Au cours de plusieurs décennies, des mathématicien(ne)s, des informaticien(ne)s et des ingénieur(e)s ont mis au point un large éventail de méthodes/d’algorithmes pour identifier ces très grands nombres premiers. Certains sont des variantes du crible d’Eratosthène et d’autres s’inspirent de la théorie des probabilités. Même la chimie moléculaire s’en mêle !
Maintenant que nous avons parlé de ce qu’est (et de ce que n’est pas !) un algorithme et que nous en avons illustré plusieurs, j’aimerais que vous appliquiez ce que vous avez appris pour créer votre propre algorithme.
Cet algorithme peut être lié à n’importe quel sujet : un ensemble d’étapes permettant de résoudre un problème de mathématiques ou peut-être même d’accomplir une action dans votre application mobile ou votre jeu vidéo préféré.
Avant de rédiger les étapes, assurez-vous, en premier lieu, de préciser votre objectif. Ensuite, écrivez les étapes de l’algorithme donné. Votre algorithme doit comporter entre cinq et dix étapes. Assurez-vous d’écrire également les données d’entrée et de sortie de votre algorithme !
Lorsque vous développez votre algorithme, gardez à l’esprit les caractéristiques clés que nous avons évoquées précédemment : les instructions doivent être clairement définies, l’algorithme doit permettre d’atteindre votre objectif et (bien que cela ne soit pas obligatoire) il doit être efficace.
Donnez aux participant(e)s 25 minutes pour réaliser l’activité. En fonction du temps imparti, au cours de la présente ou de la deuxième réunion de groupe, engagez la discussion suivante.
Regroupez les participant(e)s en binômes.
En binômes, je veux que vous partagiez votre algorithme et que vous discutiez des points suivants :
Donnez aux participant(e)s 15 minutes pour faire cet exercice avec leur partenaire. Ensuite, accordez 10 minutes aux binômes pour qu’ils partagent a) les moyens qu’ils ont trouvés pour rendre leur algorithme plus efficace, sur la base de leur discussion avec leur partenaire, et/ou b) une chose nouvelle ou surprenante qu’ils ont apprise en développant leur propre algorithme ou en examinant celui de leur partenaire.
Félicitations !
Vous avez terminé la leçon.
Les étudiant(e)s vont apprendre à sécuriser leurs informations en ligne en utilisant et en conservant des mots de passe forts.
Voir la pageLes étudiant(e)s vont être capables de décrire les risques liés au fait d’être en ligne.
Voir la pageLes étudiant(e)s vont apprendre ce que signifie vérifier l’information, et pourquoi il est important que les internautes vérifient les articles qu’ils lisent ou regardent.
Voir la pageLes étudiant(e)s vont découvrir une liste de vérification en cinq étapes qu’ils (elles) pourront utiliser pour vérifier la origine, la source, la date, l’emplacement et la raison d'être d’une image ou d’une vidéo d’actualité.
Voir la pageLes étudiant(e)s vont être en mesure de définir ce qu’est un « scrape » (copie d’un original) et d’expliquer pourquoi la prolifération de ce type de texte médiatique peut rendre le processus de vérification plus difficile pour les actualités de dernière minute.
Voir la pageLes étudiant(e)s vont apprendre à sécuriser leurs informations en ligne en utilisant et en conservant des mots de passe forts.
Voir la pageLes étudiant(e)s vont être capables de décrire les risques liés au fait d’être en ligne.
Voir la pageLes étudiant(e)s vont apprendre ce que signifie vérifier l’information, et pourquoi il est important que les internautes vérifient les articles qu’ils lisent ou regardent.
Voir la pageLes étudiant(e)s vont découvrir une liste de vérification en cinq étapes qu’ils (elles) pourront utiliser pour vérifier la origine, la source, la date, l’emplacement et la raison d'être d’une image ou d’une vidéo d’actualité.
Voir la pageLes étudiant(e)s vont être en mesure de définir ce qu’est un « scrape » (copie d’un original) et d’expliquer pourquoi la prolifération de ce type de texte médiatique peut rendre le processus de vérification plus difficile pour les actualités de dernière minute.
Voir la page