Comment un hôpital ou un ordinateur peut-il toujours traiter en premier le cas le plus urgent, sans trier sans cesse ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Aux urgences, les patients ne passent pas dans l'ordre d'arrivée mais selon la gravité, et de nouveaux patients arrivent sans cesse. Je me suis demandé comment un logiciel gérerait cela efficacement. En NSI, j'ai découvert le tas binaire, une structure astucieuse où un arbre est caché dans un simple tableau, grâce à une numérotation qui rappelle l'écriture binaire.

L'enjeu et les notions du programme

Exploiter une numérotation des nœuds d'un arbre par des calculs d'indices et majorer le coût des opérations par la hauteur.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Une file de priorité doit permettre d'ajouter un élément et de retirer le plus prioritaire, rapidement, un grand nombre de fois. Trier toute la liste à chaque arrivée coûterait trop cher. Problématique : quelle structure fait mieux ?

2. 2. Mathématiques : un arbre dans un tableau

   4 min

   Un tas est un arbre binaire complet (tous les niveaux pleins sauf peut-être le dernier, rempli de gauche à droite) où chaque parent est plus prioritaire que ses enfants. Le plus prioritaire est donc à la racine.

   On numérote les nœuds niveau par niveau à partir de 0. Les enfants du nœud $i$i sont $2i+1$2i+1 et $2i+2$2i+2, son parent est $\lfloor \frac{i-1}{2}\rfloor$lfloor(i-1)/2rfloor. Ces formules se démontrent : le niveau $k$k occupe les indices $2^k-1$2^(k)-1 à $2^{k+1}-2$2^(k+1)-2, et le $j$j-ième nœud d'un niveau a ses enfants en position $2j$2j et $2j+1$2j+1 du niveau suivant.

   Un arbre complet à $n$n nœuds a une hauteur $\lfloor {\log }_{2}n\rfloor$lfloorlog₂nrfloor. Pour un million d'éléments : 19 niveaux sous la racine. Insérer : on place l'élément à la fin et on le fait remonter en l'échangeant avec son parent tant qu'il est plus prioritaire : au plus 19 échanges. Retirer la racine : on la remplace par le dernier élément, qu'on fait descendre : au plus 19 étapes, chacune avec deux comparaisons.

3. 3. NSI : usages

   3 min

   Le tas sert dans l'algorithme de Dijkstra (extraire le sommet le plus proche), dans les ordonnanceurs des systèmes d'exploitation (quel processus exécuter) et dans le tri par tas : on insère les $n$n éléments puis on retire $n$n fois la racine, soit environ $2n{\log }_{2}n$2nlog₂n opérations au pire, sans mémoire supplémentaire.

   En Python, le module heapq implémente un tas dans une liste. Comparaison de coût pour un million d'opérations sur une file d'un million d'éléments : avec un tas, environ $2\times 10^7$2×10⁷ étapes ; en triant à chaque fois, des milliards.

4. 4. Conclusion

   1,5 min

   Le tas binaire garde toujours le plus urgent à la racine et ne coûte que la hauteur de l'arbre, environ ${\log }_{2}n$log₂n, par opération. La numérotation $2i+1$2i+1, $2i+2$2i+2 range cet arbre dans un tableau sans pointeur. J'ouvre sur le tri par tas, qui en découle directement.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Confondre tas et arbre binaire de recherche.
• Se tromper d'indices selon que l'on commence à 0 ou à 1.
• Croire qu'il faut trier le tableau après chaque insertion.

Revoir les notions

• Fonction logarithme népérien (Terminale spé maths) →
• Suites arithmétiques et géométriques (Première spé maths) →

Autres questions : arbres et structures de données

• Pourquoi peut-on retrouver une donnée parmi un million en une vingtaine d'étapes seulement ?
• Pourquoi l'ordre dans lequel on range des données dans un arbre change-t-il tout ?
• Comment compresser un texte sans perdre la moindre information ?
• Pourquoi chercher une clé dans un dictionnaire Python est-il instantané, même avec des millions d'entrées ?

Toutes les questions maths-nsi →