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é