Module sur les opportunités numériques

Leçon 4 : Qu’est-ce qu’un algorithme ?

Prêt(e)s ?
Commencer la leçon.

Bases de l’algorithme

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

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 ? » .

DITES À VOS ÉTUDIANT(E)S

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 !

DEMANDEZ À VOS ÉTUDIANT(E)S

• Vous pouvez probablement penser à de nombreux types de routines que vous faites chaque jour et qui permettent d’accomplir différentes tâches. Quelqu’un peut-il partager un exemple d’étapes d’une de vos routines ?
  • Il peut s’agir, par exemple, des indications nécessaires pour se rendre de chez vous à chez un(e) ami(e), de la série d’exercices d’échauffement à suivre avant de courir ou des différentes étapes à suivre pour laver votre linge. À mesure que les participant(e)s partagent leurs routines, demandez-leur s’ils (elles) estiment que les étapes à suivre sont claires/précises.

DITES À VOS ÉTUDIANT(E)S

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.

DEMANDEZ À VOS ÉTUDIANT(E)S

• Pouvez-vous penser à d’autres exemples de mathématiques où vous avez utilisé un algorithme pour résoudre un problème ? Les exemples possibles incluent l’addition et la multiplication de fractions (par exemple : 3/4 + 1/8 = 6/8 + 1/8 = 7/8) et/ou la résolution d’équations (par exemple : 3x + 2 = 5).

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DITES À VOS ÉTUDIANT(E)S

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 !

ACTIVITÉ INTERACTIVE EN CLASSE

Distribuez le document « Recette : Participant(e) ». 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.

DEMANDEZ À VOS ÉTUDIANT(E)S

• Reprenons ensemble. Quel est votre constat ? Pensez-vous que la recette est un algorithme ? Pourquoi ?

DITES À VOS ÉTUDIANT(E)S

La recette n’est pas un algorithme pour deux raisons essentielles. Tout d’abord, certaines étapes sont ambiguës (par exemple, dans la recette, le durée de cuisson de l’ugali n’est pas indiquée). En outre, pour certains des ingrédients, les quantités spécifiques nécessaires ne sont pas indiquées. La procédure expliquée dans ces étapes n’est pas très efficace. 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.

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

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 d’ugali », 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 de l’ugali, comme le temps de cuisson du mélange.

Toutefois, lorsqu’on suit une recette, on peut faire preuve d’une certaine souplesse. Ainsi, le temps nécessaire à la cuisson du mélange d’ugali 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 la cuisson du 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.

DEMANDEZ À VOS ÉTUDIANT(E)S

• Nous pouvons considérer le nombre de portions d'ugali et les ingrédients mesurés correspondants comme les entrées de notre exemple de recette. En suivant les étapes de la recette (comme indiqué sur le document « Recette : copie pour l’enseignant(e)), on obtient 4 à 5 portions d'ugali, c’est notre résultat. Mais que faire si l'on veut faire 10 portions d'ugali ? Devons-nous écrire un algorithme entièrement nouveau ?

DITES À VOS ÉTUDIANT(E)S

Non, nous pouvons facilement ajuster la quantité d’ingrédients afin de pouvoir saisir n’importe quel nombre de portions, d’une portion individuelle à huit, neuf, 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 l’ugali présentée sur votre document, nous constatons que les ressources (c’est-à-dire l’argent et le stockage) sont utilisées de manière inefficace lorsque nous voyons que les ingrédients exigent un type ou une quantité spécifique de farine de maïs.

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, le fait de prendre une pause de 30 minutes pour aller regarder votre émission de télévision préférée a non seulement pour effet d’allonger le temps de préparation, mais s’avère aussi désastreux, car le mélange de haricots reste sur le feu pendant une demi-heure.

Vous remarquerez également qu’en haut de la recette, j’ai indiqué un résultat ou un objectif : la recette permet d’obtenir 4 à 5 portions d’ugali.

DITES À VOS ÉTUDIANT(E)S

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 ? ».]

ACTIVITÉ INTERACTIVE EN CLASSE

Projetez cette définition, le deuxième point du document « Qu’est-ce qu’un algorithme ? », sur un écran.

DITES À VOS ÉTUDIANT(E)S

Une autre façon de considérer les algorithmes informatiques est [Lisez le troisième point du document « Qu’est-ce qu’un algorithme ? ».]

ACTIVITÉ INTERACTIVE EN CLASSE

Projetez cette définition, le troisième point du document « Qu’est-ce qu’un algorithme ? » sur un écran.

DITES À VOS ÉTUDIANT(E)S

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.

DITES À VOS ÉTUDIANT(E)S

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 !

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DITES À VOS ÉTUDIANT(E)S

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.

DEMANDEZ À VOS ÉTUDIANT(E)S

• Quelqu’un peut-il donner d’autres exemples ? Autres exemples possibles : l’index d’un livre, les entrées d’un dictionnaire ou les livres d’une bibliothèque.

DITES À VOS ÉTUDIANT(E)S

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.

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DEMANDEZ À VOS ÉTUDIANT(E)S

• Voyez-vous ce que nous avons réalisé dans cette deuxième série de comparaisons ?

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DITES À VOS ÉTUDIANT(E)S

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.

DEMANDEZ À VOS ÉTUDIANT(E)S

• Vous voyez pourquoi nous n’avons eu besoin de faire que cinq comparaisons au troisième tour ?

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DITES À VOS ÉTUDIANT(E)S

Maintenant les gobelets sont en ordre croissant !

Référez-vous à l’image N°7 de tri à bulles du document.

DEMANDEZ À VOS ÉTUDIANT(E)S

• Que pensez-vous du tri à bulle en termes de quantité de travail nécessaire ? La réponse possible est que, bien que le tri à bulles soit simple, il peut prendre beaucoup de temps avec toutes les comparaisons à effectuer.

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DITES À VOS ÉTUDIANT(E)S

La première partie du tri fusion consiste à « diviser ».

ACTIVITÉ INTERACTIVE EN CLASSE

Projetez sur un écran le diagramme « Tri fusion - Première étape : Diviser ».

Reportez-vous à la première étape : Diagramme « Diviser ».

DITES À VOS ÉTUDIANT(E)S

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 »].

ACTIVITÉ INTERACTIVE EN CLASSE

Posez les huit gobelets séparément.

DITES À VOS ÉTUDIANT(E)S

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 ».

ACTIVITÉ INTERACTIVE EN CLASSE

Projetez sur un écran le diagramme « Tri fusion - Deuxième étape : Régner ».

Reportez-vous à la deuxième étape : Diagramme « Régner ».

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

Placez les gobelets dans la disposition prévue dans la rangée « Quatre listes » du Tri fusion - Deuxième étape : Diagramme « Régner ».

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DITES À VOS ÉTUDIANT(E)S

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.)

ACTIVITÉ INTERACTIVE EN CLASSE

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 ».

DITES À VOS ÉTUDIANT(E)S

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).

ACTIVITÉ INTERACTIVE EN CLASSE

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 !

DITES À VOS ÉTUDIANT(E)S

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.

Algorithmes en prime time

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

Distribuez le document « Algorithmes en prime time » et des stylos ou crayons.

DITES À VOS ÉTUDIANT(E)S

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.

DEMANDEZ À VOS ÉTUDIANT(E)S

• À votre avis, quelle devrait être la prochaine étape ?
  • Barrez tous les multiples de 3 (c’est-à-dire les nombres divisibles par 3), à l’exception du 3. Entourez le 3, un autre nombre premier. Notez que certains chiffres peuvent déjà avoir été barrés, comme le 6 (qui est un multiple de 2 et de 3).

DITES À VOS ÉTUDIANT(E)S

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.

• Votre algorithme vous permet-il d’identifier tous les nombres premiers jusqu’à 100 ? En d’autres termes, atteint-il son objectif ?
• Y a-t-il des moyens de rendre votre algorithme plus efficace ?

ACTIVITÉ INTERACTIVE EN CLASSE

Regroupez les participant(e)s en binômes. Prévoyez 15 minutes pour cet exercice.

DITES À VOS ÉTUDIANT(E)S

Reprenons ensemble. Voici une façon de formuler les étapes de cet algorithme.

ACTIVITÉ INTERACTIVE EN CLASSE

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.

DITES À VOS ÉTUDIANT(E)S

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.

DEMANDEZ À VOS ÉTUDIANT(E)S

• Comment pouvez-vous être sûr que l’algorithme que vous avez développé en groupe identifie tous les nombres premiers jusqu’à 100 ?
  • Une réponse possible serait que les participant(e)s ont identifié tous les nombres qui ne sont que des multiples de 1 et d’eux-mêmes (c’est-à-dire que ces nombres ne sont divisibles que par 1 et eux-mêmes) avant de les entourer.

• Dans vos binômes, avez-vous trouvé des moyens de rendre cet algorithme plus efficace ?
  • Une réponse possible serait qu’une fois que les participant(e)s ont atteint le nombre premier 11, ils ont remarqué que tous ses multiples ont été rayés. Par exemple, 44 a été barré en tant que multiple de 2. Et 33 a été barré en tant que multiple de 3. De plus, une fois que nous avons atteint 11 x 11, nous remarquons que le produit (121) est supérieur à 100. Nous pouvons alors entourer tous les nombres restants (c’est-à-dire les nombres qui n’ont pas encore été rayés), qui sont tous des nombres premiers.

DITES À VOS ÉTUDIANT(E)S

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.

DEMANDEZ À VOS ÉTUDIANT(E)S

• L’entrée de 100 est-elle correcte ?
  • Oui. Comme l’indique l’objectif de l’algorithme, nous cherchons à trouver tous les nombres premiers jusqu’à 100.

DITES À VOS ÉTUDIANT(E)S

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 !

Devoirs

DITES À VOS ÉTUDIANT(E)S

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.

ACTIVITÉ INTERACTIVE EN CLASSE

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.

Discussion

ACTIVITÉ INTERACTIVE EN CLASSE

Regroupez les participant(e)s en binômes.

DITES À VOS ÉTUDIANT(E)S

En binômes, je veux que vous partagiez votre algorithme et que vous discutiez des points suivants :

• Pensez-vous pouvoir reproduire les étapes de l’algorithme de votre partenaire ? Si non, quelles modifications pouvez-vous suggérer ?
• Pensez-vous qu’il existe des moyens de rendre l’algorithme de votre partenaire plus efficace ? Si oui, comment ?
• Avez-vous appris quelque chose de nouveau ou de surprenant en créant votre propre algorithme ou en lisant celui de votre partenaire ?
• Vous aurez 15 minutes pour réaliser cet exercice.

ACTIVITÉ INTERACTIVE EN CLASSE

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.

Leçon précédente Leçon suivante