Le problème du rangement de boites dans un espace donné est une façon d'aborder la notion de complexité d'un algorithme.

Alice déménage

Sa voiture étant un peu petite, Alice doit fixer des cartons de déménagement de différentes tailles sur le toit. Ils doivent être placés dans le bon sens afin de ne pas les abimer.

Plus la pile sur le toit est haute, moins la voiture est aérodynamique et plus elle consomme d’essence... Elle cherche donc à les empiler en minimisant la hauteur sans dépasser la largeur du toit.

Cette situation est présentée en deux dimensions dans une activité qui utilise des rectangles en bois de différentes tailles. Ils doivent être « empilés » dans un cadre de largeur donnée. Les pièces doivent garder leur orientation (le repère dans le coin supérieur droit) et ne peuvent être tournées. Lorsqu’on a réalisé un empilement on peut s’interroger : Est-ce la meilleure solution ? A-t-on utilisé une stratégie particulière ? Si oui, est-elle généralisable ?

Certaines situations sont assez simples à résoudre. D’autres, comportant plus de pièces de tailles différentes, sont moins faciles et il reste des trous dans l’empilement obtenu. Peut-on espérer faire mieux ? Pourquoi ? Si on donne une solution, est-il facile de vérifier que c’est la meilleure ? Les questions posées ont pour ... Lire la suite