Exercices: Algorithmes et pensée informatique

Écrire l'algorithme, sous forme de liste d'étapes numérotées, pour préparer un sandwich au fromage, de façon qu'une personne qui n'en a jamais fait puisse le suivre sans hésitation. Relire votre liste et vérifier qu'il ne manque pas d'étapes que vous considériez comme évidentes.

Les étapes de l'algorithme « aller au lycée » sont dans le désordre : (a) entrer en classe, (b) se lever, (c) prendre le petit-déjeuner, (d) sortir de la maison, (e) s'habiller, (f) marcher jusqu'au lycée. Les remettre dans le bon ordre et ajouter à l'algorithme une décision : que faire s'il pleut au moment de sortir de la maison.

La figure montre, avec des blocs emboîtés, l'algorithme d'une lampe de lecture automatique qui doit s'allumer seulement quand il y a peu de lumière, mais il manque un bloc.

Indiquer quel bloc vous placeriez dans l'emplacement vide et expliquer avec vos propres mots comment fonctionne l'algorithme complet, étape par étape.

De nombreux appareils du quotidien suivent des algorithmes. Choisir deux appareils de cette liste — lave-linge, four à micro-ondes, feu tricolore — et décrire pour chacun quelles données il reçoit (entrée), ce qu'il décide ou répète (traitement) et ce qu'il fait à la fin (sortie).

Écrire l'algorithme pour préparer un verre de lait au cacao en six à huit étapes, assez précises pour qu'un robot puisse les suivre : quantités, ordre des étapes et manière de vérifier que le cacao est dissous avant de terminer.

Lire cet algorithme : (1) prends le paquet de cartes, (2) tant qu'il reste des cartes dans la main, distribue-en une à chaque joueur en commençant par ta gauche, (3) quand il ne reste plus de cartes, annonce « distribuées ». Expliquer en une phrase ce que fait l'algorithme et indiquer quelle partie est la répétition et quand elle s'arrête.

Dans la recette « faire cuire un œuf au plat », identifier l'entrée (les ingrédients et ustensiles), le traitement (les étapes avec le feu et la poêle) et la sortie (le résultat). Expliquer pourquoi raisonner ainsi aide à écrire des algorithmes clairs.

Une recette dit « remue la sauce jusqu'à ce qu'elle épaississe ». Expliquer pourquoi un algorithme doit toujours se terminer et ce qui pourrait arriver si la sauce n'épaississait jamais. Réécrire cette étape pour que le cuisinier ne reste pas à remuer indéfiniment.

Décomposer le problème « organiser la fête de fin d'année » en quatre sous-problèmes plus petits et écrire deux étapes concrètes pour résoudre chacun. Expliquer quel avantage il y a à diviser ainsi un gros problème.

Pour trier un jeu de cartes, il existe plusieurs algorithmes différents, et certains sont plus rapides que d'autres. Expliquer à l'aide d'un exemple de la vie quotidienne qu'un même problème peut être résolu par plusieurs algorithmes et ce que signifie qu'un algorithme soit « meilleur » qu'un autre.

Une recette dit : « ajoute du sel et laisse cuire un moment à feu moyen ». Expliquer pourquoi un ordinateur ne pourrait pas suivre cette instruction et la réécrire sous forme d'étape d'algorithme précise, en indiquant les quantités, les durées et comment vérifier que l'étape est terminée.

Reconnaître des motifs, c'est trouver la règle qui se répète. Découvrir le motif de ces trois suites et l'exprimer sous forme de règle claire : (a) 5, 10, 15, 20, …, (b) 100, 90, 80, 70, …, (c) lundi : 1 flexion, mardi : 2, mercredi : 4, jeudi : 8, … Indiquer quelle valeur viendrait ensuite dans chacune.

Le plan du métro ne dessine pas la ville réelle : il supprime les distances, les courbes et les rues, et ne garde que les stations et les correspondances. Expliquer ce qu'est l'abstraction à partir de cet exemple, puis l'appliquer au plan de votre collège : quelles trois choses inclureriez-vous et quelles trois choses supprimeriez-vous ?

Vous pouvez le faire sur papier et envoyer une photo de votre réponse.

Faire la trace de cet algorithme avec $n = 7$ : (1) partir de la valeur $n$, (2) répéter trois fois : lui ajouter 2, (3) lui retrancher 5, (4) afficher le résultat. Noter la valeur après chaque étape, donner le résultat final et expliquer ce qu'est une trace d'exécution et à quoi sert de la faire à la main.

Cet algorithme pour « faire la lessive » contient une erreur : (1) mettre tout le linge dans le lave-linge, blanc et couleurs ensemble, (2) ajouter la lessive, (3) choisir le programme long à l'eau chaude, (4) étendre. Trouver deux étapes problématiques, expliquer ce qui peut mal tourner dans chacune et réécrire l'algorithme corrigé avec une étape de tri préalable.

Écrire l'algorithme pour compter combien de personnes entrent par la porte de la classe en utilisant seulement une variable « compteur » qui commence à 0 : que faites-vous chaque fois que quelqu'un entre, comment savez-vous quand arrêter de compter et quelle valeur aura le compteur à la fin.

Concevoir l'algorithme complet, avec des étapes numérotées comprenant des décisions et des répétitions, d'un feu piéton à bouton : que se passe-t-il depuis le moment où quelqu'un appuie sur le bouton jusqu'à ce que le feu retrouve son état initial, en incluant la durée de chaque feu.

Réfléchir à un programme qui joue au morpion. Décrire la stratégie qu'il suivrait à chaque tour : quelles données de la grille il doit examiner, dans quel ordre, et quelles règles vous utiliseriez pour décider où placer le pion. Il n'est pas nécessaire d'écrire du code : les règles en langage naturel suffisent.

L'algorithme d'une cantine distribue un sandwich à chaque convive, mais il échoue lorsqu'il y a plus de convives que de sandwichs. Expliquer ce qu'est un « cas limite » dans un algorithme, proposer comment la distribution devrait se comporter dans cette situation et réécrire l'étape problématique pour que l'algorithme n'échoue pas.

La figure montre, avec des blocs emboîtés, le squelette d'un jeu où il faut deviner un nombre secret, mais il manque une pièce dans la boucle pour que le jeu donne des indices au joueur.

Décrire quel bloc (ou quels blocs) vous placeriez dans l'emplacement vide pour que le jeu indique au joueur si son nombre est plus grand ou plus petit que le nombre secret, et expliquer le fonctionnement complet de l'algorithme : ce qui est répété, quand il se termine et ce qui se passe si le joueur trouve du premier coup.

Vous cherchez le mot « chauve-souris » dans un dictionnaire de 500 pages. Comparer ces deux algorithmes : ouvrir à la première page et avancer page par page, ou ouvrir au milieu et écarter à chaque fois la moitié qui ne convient pas. Expliquer lequel est le plus efficace, pourquoi il ne fonctionne que si les pages sont ordonnées et estimer combien d'« ouvertures » chaque méthode nécessite.

Deux personnes préparent ensemble le petit-déjeuner pour quatre invités : il faut faire du café, griller du pain, presser du jus et mettre la table. Répartir les tâches entre les deux en respectant les dépendances (on ne peut pas servir le café avant de l'avoir fait) et expliquer quelles tâches peuvent être réalisées en même temps et lesquelles non, avec leur ordre.

Un distributeur automatique de billets ne dispose que de billets de $20\ \text{€}$ et son algorithme répartit la somme demandée en billets. Expliquer ce qui se passe quand quelqu'un demande $75\ \text{€}$, pourquoi c'est un cas limite et réécrire les règles du distributeur pour qu'il réponde toujours quelque chose de raisonnable.

Pour le recyclage de la classe, on propose deux algorithmes : (a) chaque jour, la personne responsable trie tous les déchets de la journée dans les trois bacs, et (b) chaque semaine, à tour de rôle, un binôme trie ce qui s'est accumulé. Évaluer les deux selon les critères de temps total, d'erreurs de tri et de répartition de l'effort, puis en choisir un en justifiant.