Avant-propos : quand faire ces activités ?

Cette étape est différente des autres au sens où elle ne contient pas de tâches nécessaires à la programmation du jeu vidéo, mais consiste en une série d’activités (débranchées, pour la plupart) qui permettent de revenir sur certains concepts algorithmiques utilisés notamment dans l’activité de programmation.

Ces activités sont complètement indépendantes les unes des autres et optionnelles : on peut parfaitement poursuivre le projet sans les réaliser.

Afin de ne pas casser la dynamique du projet en cours (programmation du jeu vidéo dans Scratch), nous conseillons de mener les activités débranchées proposées ici sur un autre temps que celui dédié à la programmation qui doit suivre son cours. L’idéal est de le faire sur le temps accordé aux mathématiques ou au français.
L’activité 1, branchée, peut quant-à-elle facilement s’intégrer à une séance de programmation (il suffit de prendre 10 minutes avant de se replonger dans le projet en cours).

Activité 1 : évaluation formative sur le concept de boucle  (branchée, 10 à 20 minutes)

Cette activité est fortement conseillée après l’étape 4, au cours de laquelle les élèves ont manipulé plusieurs fois des boucles dans Scratch. Ce concept de boucle peut être consolidé grâce à une série de petits exercices d’évaluation formative. Ceux-ci permettront également d’explorer plus avant les boucles disponibles en Scratch (car toutes celles que nous utilisons dans notre programme sont du type « répéter indéfiniment », mais il y en a d’autres !).

Tout comme cela est proposé au cycle 2 avec Scratch Junior (cf. Séance II-2.3), on peut proposer aux élèves de simplifier l’écriture d’un programme en utilisant des boucles. Le programme ci-dessous, à gauche, fait dessiner un carré par le lutin. Le programme de droite arrive au même résultat en utilisant une boucle. Suivant le niveau des élèves, on peut soit leur demander de réaliser le programme de droite par eux-mêmes, soit leur donner tous les éléments, dans le désordre et non reliés entre eux et leur demander de tout remettre en ordre pour que ce programme donne le même résultat que celui de gauche.

Le lutin dessine un carré de 100 pixels de coté

Ce programme fait exactement la même chose, avec une boucle

   
Nous conseillons à l’enseignant de répéter ce type d’exercice autant de fois que nécessaire pour que l’utilisation des boucles soit bien comprise et devienne naturelle.

 Activité 2 : un jeu de cartes pour s’approprier la notion de variable  (débranchée, 1 heure)

Cette activité a pour objectif d’aborder la notion de variable, et propose pour cela d’initier les élèves à un jeu de cartes. Il est intéressant de donner aux élèves l’occasion de jouer plusieurs fois à ce jeu, car ils deviennent alors capables d’élaborer des stratégies complexes. Le travail peut être réalisé sur des temps de calcul mental (manipulation des scores), de français (travail sur la signification des cartes), ou en accompagnement personnalisé par petits groupes de 8 ou 16 élèves. Si le travail est effectué en classe entière, ne pas faire l’économie d’une discussion collective sur la signification des cartes, avant la mise en œuvre du jeu. Si le travail est effectué en demi-groupe, préciser la signification des cartes qui posent problème lorsque la difficulté se présente.

Les variables manipulées dans le jeu sont les scores des joueurs, et certaines  cartes affectent ces scores. Dans un premier temps de découverte du jeu, seules des cartes proposant des manipulations simples des scores sont intégrées au jeu. Puis des cartes plus complexes sont introduites, incluant des manipulations des scores en fonction de certaines conditions.

Situation déclenchante – Présentation du jeu

Les soirées sont longues à la base installée sur la planète lointaine. Les explorateurs, une fois accomplies leurs missions de travail, se détendent en faisant du sport en salle et en jouant à des jeux de société. Leur jeu préféré est un jeu de cartes auxquels les élèves vont jouer. Le jeu se joue à 4 équipes (idéalement des binômes) nommées A, B, C, D. On organise donc des tablées de 8 élèves. Le but de chaque équipe est d’accumuler le plus de points possible, de la façon suivante :

• Les équipes A, B, C et D démarrent le jeu avec un score initial de 1 point, inscrit sur une ardoise.
• Chaque équipe reçoit 4 cartes distribuées au hasard, et les cartes restantes sont placées en pile (la pioche), face cachée.
• Les élèves prennent connaissance de leurs cartes, sans les montrer aux élèves des équipes concurrentes.
• À tour de rôle, les équipes se mettent d’accord pour choisir une de leurs 4 cartes. Ils la lisent à voix haute, la posent sur la table face visible, et obéissent aux instructions qu’elle donne. Certaines de ces instructions affectent le score d’une ou plusieurs équipes. Dans ce cas, les scores sont mis à jour sur les ardoises.
• Lorsque toutes les cartes ont été jouées, l’équipe qui a le plus de points est déclarée  gagnante.

L’enseignant donne un exemple au tableau : il dessine la position des équipes A, B, C et D autour d’une table en vue du dessus, avec les scores à la valeur 1. Puis il lit à voix haute (ou fait lire par un élève) une carte jouée par l’équipe A … et demande à la classe comment les scores vont changer sous l’effet de cette carte. Les changements des scores sont effectués. L’enseignant lit ensuite (ou fait lire) une carte jouée par l’équipe B … et ainsi de suite. Il continue aussi longtemps que nécessaire pour que toute la classe estime avoir compris le jeu.

Alternative : on peut préférer organiser le jeu sur un mode coopératif. Dans ce cas, les 4 équipes d’une table coopèrent, sans s’informer mutuellement sur la nature des cartes qu’elles ont en main, pour que la somme de leurs scores finaux soit la plus élevée possible.

Jeu avec les cartes 1 à 24

Les élèves jouent au jeu avec seulement les cartes 1 à 24 de la Fiche 34. Parmi ces cartes, celles qui affectent les scores donnent explicitement le nom des scores à changer (A, B, C et/ou D) et les changements de score ne dépendent pas de conditions.
Lors de la mise en commun, le professeur demande aux élèves si leur score a toujours eu la même valeur au cours du jeu, ou si cette valeur a changé. Il introduit l’adjectif « variable », pas encore dans son sens informatique. La classe discute du rôle de l’ardoise (elle permet de noter les valeurs actuelles des scores, et de les modifier facilement).
Il peut ensuite, à condition que les élèves aient déjà une première pratique de Scratch :

• leur demander de proposer un nom pour les scores des 4 équipes d’une table, par exemple score A, score B, score C et score D.
• leur montrer comment initialiser ces 4 variables à la valeur 1.
• introduire le terme variable dans son sens informatique : une variable est un espace de mémoire dans lequel on peut stocker une valeur,  pour la réutiliser ou la modifier plus tard.
• commencer un travail de traduction en Scratch des cartes les plus simples (cartes 1 à 8 pour commencer, et davantage si la classe se prend au jeu, voire paragraphe « Traduction en langage Scratch », plus bas). Les cartes traduites sont dorénavant remplacées dans le jeu par leur version en langage Scratch.

Jeu avec les cartes 1 à 36

Les élèves rejouent au jeu en ajoutant les cartes 25 à 36 de la Fiche 35. Parmi les nouvelles cartes, certaines désignent des scores à changer, relativement à la position du joueur (score du joueur, score de son voisin de droite ou de son voisin d’en face par exemple). D’autres introduisent des conditions (si votre score … alors …).
Le travail de traduction en Scratch des cartes se poursuit progressivement, toujours en remplaçant les cartes au fur et à mesure de leur traduction.

Jeu avec les cartes 1 à 48

Les élèves rejouent au jeu en ajoutant les cartes 37 à 48 de la Fiche 35. Parmi ces nouvelles cartes, deux abordent les tirages aléatoires. Les 8 dernières cartes sont à compléter par les élèves.
La traduction des cartes se poursuit, sans chercher l’exhaustivité.

Traduction des cartes en langage Scratch

Selon l’avancement du travail avec Scratch , certaines cartes sont traduites du français au langage Scratch, progressivement (cartes 1 à 8 pour commencer).
Par exemple :

• la carte n°1 s’écrit
  
• la carte n°5 s’écrit
  
• la carte n°9 peut s’écrire de 2 façons différentes :
      ou    

La traduction est répartie entre les différents groupes d’élèves et discutée. Attention, certaines traductions sont délicates (surtout pour les cartes à partir du numéro 25), d’autres sont impossibles (soit que les cartes n’affectent pas les scores, soit que la stratégie des joueurs dépende du contexte : valeur de leur score, et des scores des autres équipes, cartes restant dans leur main).
Certaines cartes, comme par exemple la n° 32, nécessitent de créer une variable supplémentaire pour stocker une valeur de façon temporaire.

Conclusion et mise en commun

Les élèves effectuent collectivement la synthèse de ce que le jeu de cartes leur a enseigné :

• Au cours de nombreux jeux, les scores des joueurs changent de valeur (on dit qu’ils sont variables). Ils sont mémorisés à chaque étape du jeu. De même, la position des joueurs sur un plateau de jeu, le nombre de pions qu’ils possèdent, etc. sont mémorisés et varient.
• Dans un langage de programmation, une variable permet de mémoriser une valeur qui peut varier au cours de l’exécution du programme.

Prolongement

Les élèves recherchent différents contextes dans lesquels les ordinateurs utilisés dans la vie courante utilisent des variables, pour stocker des données :

• l’heure affichée sur une montre digitale.
• la vitesse de déplacement d’une voiture affichée sur un écran numérique.
• le solde d’un compte bancaire.

Ils recherchent à quelles occasions ces variables changent de valeur ou sont utilisées.
Par exemple, l’heure de la montre change toutes les secondes, et à une certaine heure, une alarme se déclenche.
Le solde d’un compte bancaire change à chaque fois qu’on effectue une dépense ou un encaissement.

Activité 3 : un jeu de cartes pour travailler les opérateurs logiques  (débranchée, 1 heure)

Au cours de l’étape précédente, les élèves ont utilisé des tests (si le rover récolte une ressource, alors le score augmente). L’enseignant explique à la classe que le groupe de mots « Le rover récolte une ressource » est une « expression » qui peut être soit vraie, soit fausse. Une telle expression s’appelle une  « condition ».
L’activité proposée ici se déroule en 2 temps :

• Dans un premier temps, les élèves se familiarisent avec les expressions logiques en analysant une scène (Fiche 36).
• Dans un second temps, à l’aide de vignettes présentant des conditions et des connecteurs logiques, ils expriment la condition qui doit être remplie pour que l’alarme de la station spatiale se déclenche (Fiche 37).

Exercice de logique (individuel)

Chaque élève reçoit la Fiche 36 et doit indiquer, dans chaque situation, si l’expression est vraie ou fausse, ou encore si rien ne lui permet de le savoir.

Les réponses sont :

• Expression 1 : VRAIE (c’est assez évident !)
• Expression 2 : FAUSSE (là aussi !)
• Expression 3 : VRAIE (une porte est toujours, soit dans la position ouverte, soit dans la position fermée).
• Expression 4 : FAUSSE (une porte ne peut pas être ouverte et fermée en même temps)
• Expression 5 : on ne peut pas savoir (rien ne nous renseigne sur l’état de la porte, à moins que nous ne puissions la voir en ce moment)
• Expression 6a : VRAIE (les 2 conditions sont réalisées en même temps)
• Expression 6b : VRAIE (il suffit que l’une des conditions soit vérifiée, ce qui est le cas)
• Expression 7a : FAUSSE (la seconde condition n’est pas réalisée)
• Expression 7b : VRAIE (il suffit que l’une des conditions soit vérifiée, ce qui est le cas)

Les réponses des élèves sont comparées pour les différentes expressions de la fiche documentaire. L’enseignant veille à ce que la classe atteigne un consensus pour chacune d’entre elles. Il est probable que les expressions comportant un « OU » soient plus difficiles à évaluer pour les élèves.

• Pour que l’expression « A ou B » soit vraie, il suffit que l’une des deux sous-expressions A et B soit vraie. Il est possible, mais pas nécessaire, que A et B soient vraies à la fois.
• Pour que l’expression « A et B » soit vraie, il faut qu’à la fois A et B soient vraies.

Au besoin, la classe invente de nouvelles expressions simples pour manipuler ces conditions logiques et teste si ces expressions sont vraies ou fausses sur l’une et l’autre des illustrations de la Fiche 36 (ou sur des situations quotidiennes de l’école). Si cela est plus simple pour les élèves, présenter les expressions à l’intérieur d’un test plutôt que de façon isolée. Par exemple : « la cloche de l’école sonne si c’est l’heure de la récréation ou c’est l’heure de la reprise ou c’est l’heure de la fin des cours. »

Manipuler les expressions logiques : programmer l’alarme de la base

Une fois cette petite gymnastique acquise par les élèves, l’enseignant distribue la Fiche 37 aux élèves, répartis en petits groupes (maximum 4 élèves par groupe). Cette fiche permet de réinvestir les notions précédentes dans le contexte de notre scénario, à savoir l’exploration de la planète.
La consigne à donner à chaque groupe est la suivante : découpez les vignettes puis combinez-les  de façon à former des expressions logiques. On souhaite décrire la condition qui permet de déclencher l’alarme de notre station spatiale.

Par exemple : l’alarme se déclenche :

• SI « le sas de sécurité est ouvert » ;
• OU si « la nuit tombe » ET « le rover n’est pas présent dans la base » ;
• OU si « le niveau d’oxygène est critique » ET « la base est occupée » ;
• OU si « l’énergie est basse » ET « la base est occupée » ;
• OU si « le groupe électrogène NE fonctionne PAS ».
• Etc.

Dans un premier temps, l’enseignant veille à ce que toutes les vignettes soient bien comprises, qu’il s’agisse des conditions (cartes présentant des dessins) ou des connecteurs logiques (SI, ALORS, ET, OU, NON). Le « NON » est nouveau, et nécessite une explication. Le fait que le rover ne soit pas présent dans la base s’écrit : « NON (le rover est présent dans la base) ». Il peut être nécessaire de réfléchir collectivement à quelques cas simples, d’abord à l’oral, puis à l’aide des vignettes. Dès que le principe est compris des élèves, on peut les laisser en autonomie pour trouver d’autres conditions et les écrire.

La première condition s’écrit :

La seconde s’écrit

Notes pédagogiques

• Les parenthèses permettent de rendre les expressions plus facilement lisibles, et font partie intégrante de la syntaxe. Déplacer des parenthèses peut changer le sens d’une expression ! Les élèves peuvent placer leurs cartes sur une feuille blanche et dessiner les parenthèses sur la feuille.
• En fonction de l’aisance des élèves, on pourra leur demander soit d’écrire chaque condition séparément, soit d’écrire une seule expression qui rassemble toutes les conditions faisant que l’alarme se déclenche (toutes ces conditions sont connectées par des « OU ». Dans ce cas, il peut être nécessaire d’imprimer plusieurs copies de la Fiche 37 pour que chaque groupe puisse disposer de davantage de vignettes (en particulier, les connecteurs logiques).

Pour chacune des conditions nécessaires au déclenchement de l’alarme, l’enseignant veille à ce que les différentes propositions des élèves soient présentées et discutées.
Collectivement, la classe construit une expression unique qui les regroupe toutes. Pour plus de visibilité, ne pas hésiter à multiplier les parenthèses et à écrire l’expression sur plusieurs lignes :

La classe synthétise collectivement ce qui a été appris au cours de cette séance :

• Dans un algorithme, on peut utiliser des tests qui disent quelle instruction effectuer quand une condition est vérifiée ou non.
• Une condition est une expression qui peut être soit vraie, soit fausse (mais pas les deux).
• on peut utiliser des connecteurs logiques comme ET, OU,  NON pour fabriquer des expressions logiques.

Les élèves notent ces conclusions dans leur cahier de sciences. L’enseignant, quant à lui, met à jour l’affiche « qu’est-ce que l’informatique » démarrée en début de projet en recopiant ce que la classe a appris sur la notion de logique au cours de cette séance.

Activité 4 : comprendre qu’un algorithme n’est pas toujours parfait : le jeu du voyageur de commerce  (débranchée, 1 heure)

Notes pédagogiques :

• Cette activité, optionnelle, cible davantage les élèves plus âgés (6ème et au-delà). Elle consiste à approfondir la notion d’algorithme à travers un problème simple : trouver le plus court chemin permettant de passer par différents endroits. Elle a pour but de montrer que, parfois, un problème ne peut pas être résolu, même s’il existe un algorithme qui, a priori, est censé fonctionner. Il faut alors se contenter d’une solution approchée, imparfaite mais suffisante.
• Ici, il existe un algorithme simple pour résoudre le problème (essayer tous les chemins, et choisir le plus court)… mais cet algorithme ne peut pas être mis en œuvre dans la pratique, car le nombre de chemins à tester devient très rapidement gigantesque.

Situation déclenchante

Au cours des séances précédentes, les élèves ont complété leur programme pour y ajouter un défi : le rover doit explorer la carte pour récupérer toutes le plus de ressources possibles.
L’enseignant explique que le carburant est limité et précieux et qu’il faut l’économiser au maximum. Ainsi, on se place dans un problème « classique » d’optimisation : « On connait à l’avance le nombre et l’emplacement des ressources. On doit trouver un chemin qui passe par toutes ces ressources et revienne au point de départ… et qui soit le plus court possible. »

L’enseignant demande aux élèves s’il existe une méthode (un algorithme) qui permet de donner la solution à ce problème. La discussion collective montre que cette question peut être décomposée en 2 questions plus précises :

• Le problème a-t-il une solution ? Parmi les chemins qui passent par toutes les ressources, est-ce qu’il y a un chemin plus court que les autres (éventuellement, ex-aequo) ? La réponse à cette question est « oui » : il existe plusieurs chemins possibles, il y a donc forcément un (ou plusieurs) chemin(s) plus court(s) que les autres.
• Existe-t-il une méthode qui nous permette de trouver, à coup sûr, un chemin le plus court possible ? La classe peut proposer une méthode pour trouver ce chemin : il suffit de tester tous les chemins possibles et de mesurer leur longueur, pour sélectionner le plus court.

En fonction du matériel disponible, l’enseignant peut proposer soit 1 seule activité (basée sur la fiche documentaire), soit 2 activités (d’abord, la fiche documentaire, puis l’expérience à l’aide des planches cloutées)

Recherche du plus court chemin (par groupes)

L’enseignant distribue la Fiche 38 à chaque élève (ceux-ci sont répartis par groupes, mais en raison du nombre de chemins à tester et dessiner, il est préférable de donner une fiche à chacun). Il s’agit de trouver tous les chemins possibles pour aller chercher 2 ressources, ou 3, ou 4, et de mesurer la longueur de ces chemins à l’aide d’une règle.
NB : on suppose qu’on ne passe par la base que deux fois : au départ et à l’arrivée.

Mise en commun

La discussion collective permet de faire ressortir le fait que le nombre de chemins possibles augmente très vite avec le nombre de ressources à aller chercher. Pour 2 ressources : si on note B la base, 1 et 2 les ressources, on a 2 trajets possibles : B12B ou B21B … ce qui correspond en fait au même chemin effectué dans un sens ou dans l’autre. Pour 3 ressources, il y a 6 trajets possibles, soit 3 chemins réellement différents : B123B et B321B (même chemin dans les deux sens) B132B et B231B (même chemin dans les deux sens) B213B et B123B (même chemin dans les deux sens) Pour 4 ressources, il y a 24 trajets possibles soit 12 chemins réellement différents : B1234B et B4321B (même chemin dans les deux sens) B1243B et B3421B B1324B et B4231B B1342B et B2431B B1423B et B3241B B1432B et B2341B B2134B et B4312B B2143B et B3412B B2314B et B4132B B2413B et B3142B B3124B et B4213B B3214B et B4123B Quand on élimine les doublons, il ne reste plus « que » 12 possibilités, ce qui est bien trop grand pour permettre aux élèves de toutes les trouver et de toutes les dessiner sur un même schéma.

(Facultatif) Recherche du plus court chemin (par groupes)

S’il dispose d’une planche cloutée pour chaque groupe, l’enseignant distribue cette planche et demande aux élèves de trouver le chemin le plus court permettant à la ficelle de passer par tous les clous (et de revenir au point de départ). Pour chaque  trajet testé, on met une marque sur la ficelle afin d’indiquer la longueur atteinte (qui doit être la plus courte possible). Cette activité est similaire à la précédente, mais le fait d’avoir un support physique (les clous, la ficelle) permet aux élèves d’éliminer facilement certains « mauvais » chemins et d’avoir une intuition de ce que peut être un « bon » chemin.

Mise en commun

Cette nouvelle mise en commun permet de faire ressortir plusieurs choses :

• Il existe un très grand nombre de chemins possibles (personne n’a pu tous les tester)
• Au début de l’activité, les progrès sont rapides (on trouve des chemins de plus en plus courts), puis les progrès sont minimes (on a beau multiplier les essais, on ne gagne plus que quelques millimètres)
• Certains élèves peuvent penser avoir trouvé LE meilleur chemin. Il n’est pas possible de confirmer cette affirmation, mais on remarque que les « bons » chemins sont ceux qui évitent les croisements et limitent les retours en arrière.

Notes scientifiques :

• Le nombre de chemins différents, pour n ressources + 1 base (ou n+1 clous, comme dans la seconde expérience), est n ! (ce qui se lit « factorielle n »). Ce nombre se construit en multipliant n par tous les entiers situés en dessous de lui, jusqu’à 1. Par exemple :
  o    1 ! = 1
  o    2 ! = 2x1 = 2
  o    3 ! = 3x2x1 = 6
  o    4 ! = 4x3x2x1 = 24
• Si l’on élimine tous les chemins identiques mais pris dans un sens ou dans l’autre, cela donne, pour n ressources, un nombre n!/2 de chemins possibles.
• Cette fonction (qui, pour un nombre n de ressources associe n!/2 chemins) augmente très rapidement :
  o    5 ressources :      60 chemins
  o    6 ressources :    360 chemins
  o    7 ressources : 2 520 chemins
  o    10 ressources : près de 2 millions de chemins
  o    20 ressources : un milliard de milliards de chemins possibles
  o    Pour 100 ressources : le nombre de chemins possibles s’écrit avec 158 chiffres !
• Ce problème est devenu un « classique » en algorithmique, connu sous le nom du « problème du voyageur de commerce ». Un représentant doit démarcher plusieurs clients répartis sur le territoire. Quel chemin doit-il emprunter pour tous les démarcher une fois, en un minimum de temps ?

L’enseignant explique à la classe que le nombre de chemins augmente de façon vertigineuse (il peut expliquer que, pour 20 ressources, il y a plus d’1 milliard de milliards de possibilités). Il demande aux élèves s’ils connaissent un appareil qui permet de trouver le meilleur chemin parmi plusieurs. Il est probable que certains élèves citent le GPS. En remplaçant les ressources par des villes, le problème que doit résoudre un GPS est du même genre (quoi qu’un peu différent : le voyageur de commerce est obligé de passer par toutes les villes, ce qui n’est pas le cas lors de l’utilisation d’un GPS qui doit déterminer le chemin le plus court pour aller d’un endroit à un autre, en passant en général par plusieurs endroits intermédiaires). Comment faire, sachant qu’il existe, non pas 20 villes en France, mais des dizaines de milliers ?
La classe convient qu’il n’est pas possible de tester tous les chemins possibles (même un supercalculateur ne pourrait pas faire ce test en un temps inférieur à l’âge de l’univers !).  Le calculateur contenu dans un GPS procède de façon analogue à notre expérience de la planche à clou : il détermine un chemin au hasard, qu’il fait évoluer plusieurs fois de façon à réduire la longueur totale du trajet. Quand il ne parvient plus à réduire cette longueur de façon significative, il arrête la recherche et propose le meilleur chemin parmi ceux qu’il a explorés. Pour augmenter ses chances, il peut éventuellement tirer plusieurs chemins au hasard et faire évoluer chacun d’entre eux indépendamment.
Le GPS ne fournit donc pas le meilleur chemin possible, mais un chemin « plutôt bon ». Il n’est pas surprenant que 2 GPS différents fournissent, pour un même objectif, 2 solutions différentes car ils diffèrent à la fois par leur carte (qui peut être plus ou moins riche, plus ou moins actualisée) et par leur algorithme.

Conclusion et traces écrites

La classe synthétise collectivement ce qui a été appris au cours de cette séance :

• Parfois, un problème est si long ou si compliqué à résoudre que l’on doit se contenter d'un algorithme qui ne donne pas une solution parfaite.
• Pour certaines tâches, comme trouver le meilleur chemin parmi de nombreuses possibilités, les ordinateurs sont bien plus rapides que les hommes.

Les élèves notent ces conclusions dans leur cahier de sciences. L’enseignant, quant-à-lui, met à jour l’affiche « qu’est-ce que l’informatique ? ».

Prolongement

• Le visionnage du film « The imitation game » racontant la vie d’Alan Turing permet d’illustrer, dans un autre contexte (ici, il s’agit de casser le cryptage des nazis pendant la 2^nde guerre mondiale), qu’il est parfois impossible de tester toutes les possibilités d’un problème et qu’il faut trouver une méthode pour restreindre la taille du problème en se concentrant sur les possibilités « intéressantes ». Même dans ce cas, le champ des possibles est très supérieur à la capacité de traitement d’un ou plusieurs êtres humains. Pour résoudre ce problème, Alan Turing et son équipe ont non seulement dû trouver un algorithme efficace, mais également fabriquer une machine pour l’exécuter : cette machine a conduit aux ordinateurs que nous connaissons aujourd’hui.
• On peut comparer les itinéraires fournis par plusieurs services de cartographie (GoogleMaps, Mappy, ViaMichelin…) ou plusieurs GPS, et ainsi vérifier que ces outils ne fournissent pas LE meilleur chemin (auquel cas, ils donneraient tous le même), mais un chemin « plutôt bon ».