TNSI : TD des Marmottes au Sommeil Léger⚓︎

Introduction⚓︎

Cette activité présente, même si ce n'est pas visible au premier abord, le concept de compression de données, que nous appliquerons plus particulièrement à des textes.
Après une phase de tâtonnement et d'optimisations on va réfléchir à un algorithme.

Dans cette activité, vous allez aider des marmottes à construire leur nouveau terrier.

Principe du Jeu et Construction du Terrier⚓︎

Principe du Jeu⚓︎

Un groupe de marmottes au sommeil léger (càd qui se réveillent lorsque d'autres marmottes leur passent à côté, durant leur hibernation), moyennement satisfaites de leur terrier actuel, décide de concevoir un nouveau terrier, et de le creuser avant l’hiver.

Chaque marmotte doit dormir dans une Salle (de sommeil) de son terrier
Chaque marmotte se réveille un certain nombre précis de fois (connu à l'avance) durant son hibernation en hiver
Le but de jeu étant de gêner/réveiller le moins possible les autres marmottes durant leur hibernation, car elles ont chacune le Sommeil Léger.

Règles de Construction du Terrier⚓︎

Plus précisément, on déduit des règles du jeu précédentes, que la contruction du terrier doit suivre les $3$ règles suivantes :

Règle de Stabilité du Terrier : A partir de l'entrée, ou à partir de l'extrêmité d'un couloir (appelé un embranchement/noeud), on peut au maximum creuser deux couloirs, sinon la structure risque de s'effondrer.
Règle Individuelle de Sommeil Léger 1 : Pas de marmottes aux embranchements/noeuds.
Autrement dit, les Salles de Sommeil des marmottes sont forcément situées au fin fond d'une galerie.
En effet, si la salle de sommeil était sur un noeud (ou encore pire, au milieu d'un couloir) alors elle se ferait marcher dessus par d'autres marmottes habitant plus loin dans le terrier, et cela la réveillerait : elle a le sommeil léger. Les marmottes dorment donc uniquement au fond d'une galerie qui ne donne sur rien d'autre que sa salle.
Règle Globale de Sommeil Léger 2 : Minimisation du bruit total des déplacements
Même le simple déplacement des marmottes qui se réveillent, à cause du bruit lointain de leurs petites pattes, génère des vibrations qui dérangent le groupe pendant leur sommeil : elles ont vraiment le sommeil léger !! Du coup, comme on sait combien de fois chacune va se réveiller et sortir (et revenir) du terrier pendant l'hiver, l'objectif sera que la somme des déplacements de toutes les marmottes soit la plus petite possible.. Par souci de simplicité (et parce que cela change pas le résultat), on pourra ne compter que les sorties du terrier, inutile de compter les retours dans le terrier.

En Pratique : Comment compter les déplacements des marmottes ?

Voici deux exemples de comptage des déplacements des marmottes :

Une marmotte dormant à $4$ couloirs de l’entrée, et se réveillant $5$ fois dans l’hiver va parcourir $4 \times 5 = 20$ couloirs aller (il faudrait aussi compter les $20$ retours, mais pour simplifier on ne va compter que les allers).
une marmotte qui se réveille $6$ fois, et située à $3$ couloirs de la sortie, devra parcourir $6 \times 3 = 18$ couloirs aller (il faudrait aussi compter les $18$ retours, mais pour avoir des chiffres moins gros on ne va compter que les allers). Si on la mettait à $1$ couloir de la sortie, elle ne parcourrait plus que $6 \times 1 = 6$ couloirs.

Un Vrai Exemple⚓︎

Voici une liste de noms de marmottes, et le nombre de fois qu'elles se réveillent en hiver :

Col

Nom	Nombre de Réveils
`Anne`	$6$
`Benjamin`	$5$
`Romain`	$5$
`Space-Marmotte`	$5$
`Etienne`	$4$
`Isabelle`	$2$
`Lisa`	$2$
`Simon`	$2$
`Ohé!`	$1$

Col

Exemple de Marmottes au Sommeil Léger

Grâce au matériel donné en classe (marmottes papier, et couloirs papier), ou dans le pire des cas, en dessinant sur feuille un arbre, déterminer quel est le meilleur terrier pour ces marmottes.

Lien avec la compression de textes⚓︎

Les textes à envoyer via un canal de communication sont (la plupart du temps) codés en binaire.

On souhaite envoyer le texte suivant via un canal de communication :

BARBARA⎵RASE⎵BLAISE⎵LE⎵BARBIER⎵!

Quel est le lien avec le terrier des marmottes? Expliquer le plus en détail possible.

Références et Matériel⚓︎

Cette activité est directement inspirée de l'activité Les Marmottes au sommeil léger de Marie Duflot Kremer
Le format pratique du TD est issu de l'IREM de grenoble
Ce TD requiert l'impression du kit complet suivant. Télécharger et donner aux élèves.