Question transversaleMathsNSIAlgorithmes et complexité

Un ordinateur mille fois plus rapide permet-il de résoudre des problèmes mille fois plus grands ?

Q: Pourquoi l'exponentielle l'emporte-t-elle sur toute puissance ?

Croissances comparées : $lim_n→+∞2ⁿ/n^(k)=+∞$ pour tout entier $k$.

Avec un algorithme linéaire, oui. Avec un coût n², la taille traitable n'est multipliée que par √1000 ≈ 31,6 ; avec n³, par 10. Avec un coût 2ⁿ, on gagne seulement log₂ 1000 ≈ 10 éléments : la vitesse ne vient pas à bout de l'exponentielle.

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.

On entend souvent que les ordinateurs progressent si vite que tout problème finira par être résolu. En NSI, j'ai pourtant vu un programme qui, pour 30 objets, tournait des heures. Je me suis demandé ce que gagnerait une machine mille fois plus rapide. Le calcul m'a surpris : selon l'algorithme, on gagne énormément ou presque rien.

L'enjeu et les notions du programme

Résoudre des équations du type f(n') = 1000 f(n) pour des fonctions puissances et exponentielles, et en déduire la limite de la puissance de calcul.

Mathématiques

Fonctions puissances, racine carrée et cubique (seconde, première)
Fonction exponentielle et logarithme (terminale)
Croissances comparées (terminale)

Numérique et sciences informatiques

Coût d'un algorithme, notion de complexité (première)
Algorithmes exponentiels : recherche exhaustive (terminale)

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

1. Introduction
1 min
En un temps fixé, une machine fait un nombre $N$ N d'opérations. Si elle devient 1 000 fois plus rapide, elle en fait $1000 N$ 1000N. Problématique : quelle taille de problème peut-on alors traiter, selon le coût de l'algorithme ?
2. Mathématiques : résoudre f(n') = 1000 f(n)
4 min
Coût linéaire $f (n) = n$ f(n)=n : $n^{'} = 1000 n$ n'=1000n. On traite des problèmes mille fois plus grands.
Coût quadratique $f (n) = n^{2}$ f(n)=n² : $n^{'2} = 1000 n^{2}$ n'²=1000n², donc $n^{'} = 1000 n \approx 31, 6 n$ n'=√(1000) n≈31,6 n. Coût cubique : $n^{'} = 31000 n = 10 n$ n'= racine 3-ième de (1000) n=10n.
Coût exponentiel $f (n) = 2^{n}$ f(n)=2ⁿ : $2^{n^{'}} = 1000 \times 2^{n}$ 2^(n')=1000×2ⁿ, donc $n^{'} = n + lo g_{2} 1000 \approx n + 10$ n'=n+log₂ 1000≈ n+10. La machine mille fois plus rapide ne traite que 10 éléments de plus ! Si l'on passait de 30 à 40 objets, il faudrait encore la multiplier par 1 000 pour aller à 50.
C'est la traduction des croissances comparées : l'exponentielle l'emporte sur toute puissance. Un progrès multiplicatif de la machine se traduit par un progrès additif de la taille traitable.
3. NSI : où l'on rencontre l'exponentielle
3 min
Les algorithmes exponentiels apparaissent dès qu'on teste toutes les combinaisons : les $2^{n}$ 2ⁿ sous-ensembles d'un ensemble (problème du sac à dos), les $n!$ n! ordres de visite (voyageur de commerce), les $2^{n}$ 2ⁿ affectations de variables booléennes.
Pour ces problèmes, on cherche des algorithmes plus astucieux (programmation dynamique, élagage) ou on accepte des solutions approchées par des heuristiques (algorithmes gloutons). Exemple mesurable en Python : énumérer les sous-ensembles de 20, 21, 22 éléments ; le temps double à chaque élément ajouté.
4. Conclusion
1,5 min
Un ordinateur mille fois plus rapide multiplie par 1 000 la taille des problèmes linéaires, par 31 seulement celle des problèmes quadratiques, et n'ajoute que 10 éléments aux problèmes exponentiels. Le progrès algorithmique compte plus que le progrès matériel. J'ouvre sur la question P = NP.

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.

n^{'2} = 1000 n^{2} \Rightarrow n^{'} \approx 31, 6 n n^{'3} = 1000 n^{3} \Rightarrow n^{'} = 10 n n'²=1000 n²\Rightarrow n'\approx31,6 n n'³=1000 n³\Rightarrow n'=10n 2^{n^{'}} = 1000 \times 2^{n} \Rightarrow n^{'} = n + lo g_{2} 1000 \approx n + 10 2^(n')=1000\times2ⁿ\Rightarrow n'=n+log₂1000\approx n+10

Conclusion : la réponse à la question

La vitesse des machines ne suffit pas face à un coût exponentiel : elle ne fait qu'ajouter quelques éléments. Seule une meilleure méthode change d'échelle, ce que montrent les croissances comparées.

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.

Résolvez 2^x = 1 000.

$x = \frac{l n 1000}{l n 2} \approx 9, 97$ x=ln1000/ln2≈9,97.

Et pour un coût n log₂ n ?

On gagne un peu moins que pour un coût linéaire : presque un facteur 1 000.

Pourquoi l'exponentielle l'emporte-t-elle sur toute puissance ?

Croissances comparées : $n \to + \infty lim \frac{2 ^{n}}{n ^{k}} = + \infty$ lim_n→+∞2ⁿ/n^(k)=+∞ pour tout entier $k$ k.

Combien de sous-ensembles pour 30 objets ?

$2^{30} \approx 1, 07 \times 1 0^{9}$ 2³⁰≈1,07×10⁹.

Qu'est-ce qu'une heuristique ?

Une méthode rapide qui donne une bonne solution sans garantie qu'elle soit la meilleure.

Les pièges qui coûtent des points

Croire que le gain est toujours proportionnel à la vitesse.
Confondre multiplier par 1 000 la taille et ajouter 10 éléments.
Oublier que les constantes comptent pour les petites tailles.

Revoir les notions

Autres questions : algorithmes et complexité

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 →