Maths, Fourmis, Informatique et Petits Chevaux - 2 Journée des Ludologues 18-06-08 Pierre Chauvet...

Maths, Fourmis, Informatique Maths, Fourmis, Informatique et Petits Chevaux - 2et Petits Chevaux - 2

Journée des Ludologues 18-06-08Journée des Ludologues 18-06-08

Pierre ChauvetIMA – UCO

pierre.chauvet@uco.fr

Partie 2 :Partie 2 :Jeux avec les CavaliersJeux avec les Cavaliers

Activité proposée pour la Fête de la Science en 2006 et 2007 par Laurent Péridy

Public: groupes d’enfants (7 à 12 ans), adultes

Contexte

Le Dispositif…Le Dispositif…

Deux animateurs (L. Péridy, P. Chauvet) Un échiquier en papier (format A3) par auditeur, en général coupé en deux Quelques petits chevaux en papier et un crayon par personne Micro+Vidéoprojecteur, fichier powerpoint

Des échecs aux cavaliers, de Des échecs aux cavaliers, de l’optimisation aux fourmis…l’optimisation aux fourmis…

Distances et chemins

Durée: 1h30 à 2h

Activité 1Activité 1

Prendre un échiquierNuméroter les colonnes : a b c d e f g hNuméroter les lignes : 1 2 3 4 5 6 7 8Colorier d4 en bleuRepérer les cases accessibles à partir de d4

pour le cavalierLes colorier en rouge

Cases rougesCases rouges

Questions 1 Questions 1

Combien de cases rouges avez vous coloriées ? Est-ce qu’une case située à côté de d4 est rouge ? A quelle figure géométrique vous font penser les

cases rouges ? Tracez un trait passant par le centre de chaque case

En un coup peut-on aller d’une case rouge sur une autre case rouge ?

Activité 2Activité 2

Colorier en vert toutes les cases accessibles à partir d’une case rouge.

Cases vertes Cases vertes c6c6

c

6

Cases vertes Cases vertes c6c6 et et e6e6

6

e

Cases vertesCases vertes

Questions 2 Questions 2

En un coup peut-on aller d’une case verte à la case bleue sans passer par une case rouge ?

A quelle figure géométrique vous font penser les cases vertes ?

Quelle est la distance entre la case bleue et les cases vertes ?Notion de longueur/distance

Questions 3 Questions 3

Quelles sont les cases les plus proches de la case bleue ? Les cases vertes ou les cases rouges ?

Questions 4 Questions 4

Proposer un chemin de longueur 3 allant de la case bleue à la case g6 ?

Proposer un chemin de longueur 4 allant de la case bleue à la case g6 ?

Proposer un chemin de longueur 5 allant de la case bleue à la case g6 ?

Quel est le plus court chemin pour aller de la case a1 à la case h8 ?

Activité 4Activité 4

Peut-on visiter une et une seule fois toutes les cases de l’échiquier avec un cavalier ?

Activité 4Activité 4

Peut-on visiter une et une seule fois toutes les cases de l’échiquier avec un cavalier ?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

1

2

3

4

5

6

7

8

9

10

11

12

GrapheGraphe

Notion de graphe :– Des sommets -> un sommet par case– Des arcs -> une flèche entre deux sommets si le

cavalier peut passer d’une case à l’autre en un déplacement

Degré du sommet i = nombre de sommets reliés par un arc au sommet i.

Algorithmes sur les graphesAlgorithmes sur les graphes

Parcours Hamilthonien: – Chemin passant une et une seule fois sur tous les sommets

d’un graphe. Algorithme

– Méthode de résolution– Succession d’étapes conduisant à une solution

Problèmes sur les graphes– Plus courts chemins– Problème du Voyageur de Commerce– …

Les fourmis…Les fourmis…

Conclusion Partie 2Conclusion Partie 2

La majeure partie de l’activité fonctionne de 7 à 77 ans Re-découverte de la notion de distance et longueur (cas non-euclidien), de parcours Exemple d’application amusante de la théorie des graphes Illustration des outils théoriques enseignés et utilisés à l’IMA en logistique