Adhérer ou faire un don

L’algorithmique de la jeep

Philippe Langlois

Résumé de l’article

Le problème étudié est celui de "la traversée du désert". Partant d’une base contenant n fois la quantité de carburant que le véhicule peut emporter, par quel processus ce dernier peut-il aller le plus loin possible ? L’article présente un algorithme solution et montre qu’il est optimal, d’abord pour n valant 2 ou 3, puis pour n quelconque, mais qu’il n’est pas strictement optimal.

Ce problème pratique peut aider les élèves à comprendre la notion d’algorithme non trivial et non lié au calcul sur ordinateur. Des variantes du problème sont proposées suivant les conditions initiales.

Plan de l’article

  • Introduction
  • 1. Mise en place des données
  • 2. Traversée avec 2UK
  • 3. Traversée avec 3UK
  • 4. Algorithme pour n entier quelconque
  • 5. La qualité de l’algorithme $V_n$ pour n entier
  • 6. L’algorithme $V_n$ est optimal
  • Conclusion
  • Appendice
  • Références

- Télécharger l’article en pdf dans son intégralité

(Article mis en ligne par Armelle BOURGAIN)