Question transversaleMathsNSIArbres et structures de données

Pourquoi chercher une clé dans un dictionnaire Python est-il instantané, même avec des millions d'entrées ?

Q: Pourquoi (1 − 1/m)ⁿ ≈ e⁽−n/m) ?

On écrit $(1-1/m)ⁿ=e^(nln(1-1/m))$ et $ln(1-1/m)≈-1/m$ pour $m$ grand.

Q: Quelle est l'espérance d'une loi binomiale ?

$E(X)=np$, ici $n×1/m=α$.

Un dictionnaire range chaque clé dans une case calculée par une fonction de hachage. Avec n clés pour m cases, une case contient en moyenne α = n/m clés, et la probabilité qu'une case soit vide vaut environ e^(−α). Si α reste proche de 1, une recherche coûte en moyenne environ 1 + α/2 comparaisons, quelle que soit la taille.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

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.

En NSI, j'ai comparé le temps de recherche d'un élément dans une liste et dans un dictionnaire Python. Pour une liste d'un million d'éléments, la recherche prend un temps visible ; pour un dictionnaire, elle est immédiate. J'ai voulu comprendre ce miracle, et j'ai découvert qu'il repose sur un calcul de probabilités et sur l'exponentielle.

L'enjeu et les notions du programme

Modéliser la répartition des clés par des probabilités, approcher (1 − 1/m)ⁿ par l'exponentielle et en déduire le coût moyen d'une recherche.

Mathématiques

Probabilités, épreuves indépendantes (première)
Limite de (1 + x/n)ⁿ, fonction exponentielle (terminale)
Espérance d'une variable aléatoire, loi binomiale (première, terminale)

Numérique et sciences informatiques

Dictionnaires : clés et valeurs (première)
Fonctions de hachage (terminale)

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

1. Introduction
1 min
Chercher dans une liste demande de la parcourir : jusqu'à $n$ n comparaisons. Un dictionnaire calcule directement, à partir de la clé, le numéro de la case où elle se trouve. Problématique : que se passe-t-il quand deux clés tombent dans la même case, et combien coûte alors une recherche ?
2. Mathématiques : répartir n clés dans m cases
4 min
On modélise la fonction de hachage comme si chaque clé tombait au hasard, uniformément, dans l'une des $m$ m cases. Le nombre de clés dans une case donnée suit la loi binomiale $B (n, \frac{1}{m})$ mathcal B (n,1/m), d'espérance $α = \frac{n}{m}$ α=n/m, appelé taux de remplissage.
Probabilité qu'une case soit vide : $(1 - \frac{1}{m})^{n} = (1 - \frac{1}{m})^{α m} \approx e^{- α}$ (1-1/m)ⁿ=(1-1/m)^(α m)≈ e^(-α), car $(1 + \frac{x}{k})^{k}$ (1+x/k)^(k) tend vers $e^{x}$ e^(x). Pour $α = 1$ α=1, environ 37 % de cases vides ; pour $α = 0, 5$ α=0,5, 61 %.
Coût d'une recherche réussie, quand les clés d'une même case sont rangées à la suite : on compare d'abord à la clé cherchée elle-même, plus en moyenne la moitié des autres clés de la case, soit environ $1 + \frac{α}{2}$ 1+fracα2. Pour $α = 1$ α=1 : 1,5 comparaison en moyenne, que le dictionnaire contienne mille ou un milliard de clés.
3. NSI : garder le taux de remplissage bas
3 min
Python agrandit le tableau quand il se remplit (vers les deux tiers), et recopie toutes les clés : cette opération coûte cher mais est rare, et son coût réparti sur toutes les insertions reste constant en moyenne.
Une mauvaise fonction de hachage, qui envoie beaucoup de clés dans la même case, détruit cette efficacité : la recherche redevient linéaire. C'est pourquoi les clés d'un dictionnaire doivent être immuables (chaînes, nombres, tuples) : si une clé changeait, son hachage changerait et on ne la retrouverait plus.
4. Conclusion
1,5 min
Un dictionnaire est instantané parce que le coût moyen d'une recherche dépend du taux de remplissage $α$ α, environ $1 + \frac{α}{2}$ 1+fracα2, et non du nombre de clés. L'exponentielle décrit la répartition des clés. J'ouvre sur les attaques qui choisissent des clés en collision pour ralentir un serveur.

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.

X~mathcal B (n,1/m), E(X)=α=n/m P( case vide )=(1-1/m)ⁿ≈ e^(-α)α=1: e⁻¹≈0,37 coût moyen ≈1+fracα2=1,5

Conclusion : la réponse à la question

La rapidité d'un dictionnaire est un résultat de probabilités : tant que le taux de remplissage reste borné, le coût moyen d'une recherche est constant. La structure échange de la mémoire contre du temps.

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.

Pourquoi (1 − 1/m)ⁿ ≈ e^(−n/m) ?

On écrit $(1 - \frac{1}{m})^{n} = e^{n l n (1 - 1/ m)}$ (1-1/m)ⁿ=e^(nln(1-1/m)) et $ln (1 - \frac{1}{m}) \approx - \frac{1}{m}$ ln(1-1/m)≈-1/m pour $m$ m grand.

Quelle est l'espérance d'une loi binomiale ?

$E (X) = n p$ E(X)=np, ici $n \times \frac{1}{m} = α$ n×1/m=α.

Pourquoi une liste est-elle lente ?

Il faut la parcourir élément par élément : jusqu'à n comparaisons.

Une liste peut-elle être une clé de dictionnaire ?

Non en Python : elle est modifiable, donc son hachage pourrait changer.

Que coûte un agrandissement du tableau ?

De l'ordre de n opérations, mais il est rare : réparti sur les insertions, le coût moyen reste constant.

Les pièges qui coûtent des points

Croire que les collisions n'existent pas.
Confondre taux de remplissage et nombre de clés.
Oublier que le résultat est un coût moyen, pas une garantie dans le pire cas.

Revoir les notions

Autres questions : arbres et structures de données

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →