Activité SNT : « Le robot sauteur »

Au fil des maths vous propose quelques activités « clés en main » pour SNT en classe de Seconde : elles ont été testées et approuvées, profitez-en !
Un grand merci à Éric Bartz de la partager avec nous.
Thème : graphes.

Éric Bartz

⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅♦⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

Cette activité débranchée, réalisée dans le cadre de la formation du DIU EIL, propose la résolution de deux problèmes similaires utilisant des modèles de représentations différentes.
Cette activité est largement inspirée du site Teaching London Computing, en particulier des deux puzzles Knight’s Tour et Tour Guide Activity .
Initialement prévue pour le niveau terminale NSI, l’activité peut parfaitement s’inscrire dans le programme de SNT en classe de Seconde pour illustrer l’utilisation d’un graphe simple.

Thèmes et compétences abordés

Programme de terminale NSI
structure de données : graphe (sommets, arcs, successeurs, …), modélisation de situations sous forme de graphes ; algorithmes sur les graphes : parcours d’un graphe en profondeur ou en largeur, chercher un chemin (circuit hamiltonien) ; histoire de l’informatique : situer dans les temps les principaux événements et leurs protagonistes.

Compétences constitutives de la pensée informatique
analyser et modéliser un problème en termes de flux et de traitement d’information ; reconnaître des situations déjà analysées et réutiliser des solutions ; concevoir des solutions algorithmiques ; développer des capacités d’abstraction et de généralisation.

Positionnement

Cette activité de terminale NSI peut se positionner en introduction de la rubrique structures de données, graphes dans le cadre du développement de la pensée informatique pour résoudre un problème.

Matériel et documents à distribuer

Défi 1, le musée de l’informatique :
- une figurine représentant les visiteurs,
- le plan du musée et le plan guide à compléter (doc 1) ;
Défi 2, le robot sauteur :
- une figurine représentant le robot,
- douze jetons pour les billes d’énergie,
- le plateau de déplacement (doc 3) ;
Les synthèses :
- le graphe du musée avec les salles numérotées (doc 2),
- la fiche d’aide à la construction du graphe défi 2 (doc 4),
- si besoin, le graphe simplifié du musée (doc 5) ;
Devoir maison (facultatif).

Déroulement de l’activité

Présenter rapidement à la classe, l’activité débranchée (ne pas parler du lien entre les deux défis !) puis répartir les élèves en groupes.

Étape 1 : résolution d’un problème simple, le musée de l’informatique

Proposer à chaque groupe de résoudre le premier défi.

Résumé du défi 1
Aider le conservateur du musée à construire un plan-guide de visite. Le parcours devra passer une seule fois dans chaque salle et revenir au point de départ.

Les élèves doivent compléter le document distribué (doc 1).

Étape 2 : trouver tous les parcours possibles

Après une mise en commun des productions des groupes, faire constater que le chemin de la visite complète du musée n’est pas unique (ou poser la question de l’unicité de ce chemin si toutes les solutions proposées sont identiques).

Proposer aux groupes d’approfondir leur réflexion sur la démarche utilisée pour trouver un chemin, leur demander de décrire une méthode qui permettrait de recenser tous les parcours différents (algorithme sommaire).

Distribuer, au meilleur moment, le graphe (doc 2). Il n’est pas attendu à cette étape des détails sur la construction d’un graphe et encore moins sur l’obtention d’un circuit hamiltonien. En revanche, les questions suivantes pourront être progressivement abordées lors de cette première mise en commun :

la solution trouvée est-elle unique ?
y a-t-il d’autres solutions ?
combien ?
comment trouver tous les chemins possibles ?

Étape 3 : tenter de résoudre le défi 2, le robot sauteur

Retour à un travail de groupe : les élèves essaient de résoudre ce second défi.

Résumé du défi 2
Cette fois, c’est un robot sauteur que les élèves doivent programmer. Ils sont chargés de déterminer un chemin que doit parcourir ce robot sur une grille pour revenir à son point initial. Les consignes sont les mêmes qu’au défi 1, excepté le déplacement du robot qui s’effectue comme celui d’un cavalier aux échecs.

Les élèves disposent du plateau de déplacement (doc 3), d’une figurine et de douze jetons afin de faciliter leurs recherches.

Il sera certainement nécessaire de limiter le temps de recherche afin de ne pas décourager les groupes. Si toutefois certains arrivent à proposer une solution, il sera toujours possible de les relancer en leur demandant de refaire le parcours et de décrire la méthode utilisée.

Étape 4 : généralisation des deux défis

Une seconde synthèse en classe entière est nécessaire à l’issue de l’étape précédente. Face aux difficultés rencontrées par les groupes, on peut envisager le scénario suivant :

Demander quel défi est le plus difficile ;
Annoncer que les deux défis correspondent en fait à un même problème et qu’ils peuvent donc se résoudre de la même manière ;
Faire trouver ou remarquer que les consignes sont identiques :
- le déplacement débute et finit dans une même case,
- toutes les cases doivent être visitées,
- il est interdit de se déplacer sur une case déjà visitée,
et faire préciser ce qui rend le défi 1 plus simple (mode de représentation, abstraction des détails superflus, …) ;
Proposer alors de construire pour le défi 2 un graphe afin de simplifier le problème.

Étape 5 : résolution du défi 2 et conclusions

Il est ensuite demandé aux groupes de construire un graphe modélisant le défi 2 en s’appuyant sur la fiche d’aide (doc 4). Une fois le graphe construit, comparer avec le graphe du défi 1 et conclure.

Inverser la démarche pour les groupes en difficulté dans la construction : donner le graphe simplifié avec numéros du défi 1 (doc 5), leur demander d’en déduire un chemin du robot et d’expliquer en conclusion les liens entre les deux défis.

Devoir maison (facultatif)

Un DM peut être proposé en fin de séance. L’idée est d’aborder une partie de la rubrique Histoire de l’informatique du programme par une recherche personnelle des élèves sur les personnalités citées dans le défi 1 et l’élaboration d’un document numérique. Ce travail, à concevoir par groupe, pourra éventuellement être présenté lors d’un oral.

Retour à un travail de groupe : les élèves essaient de résoudre ce second défi.

DÉFI 1 — Le MNSI
Fiche élève (doc 1)

Pour ce premier défi, c’est le directeur du nouveau Musée du Numérique et des Sciences Informatiques qui fait appel à vous. Il souhaite réaliser un guide pour la visite des douze salles de son musée.

Voici ses consignes :

La visite du musée débute et se termine par la salle Al-Khwarizmi ;
Un visiteur doit pouvoir découvrir les onze autres salles sans y revenir ;
Le passage entre deux salles ne peut s’effectuer que par les ouvertures représentées sur le plan.

En vous aidant du plan du musée, compléter la grille de visite guidée demandée.

Plan du MNSI

Ordre visite	Nom de la salle
1	Al-Khwarizmi
2
3
4
5
6
7
8
9
10
11
12

DÉFI 1 — Le MNSI
Fiche élève (doc 2)

Pour vous aider dans la recherche de tous les circuits possibles, le directeur a modélisé le MNSI par ce graphe et a numéroté toutes les salles.

Numéro	Nom de la salle	Numéro	Nom de la salle
1	Al-Khwarizmi	7	Cerf
2	Zimmerman	8	Turing
3	Lovelace	9	Babbage
4	Van Rossum	10	Thorvalds
5	Berners-Lee	11	Pouzin
6	Knuth	12	Stallman

Compléter le tableau ci-dessous détaillant les différents circuits que l’on peut proposer aux visiteurs du musée.

	Circuit
Circuit 1
Circuit 2

DÉFI 2 — Le robot sauteur
Fiche élève (doc 3)

Grille initiale

Le conservateur a été impressionné par la rapidité avec laquelle vous avez résolu son problème, c’est pourquoi il vous fait confiance en vous demandant de programmer son robot sauteur.

Celui ci se déplace par sauts successifs sur la grille comme un cavalier aux échecs : une case dans une direction suivie de deux cases dans une direction différente, ou le contraire :

Exemple 1

Exemple 2

Exemple 3

Mais attention, car pour pouvoir effectuer un saut, le robot a besoin d’une bille d’énergie numérique. Si le robot atterrit sur une case vide, il ne peut plus se déplacer.

Le robot a été chargé initialement et est prêt à effectuer son premier saut de la case 1.

Compléter la liste circuit du code Python permettant de programmer le robot sauteur à revenir à sa position initiale après douze sauts.

DÉFI 2 — Le robot sauteur
Fiche élève (doc 3-suite)

Extrait code `Python`
`circuit = [ , , , , , , , , , , , 1 ] for numero_case in circuit :` `jump_vers(numero_case)`

DÉFI 2 — Structure du graphe
Fiche élève (doc 4)

Grille robot sauteur

Départ du saut	Liste des successeurs
1
2
3
4
5
6
7
8
9
10
11
12

Compléter le tableau des successeurs de chaque case puis construire un graphe modélisant le défi 2.

DÉFI 2 — Et on revient sur le défi 1
Fiche élève (doc 5)

Numéro	Nom de la salle	Numéro	Nom de la salle
1	Al-Khwarizmi	7	Cerf
2	Zimmerman	8	Turing
3	Lovelace	9	Babbage
4	Van Rossum	10	Thorvalds
5	Berners-Lee	11	Pouzin
6	Knuth	12	Stallman

Devoir maison
Fiche élève (doc 6)

Vous avez certainement remarqué que les salles du MNSI portent toutes le nom d’une personnalité ayant marqué l’histoire de l’informatique (Défi 1 — documents 1 et 2). Vous en connaissez certaines, d’autres vous sont inconnues.

De plus ces personnalités sont regroupées dans quatre espaces traitant chacun un thème commun.

Travail demandé (par groupe)
Construire une frise chronologique situant les douze personnalités ; Choisir un des quatre espaces et présenter dans un document numérique (diaporama, affiche, montage vidéo, …) une synthèse de vos recherches sur ce thème choisi et sur ses trois personnalités.