MODULE 2 • SÉANCE 1
Mettre un problème en fiche
La fiche avant l'algorithme
Pour qu'un programme trouve seul une solution, il faut d'abord lui décrire le problème sans rien laisser au hasard. Les spécialistes le font avec une « fiche » de quatre lignes. Cette séance apprend à la remplir : c'est l'étape la plus humaine, et celle qui fait le plus souvent échouer les projets.
À la fin de cette séance, vous saurez
- remplir la fiche : états, actions, but, coût ;
- compter les états d'un problème simple ;
- expliquer pourquoi le chemin direct n'est pas toujours le meilleur.
Les quatre lignes de la fiche
| Ligne | Question | Pour le livreur |
|---|---|---|
| États | Qu'est-ce qui décrit complètement la situation ? | Le point où se trouve le camion (dépôt, gare, marché, parc, musée). |
| Actions | Qu'a-t-on le droit de faire, depuis un état ? | Emprunter un tronçon direct vers un lieu voisin. |
| But | Dans quel état le problème est-il résolu ? | Camion arrivé au musée. |
| Coût | Qu'essaie-t-on de réduire ? | La durée totale du trajet, en minutes. |
Une transition est le passage direct d'un état à un autre par une seule action. Une suite de transitions forme un chemin : c'est lui qu'on cherche.
À essayer : le meilleur trajet
Départ : la Gare. But : le Musée. Voici les tronçons directs et leur durée.
| Tronçon | Minutes |
|---|---|
| Gare ↔ Musée | 9 |
| Gare ↔ Marché | 2 |
| Marché ↔ Parc | 1 |
| Gare ↔ Parc | 4 |
| Parc ↔ Musée | 3 |
| Marché ↔ Musée | 8 |
Cherchez le trajet le plus court avant d'ouvrir la réponse.
Voir la réponse
Gare → Marché → Parc → Musée : 2 + 1 + 3 = 6 minutes, contre 9 par le tronçon direct. Sans la ligne « coût », la machine ne pourrait pas comparer les chemins : elle s'arrêterait au premier qui arrive au but.
Combien d'états, au juste ?
Si une situation se décrit par plusieurs éléments indépendants, on multiplie leurs possibilités.
- Un cadenas à 3 interrupteurs : 2 × 2 × 2 = 8 états.
- Avec 10 interrupteurs : 210 = 1 024 états.
- Avec 30 : plus d'un milliard.
Atelier : les deux jerricans
Un jerrican A de 3 litres, un jerrican B de 5 litres, une source d'eau. Objectif : obtenir exactement 4 litres dans l'un des deux, avec le moins de transitions possible.