Questions de Grand oral maths-NSI
Des questions transversales où l'informatique donne un terrain aux mathématiques : arithmétique pour chiffrer, suites et logarithmes pour mesurer le coût d'un algorithme, récurrence pour prouver un programme récursif, probabilités pour simuler le hasard.
Représenter l'information
Binaire, entiers négatifs, nombres flottants, couleurs et caractères.
- Combien de bits faut-il pour écrire un nombre entier, et pourquoi le logarithme répond-il à la question ?Un entier n ≥ 1 s'écrit en binaire avec ⌊log₂ n⌋ + 1 chiffres : 1 000 demande 10 bits, un million 20 bits. Doubler un nombre ne coûte qu'un bit de plus, ce qui explique pourquoi l'informatique manipule sans peine des nombres immenses.Plan, tableau et questions du jury →
- Comment un ordinateur représente-t-il les nombres négatifs, et pourquoi 127 + 1 peut-il donner −128 ?Sur 8 bits, le complément à deux code −x par 256 − x : −23 devient 233, soit 11101001. L'addition devient une addition modulo 256, si bien que l'on soustrait sans circuit dédié, mais 127 + 1 « déborde » et donne −128.Plan, tableau et questions du jury →
- Pourquoi un ordinateur ne peut-il pas représenter tous les nombres réels, et où ses erreurs sont-elles les plus grandes ?Un flottant s'écrit m × 2^e avec 53 bits de mantisse : l'écart entre deux flottants voisins est relatif, environ 2,2 × 10⁻¹⁶ fois la valeur. Au-delà de 2⁵³, les entiers impairs disparaissent : 2⁵³ + 1 n'existe pas en machine.Plan, tableau et questions du jury →
- Combien de couleurs un écran peut-il afficher, et combien pèse une image non compressée ?Avec 8 bits par canal rouge, vert, bleu, un pixel prend 2²⁴ = 16 777 216 couleurs. Une image Full HD de 1 920 × 1 080 pixels pèse 6 220 800 octets, environ 6,2 Mo, et quatre fois plus en 4K : d'où le besoin de compresser.Plan, tableau et questions du jury →
- Pourquoi les informaticiens écrivent-ils en base 16 plutôt qu'en base 10 ?Comme 16 = 2⁴, chaque chiffre hexadécimal remplace exactement 4 bits : un octet s'écrit avec deux chiffres, de 00 à FF = 255. La base 10, elle, ne se découpe pas ainsi, car 10 n'est pas une puissance de 2.Plan, tableau et questions du jury →
- Comment un texte devient-il une suite de bits, et combien de caractères Unicode peut-on coder ?L'ASCII code 2⁷ = 128 caractères. Unicode prévoit 1 114 112 points de code (de 0 à 10FFFF en hexadécimal), dont 1 112 064 utilisables. UTF-8 les écrit sur 1 à 4 octets, avec des préfixes qui rendent le décodage sans ambiguïté.Plan, tableau et questions du jury →
- Pourquoi mon disque de 1 To n'affiche-t-il que 931 Go ?Le fabricant compte 1 To = 10¹² octets, le système divise par 2⁴⁰ : 10¹² / 2⁴⁰ ≈ 0,909, soit 931 « Gio ». L'écart entre 1 000 et 1 024 se cumule à chaque préfixe : 2,4 % pour le kilo, 9,1 % pour le téra.Plan, tableau et questions du jury →
- Comment un processeur, qui ne connaît que des portes logiques, fait-il une addition ?Additionner deux bits, c'est calculer une somme (OU exclusif) et une retenue (ET). En chaînant n additionneurs complets, on additionne deux nombres de n bits : 13 + 11 = 1101 + 1011 = 11000 = 24, colonne par colonne comme à l'école.Plan, tableau et questions du jury →
- Pourquoi décaler les bits d'un nombre revient-il à le multiplier ou le diviser par 2 ?Décaler l'écriture binaire d'un rang vers la gauche multiplie par 2, vers la droite donne le quotient de la division euclidienne par 2. On en déduit une multiplication rapide : 13 × 6 = 13 × 4 + 13 × 2, obtenu par deux décalages et une addition.Plan, tableau et questions du jury →
- Pourquoi certains ordinateurs risquent-ils de croire que nous sommes en 1901 le 19 janvier 2038 ?Unix compte les secondes depuis le 1ᵉʳ janvier 1970. Sur un entier signé de 32 bits, le maximum 2³¹ − 1 = 2 147 483 647 secondes est atteint le 19 janvier 2038 à 3 h 14 min 7 s (UTC) ; une seconde plus tard, le compteur passe à −2³¹, c'est-à-dire le 13 décembre 1901.Plan, tableau et questions du jury →
Cryptographie et sécurité
RSA, échange de clés, hachage, mots de passe.
- Comment peut-on chiffrer un message avec une clé que tout le monde connaît ?Avec RSA, la clé publique (n, e) = (55, 3) chiffre 2 en 2³ = 8, et seule la clé privée d = 27 permet de revenir : le reste de 8²⁷ dans la division par 55 vaut 2. Trouver d exige de factoriser n = 5 × 11, facile ici, hors de portée pour un nombre de 600 chiffres.Plan, tableau et questions du jury →
- Deux personnes peuvent-elles fabriquer un secret commun en ne s'échangeant que des messages publics ?Alice et Bob publient p = 23 et g = 5. Alice envoie 5⁶ → 8, Bob envoie 5¹⁵ → 19 (restes modulo 23). Chacun élève le nombre reçu à son exposant secret et obtient 2 : un espion qui voit 8 et 19 devrait retrouver un exposant, problème du logarithme discret.Plan, tableau et questions du jury →
- Pourquoi une clé de 128 bits est-elle considérée comme incassable par force brute ?Il y a 2¹²⁸ ≈ 3,4 × 10³⁸ clés de 128 bits. À mille milliards d'essais par seconde, les tester toutes prendrait environ 1,1 × 10¹⁹ ans, près d'un milliard de fois l'âge de l'Univers. Chaque bit ajouté double ce temps.Plan, tableau et questions du jury →
- Combien de fichiers faut-il pour que deux d'entre eux aient la même empreinte numérique ?Une empreinte de n bits prend N = 2ⁿ valeurs. Comme pour le paradoxe des anniversaires, une collision devient probable vers √(2 ln 2 · N) ≈ 1,18 · 2^(n/2) fichiers : environ 5 milliards pour 64 bits. D'où des empreintes de 256 bits.Plan, tableau et questions du jury →
- Pourquoi un site ne doit-il jamais stocker nos mots de passe, et à quoi sert le « sel » ?Un site stocke l'empreinte du mot de passe, pas le mot de passe. Sans sel, un attaquant qui vole un million d'empreintes les compare à un dictionnaire d'un million de mots en une seule passe ; avec un sel différent par compte, il doit refaire le travail pour chacun : 10¹² calculs au lieu de 10⁶.Plan, tableau et questions du jury →
- Existe-t-il un chiffrement impossible à casser, même avec une puissance de calcul infinie ?Le masque jetable combine le message avec une clé aléatoire de même longueur par OU exclusif. Si la clé est uniforme et utilisée une seule fois, chaque message chiffré est également probable quel que soit le message clair : le chiffré n'apporte aucune information, ce que Shannon a démontré en 1949.Plan, tableau et questions du jury →
- Un code secret qui a plus de clés qu'il n'y a de grains de sable sur Terre peut-il être cassé ?Une substitution de l'alphabet a 26! ≈ 4 × 10²⁶ clés, environ 88 bits : la force brute est impossible. Pourtant, un programme la casse en quelques secondes en comparant les fréquences des lettres, car le chiffrement conserve la structure du texte.Plan, tableau et questions du jury →
- Comment prouver mathématiquement qu'un message vient bien de moi ?Pour signer, on applique sa clé privée à l'empreinte du message : avec n = 55, d = 27, l'empreinte 4 donne la signature 49. Chacun vérifie avec la clé publique e = 3 : 49³ laisse le reste 4. Seul le détenteur de d peut produire 49.Plan, tableau et questions du jury →
- Comment un ordinateur trouve-t-il en une fraction de seconde un nombre premier de 300 chiffres ?Près de N, environ un nombre sur ln N est premier : vers 2¹⁰²⁴, un sur 710, donc un impair sur 355. On tire des impairs au hasard et on les teste par un test probabiliste rapide : quelques centaines d'essais suffisent en moyenne.Plan, tableau et questions du jury →
- Combien de clés secrètes faut-il pour que cent personnes puissent toutes communiquer deux à deux en secret ?Avec un chiffrement symétrique, chaque paire a besoin de sa clé : C(100, 2) = 4 950 clés, et 499 500 pour mille personnes, une croissance en n². Avec des clés publiques, chacun n'a qu'une paire de clés : 200 clés au total, une croissance linéaire.Plan, tableau et questions du jury →
Algorithmes et complexité
Tris, dichotomie, diviser pour régner, coût d'un algorithme.
- Pourquoi trier un million de nombres peut-il prendre dix minutes ou un centième de seconde selon l'algorithme ?Le tri par sélection fait n(n − 1)/2 comparaisons : 5 × 10¹¹ pour un million de nombres, soit environ 500 s à un milliard d'opérations par seconde. Le tri fusion en fait de l'ordre de n log₂ n ≈ 2 × 10⁷, soit 0,02 s. L'écart vient de la forme de la fonction, pas de la machine.Plan, tableau et questions du jury →
- Pourquoi couper un problème en deux permet-il de le résoudre beaucoup plus vite ?Le coût du tri fusion vérifie C(n) = 2C(n/2) + n et C(1) = 0. Pour n = 2^k, une récurrence donne C(n) = n log₂ n : 1 024 éléments demandent environ 10 240 opérations au lieu des 523 776 comparaisons du tri par sélection.Plan, tableau et questions du jury →
- Peut-on inventer un algorithme de tri encore plus rapide, ou existe-t-il une limite infranchissable ?Un tri par comparaisons doit distinguer les n! ordres possibles ; chaque comparaison ne fait que diviser les possibilités par 2 au mieux, il en faut donc au moins log₂(n!). Pour 4 nombres, 24 ordres demandent 5 comparaisons ; pour 10, 22. Et log₂(n!) est de l'ordre de n log₂ n.Plan, tableau et questions du jury →
- Un ordinateur mille fois plus rapide permet-il de résoudre des problèmes mille fois plus grands ?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.Plan, tableau et questions du jury →
- Rendre la monnaie avec le moins de pièces possible : faut-il toujours prendre la plus grosse pièce ?Avec les pièces en euros, prendre toujours la plus grosse pièce possible donne le minimum. Mais avec des pièces de 1, 3 et 4, rendre 6 de façon gloutonne donne 4 + 1 + 1 (3 pièces) alors que 3 + 3 suffit. La programmation dynamique trouve toujours l'optimum.Plan, tableau et questions du jury →
- Pourquoi le problème du sac à dos résiste-t-il à la puissance des ordinateurs ?Choisir des objets de valeur maximale sans dépasser un poids, c'est explorer jusqu'à 2ⁿ sous-ensembles : 2⁵⁰ ≈ 1,1 × 10¹⁵, treize jours à un milliard d'essais par seconde. La programmation dynamique, en n × W opérations pour une capacité entière W, contourne l'explosion quand W est petit.Plan, tableau et questions du jury →
- Pourquoi trouver le plus court circuit passant par vingt villes est-il si difficile ?Pour n villes, il y a (n − 1)!/2 circuits différents : 181 440 pour 10 villes, 6 × 10¹⁶ pour 20, soit près de deux ans à un milliard de circuits par seconde. On utilise des heuristiques, comme aller toujours au plus proche voisin, sans garantie d'optimalité.Plan, tableau et questions du jury →
- Pourquoi l'algorithme d'Euclide, vieux de 2 300 ans, est-il toujours aussi rapide ?Le PGCD de 1 071 et 462 s'obtient en 3 divisions. Le pire cas est celui de deux termes consécutifs de Fibonacci : 89 et 55 demandent 9 divisions. Le nombre d'étapes ne dépasse pas environ 5 fois le nombre de chiffres du plus petit nombre (théorème de Lamé).Plan, tableau et questions du jury →
- Comment un logiciel trouve-t-il un mot dans un livre entier sans comparer chaque lettre ?La recherche naïve d'un motif de m lettres dans un texte de n lettres fait jusqu'à (n − m + 1) × m comparaisons. L'algorithme de Boyer-Moore compare de droite à gauche et saute jusqu'à m positions à la fois : pour un motif de 5 lettres, il peut lire cinq fois moins de caractères.Plan, tableau et questions du jury →
- Peut-on multiplier deux grands nombres plus vite qu'avec la méthode apprise à l'école ?La multiplication posée de deux nombres de n chiffres coûte n² produits de chiffres. Karatsuba remplace 4 multiplications de moitiés par 3, d'où un coût en n^(log₂ 3) ≈ n^1,585 : pour 1 024 chiffres, 59 049 produits au lieu de 1 048 576.Plan, tableau et questions du jury →
Récursivité et récurrence
Programmes qui s'appellent eux-mêmes et preuves par récurrence.
- Comment être sûr qu'un programme récursif donne toujours le bon résultat ?Une fonction récursive se prouve comme une propriété mathématique : par récurrence. Pour fact(n) = n × fact(n − 1) avec fact(0) = 1, l'initialisation est le cas de base et l'hérédité suit l'appel récursif. Tester des valeurs ne suffit pas, la récurrence couvre tous les entiers.Plan, tableau et questions du jury →
- Pourquoi un programme récursif de quatre lignes met-il des secondes à calculer le 30ᵉ terme de Fibonacci ?La fonction fib(n) = fib(n − 1) + fib(n − 2) fait A(n) = 2F(n + 1) − 1 appels : 177 pour n = 10, 2 692 537 pour n = 30. Le nombre d'appels croît comme 1,618ⁿ. En mémorisant les résultats, on passe à n appels seulement.Plan, tableau et questions du jury →
- Pourquoi un programme récursif peut-il « déborder » alors que le même calcul en boucle fonctionne ?Chaque appel récursif en attente occupe une place dans la pile d'appels. Calculer la somme 1 + 2 + … + n récursivement demande n appels empilés : Python refuse au-delà d'environ 1 000. La boucle n'empile rien, et la formule n(n + 1)/2 ne fait qu'un calcul.Plan, tableau et questions du jury →
- Comment une figure dessinée par un programme récursif peut-elle avoir une aire nulle et une infinité de triangles ?À chaque étape, chaque triangle est remplacé par 3 triangles de côté moitié : 3ⁿ triangles, et une aire multipliée par (3/4)ⁿ, qui tend vers 0 (0,056 après 10 étapes). Sa dimension, log 3 / log 2 ≈ 1,585, est entre celle d'une ligne et celle d'une surface.Plan, tableau et questions du jury →
- De combien de façons peut-on monter un escalier en faisant des pas d'une ou deux marches ?En regardant le dernier pas, le nombre de façons E(n) vérifie E(n) = E(n − 1) + E(n − 2), avec E(1) = 1 et E(2) = 2 : c'est la suite de Fibonacci décalée. Un escalier de 10 marches se monte de 89 façons, un de 20 marches de 10 946 façons.Plan, tableau et questions du jury →
- Comment un programme peut-il énumérer toutes les façons de ranger n objets, et combien de temps cela prend-il ?Pour ranger n objets, on choisit le premier puis on range récursivement les n − 1 autres : P(n) = n × P(n − 1), d'où n! permutations. 10 objets donnent 3 628 800 rangements, énumérés en quelques secondes ; 20 objets, environ 2,4 × 10¹⁸, demanderaient des dizaines d'années.Plan, tableau et questions du jury →
- Comment démontrer qu'une fonction récursive très étrange renvoie toujours 91 ?M(n) = n − 10 si n > 100, et M(n) = M(M(n + 11)) sinon. On démontre par récurrence descendante que M(n) = 91 pour tout n ≤ 100, d'abord pour 90 ≤ n ≤ 100, puis par blocs de 11. Un programme qui semble chaotique cache un comportement très simple.Plan, tableau et questions du jury →
- Combien y a-t-il de façons de placer correctement n paires de parenthèses ?Une expression bien parenthésée se décompose en ( A ) B, avec A et B bien parenthésées : C(n + 1) = Σ C(i) × C(n − i). On obtient 1, 1, 2, 5, 14, 42… et 16 796 pour 10 paires, qui est aussi C(20, 10) / 11.Plan, tableau et questions du jury →
- Le tri rapide est quadratique dans le pire cas : pourquoi est-il pourtant si utilisé ?Le tri rapide coupe la liste autour d'un pivot. Au pire, il fait n(n − 1)/2 comparaisons (499 500 pour n = 1 000) ; en moyenne, avec un pivot au hasard, environ 2n ln n, soit à peu près 11 000 pour n = 1 000. Le hasard rend le pire cas extrêmement improbable.Plan, tableau et questions du jury →
- Pourquoi additionner les chiffres d'un nombre, puis recommencer, donne-t-il toujours son reste dans la division par 9 ?Comme 10ᵏ − 1 est divisible par 9, un nombre et la somme de ses chiffres ont le même reste dans la division par 9. En répétant récursivement, on arrive à un chiffre : 2 026 → 10 → 1, et 2 026 = 9 × 225 + 1. La preuve par neuf en découle, avec ses limites.Plan, tableau et questions du jury →
Graphes et réseaux
Plus courts chemins, parcours, PageRank, coloriage.
- Comment un GPS trouve-t-il le plus court chemin sans essayer tous les itinéraires ?L'algorithme de Dijkstra fixe à chaque étape le sommet le plus proche non encore traité. Sur un graphe de six villes, il trouve le trajet A → C → B → D → E → F de longueur 12 en six étapes. Sa correction repose sur la positivité des distances.Plan, tableau et questions du jury →
- Comment classer les pages du web par importance en ne regardant que les liens entre elles ?Un internaute qui clique au hasard sur des liens finit par passer sur chaque page une proportion stable de son temps : c'est le PageRank. Pour trois pages A → B, A → C, B → C, C → A, on trouve (0,4 ; 0,2 ; 0,4), et environ (0,39 ; 0,21 ; 0,40) avec le facteur d'amortissement 0,85.Plan, tableau et questions du jury →
- Peut-on parcourir tous les ponts d'une ville une seule fois chacun ? Le problème des ponts de KönigsbergEuler a montré en 1736 qu'un graphe connexe admet un chemin passant une fois par chaque arête seulement s'il a 0 ou 2 sommets de degré impair. Königsberg en a 4 (degrés 3, 3, 3 et 5) : la promenade est impossible. La somme des degrés, 14, vaut deux fois le nombre de ponts.Plan, tableau et questions du jury →
- Est-il vrai que tout le monde sur Terre est relié à n'importe qui par une chaîne de six connaissances ?Si chacun connaît 150 personnes, on atteint au plus 150ᵏ personnes en k étapes : 3,4 millions en 3, 506 millions en 4, 76 milliards en 5. Il suffit de k ≈ ln(8,1 × 10⁹) / ln 150 ≈ 4,6 étapes, si les cercles ne se recoupaient pas. Les recouvrements expliquent qu'on en mesure plutôt 4 à 6.Plan, tableau et questions du jury →
- Combien de créneaux faut-il au minimum pour organiser des examens sans qu'aucun élève n'en ait deux en même temps ?On relie deux épreuves qui ont un élève en commun ; il faut colorier le graphe sans que deux sommets voisins aient la même couleur. Un triangle impose au moins 3 couleurs, et l'algorithme glouton en utilise au plus Δ + 1, où Δ est le plus grand degré. Sur l'exemple, 3 créneaux suffisent.Plan, tableau et questions du jury →
- Comment un programme trouve-t-il le chemin le plus court pour sortir d'un labyrinthe ?Le parcours en largeur explore les cases par couches : toutes celles à distance 1, puis 2, etc. La première fois qu'il atteint la sortie, il a trouvé un plus court chemin. Pour un labyrinthe de 20 × 20 cases, il visite au plus 400 cases et examine au plus 760 passages.Plan, tableau et questions du jury →
- Comment relier toutes les villes d'une région par un réseau de fibre optique au moindre coût ?Un réseau qui relie n villes sans boucle est un arbre à n − 1 câbles. Il existe nⁿ⁻² arbres possibles sur n villes (formule de Cayley) : 10⁸ pour dix villes. L'algorithme de Kruskal trouve le moins cher en ajoutant les câbles du moins cher au plus cher, sauf s'ils créent un cycle.Plan, tableau et questions du jury →
- Pourquoi mes amis ont-ils en moyenne plus d'amis que moi ?En choisissant un ami au hasard, on tombe plus souvent sur une personne très connectée. La moyenne du nombre d'amis d'un ami vaut E(d²)/E(d) = E(d) + V(d)/E(d) : sur un petit réseau de degrés 3, 2, 2, 1, elle vaut 2,25 contre 2 en moyenne. Elle dépasse la moyenne dès que les degrés varient.Plan, tableau et questions du jury →
- Comment les routeurs d'internet apprennent-ils les meilleures routes, et pourquoi peuvent-ils se tromper ?Avec RIP, chaque routeur reprend les distances annoncées par ses voisins et ajoute 1 : en au plus n − 1 échanges, chacun connaît les plus courts chemins (algorithme de Bellman-Ford). Si une liaison tombe, deux routeurs peuvent se renvoyer des distances qui croissent de 1 en 1 : c'est pourquoi RIP fixe l'infini à 16.Plan, tableau et questions du jury →
- Combien de temps faut-il au minimum pour mener un projet dont les tâches dépendent les unes des autres ?On représente les tâches et leurs dépendances par un graphe orienté sans cycle. La durée minimale du projet est la longueur du plus long chemin : pour A (3 j), B (2 j) et C (4 j) après A, D (1 j) après B et C, E (2 j) après D, le chemin A-C-D-E impose 10 jours, et B dispose de 2 jours de marge.Plan, tableau et questions du jury →
Arbres et structures de données
Hauteur d'un arbre, arbres de recherche, tas, piles et files.
- Pourquoi peut-on retrouver une donnée parmi un million en une vingtaine d'étapes seulement ?Un arbre binaire de hauteur h contient au plus 2^(h+1) − 1 nœuds. Pour ranger un million de données, il faut donc une hauteur d'au moins 19 : dans un arbre bien équilibré, une recherche descend au plus d'une vingtaine de niveaux, comme une dichotomie.Plan, tableau et questions du jury →
- Pourquoi l'ordre dans lequel on range des données dans un arbre change-t-il tout ?Insérer 1, 2, 3, …, n dans cet ordre donne un arbre filiforme de hauteur n − 1, où chercher coûte jusqu'à n comparaisons. Dans un ordre aléatoire, la profondeur moyenne d'un nœud est environ 2 ln n ≈ 1,39 log₂ n : environ 28 pour un million, au lieu de 500 000 en moyenne.Plan, tableau et questions du jury →
- Comment un hôpital ou un ordinateur peut-il toujours traiter en premier le cas le plus urgent, sans trier sans cesse ?Un tas binaire range n éléments dans un tableau : les enfants de la case i sont en 2i + 1 et 2i + 2. Le plus urgent est toujours à la racine, et chaque insertion ou retrait ne coûte qu'environ log₂ n échanges : 20 pour un million d'éléments, au lieu de trier à chaque fois.Plan, tableau et questions du jury →
- Comment compresser un texte sans perdre la moindre information ?Huffman donne des codes courts aux lettres fréquentes, grâce à un arbre construit en fusionnant les deux symboles les plus rares. ABRACADABRA passe de 33 bits (3 bits par lettre) à 23 bits, près de la limite de 22,4 bits fixée par l'entropie de Shannon.Plan, tableau et questions du jury →
- Pourquoi chercher une clé dans un dictionnaire Python est-il instantané, même avec des millions d'entrées ?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.Plan, tableau et questions du jury →
- Comment une calculatrice évalue-t-elle une expression avec des parenthèses ? La notation polonaise inverséeEn notation polonaise inversée, (3 + 4) × (5 − 2) s'écrit 3 4 + 5 2 − × : plus besoin de parenthèses. Une pile suffit pour l'évaluer : on empile les nombres et chaque opérateur remplace les deux derniers par leur résultat, ici 21. Cette écriture correspond au parcours suffixe de l'arbre de l'expression.Plan, tableau et questions du jury →
- Pourquoi une file d'attente explose-t-elle quand un serveur approche les 100 % d'occupation ?Dans le modèle d'attente le plus simple, le nombre de clients présents suit une loi géométrique décalée, d'espérance ρ/(1 − ρ), où ρ est le taux d'occupation. À 50 %, 1 client en moyenne ; à 90 %, 9 ; à 99 %, 99. Passer de 90 à 95 % d'occupation double l'attente.Plan, tableau et questions du jury →
- Comment deviner un personnage parmi un million en vingt questions seulement ?Chaque question à réponse oui ou non sépare les possibilités en deux. Un arbre de décision de hauteur 20 a 2²⁰ = 1 048 576 feuilles : 20 questions suffisent pour un million de personnages, à condition que chacune coupe l'ensemble en deux moitiés. Il en faudrait 33 pour toute l'humanité.Plan, tableau et questions du jury →
- Un ordinateur peut-il prévoir tous les coups d'une partie d'échecs ?Au morpion, il y a au plus 9! = 362 880 suites de coups (255 168 parties réelles) : un programme explore tout. Aux échecs, avec environ 30 coups possibles par position, l'arbre compte de l'ordre de 10¹²⁰ parties : impossible. On explore quelques coups à l'avance avec l'algorithme minimax et l'élagage alpha-bêta.Plan, tableau et questions du jury →
- Comment un arbre peut-il compresser une image qui contient de grandes zones de même couleur ?Un arbre quaternaire découpe une image en quatre carrés, puis redécoupe seulement les carrés non uniformes. Une image de 1 024 × 1 024 pixels uniforme tient en un nœud ; au pire, l'arbre a (4¹¹ − 1)/3 = 1 398 101 nœuds, plus que le million de pixels. Le gain dépend donc de l'image.Plan, tableau et questions du jury →
Hasard et simulation
Monte-Carlo, générateurs pseudo-aléatoires, collisions.
- Comment un ordinateur, machine parfaitement déterministe, peut-il produire du hasard ?Un générateur congruentiel calcule xₙ₊₁ = reste de (a xₙ + c) par m. Avec a = 5, c = 3, m = 16, la suite parcourt les 16 valeurs avant de se répéter ; avec a = 4, c = 1, elle reste bloquée sur 5. C'est une suite récurrente, donc prévisible : du hasard « apparent », choisi avec soin.Plan, tableau et questions du jury →
- Comment mélanger une liste pour que tous les ordres soient vraiment équiprobables ?Échanger chaque élément avec un élément tiré parmi tous donne nⁿ issues : 27 pour 3 éléments, qui ne se partagent pas également entre les 6 ordres (5, 5, 5, 4, 4, 4). L'algorithme de Fisher-Yates tire parmi les éléments restants : n! issues, une par ordre, donc un mélange parfaitement uniforme.Plan, tableau et questions du jury →
- Comment simuler un dé à six faces équitable avec une simple pièce de monnaie ?Trois lancers donnent 8 issues équiprobables : on garde 1 à 6 et on recommence sur 7 et 8. Chaque essai réussit avec probabilité 6/8, donc le nombre d'essais suit une loi géométrique d'espérance 4/3 : il faut en moyenne 4 lancers de pièce pour un lancer de dé.Plan, tableau et questions du jury →
- Peut-on obtenir un tirage parfaitement équitable avec une pièce truquée dont on ignore le biais ?On lance la pièce deux fois : pile-face donne « pile », face-pile donne « face », et on recommence sinon. Les deux issues ont la même probabilité p(1 − p), quel que soit p. Pour p = 0,7, il faut en moyenne 1/0,42 ≈ 2,38 paires, soit environ 4,8 lancers.Plan, tableau et questions du jury →
- Après n pas faits au hasard, à quelle distance de son point de départ se trouve-t-on ?Un marcheur fait n pas de ±1 au hasard. Sa position Sₙ a une espérance nulle mais une variance n, donc un écart type √n : après 100 pas, il est typiquement à une dizaine de pas de son départ ; après 10 000 pas, à une centaine. La distance croît comme la racine du temps.Plan, tableau et questions du jury →
- Comment choisir au hasard un message parmi un flux dont on ne connaît pas la longueur à l'avance ?L'échantillonnage par réservoir garde le i-ème élément avec la probabilité 1/i, à la place du précédent. À la fin, chaque élément a été choisi avec la probabilité (1/i) × (i/i + 1) × … × ((n − 1)/n) = 1/n : un produit télescopique donne un tirage uniforme sans connaître n.Plan, tableau et questions du jury →
- Combien de vignettes faut-il acheter en moyenne pour compléter un album de 600 images ?Quand on possède déjà k vignettes sur n, la suivante est nouvelle avec la probabilité (n − k)/n : l'attente suit une loi géométrique d'espérance n/(n − k). En sommant, on obtient n(1 + 1/2 + … + 1/n) ≈ n ln n : environ 4 185 vignettes pour un album de 600, sept fois plus que le nombre d'images.Plan, tableau et questions du jury →
- Comment vérifier qu'un générateur de nombres aléatoires n'est pas truqué ?Sur 10 000 lancers de dé simulés, la fréquence du 6 doit tomber, dans environ 95 % des cas, dans l'intervalle [1/6 − 1/√n ; 1/6 + 1/√n] ≈ [0,157 ; 0,177]. Une fréquence en dehors fait douter du générateur. Un test ne prouve jamais qu'il est bon : il peut seulement détecter un défaut.Plan, tableau et questions du jury →
- À pile ou face, pourquoi la séquence « face, pile » apparaît-elle plus vite que « pile, pile » ?En lançant une pièce, il faut en moyenne 4 lancers pour voir « face, pile » mais 6 pour « pile, pile ». Et si deux joueurs parient sur PP et FP, celui qui a choisi FP gagne 3 fois sur 4 : PP ne peut gagner que si les deux premiers lancers sont pile.Plan, tableau et questions du jury →
- Pourquoi miner un bloc de bitcoin est-il une loterie dont on peut calculer les chances ?Un mineur doit trouver une empreinte qui commence par k zéros binaires : chaque essai réussit avec la probabilité 2⁻ᵏ, donc il faut en moyenne 2ᵏ essais. Le réseau règle k pour qu'un bloc arrive toutes les 10 minutes en moyenne ; la probabilité d'attendre plus de 30 minutes vaut alors environ e⁻³ ≈ 5 %.Plan, tableau et questions du jury →
Données et intelligence artificielle
Plus proches voisins, régression, descente de gradient.
- Comment une machine peut-elle classer une donnée nouvelle en regardant simplement ses voisines ?L'algorithme des k plus proches voisins attribue à un point la classe majoritaire parmi les k points connus les plus proches. Sur un exemple, le point (3 ; 3) est classé B avec k = 1 (voisin à distance 1) mais A avec k = 3 (distances 1, √2 et 2) : le choix de k change la réponse.Plan, tableau et questions du jury →
- Pourquoi le résultat d'un algorithme d'intelligence artificielle peut-il changer si l'on mesure en millimètres plutôt qu'en centimètres ?Avec la taille en centimètres et le poids en kilogrammes, la personne la plus proche de A(170 cm ; 60 kg) est B(180 ; 61). En millimètres, c'est C(171 ; 75) : l'écart de taille, multiplié par 10, écrase celui du poids. En centrant-réduisant chaque variable, on rend la distance indépendante des unités.Plan, tableau et questions du jury →
- Comment une machine trouve-t-elle la droite qui résume le mieux un nuage de points ?La droite des moindres carrés minimise la somme des carrés des écarts verticaux. Pour une pente fixée, cette somme est un polynôme du second degré en l'ordonnée à l'origine, minimal au sommet de la parabole. Sur 5 points, on trouve y = 1,7x + 1,3 et l'on prédit 11,5 pour x = 6.Plan, tableau et questions du jury →
- Comment une intelligence artificielle apprend-elle en corrigeant ses erreurs pas à pas ?Pour minimiser f(x) = (x − 3)², on répète xₙ₊₁ = xₙ − η f'(xₙ). L'écart à 3 est multiplié par 1 − 2η à chaque pas : avec η = 0,1, il est multiplié par 0,8 et tend vers 0 ; avec η = 1,1, il est multiplié par −1,2 et explose. Le « taux d'apprentissage » η doit être bien choisi.Plan, tableau et questions du jury →
- Pourquoi un neurone artificiel seul ne peut-il pas apprendre le « ou exclusif » ?Un neurone artificiel répond 1 si w₁x₁ + w₂x₂ ≥ θ. Il réalise le ET et le OU, mais pas le OU exclusif : les conditions 0 < θ, w₁ ≥ θ, w₂ ≥ θ et w₁ + w₂ < θ sont contradictoires. Géométriquement, aucune droite ne sépare les deux classes ; il faut une couche de neurones de plus.Plan, tableau et questions du jury →
- Comment une intelligence artificielle transforme-t-elle un score en probabilité ?La fonction σ(x) = 1/(1 + e⁻ˣ) envoie tout réel dans ]0 ; 1[ : σ(0) = 0,5, σ(2) ≈ 0,88, σ(−2) ≈ 0,12. Elle est croissante, sa courbe est symétrique autour de (0 ; 0,5), et sa dérivée vaut σ(1 − σ), ce qui facilite l'apprentissage.Plan, tableau et questions du jury →
- Pourquoi une intelligence artificielle qui ne fait aucune erreur sur ses données d'entraînement peut-elle être mauvaise ?Par 4 points mesurés on peut toujours faire passer un polynôme de degré 3 : erreur nulle. Mais sur les points (0 ; 0), (1 ; 1,2), (2 ; 1,8), (3 ; 3,1), il prédit 13 en x = 5, alors que la droite des moindres carrés, y ≈ 0,99x + 0,04, prédit environ 5. Le modèle trop souple a appris le bruit.Plan, tableau et questions du jury →
- Un détecteur de fraude juste dans 99 % des cas est-il forcément utile ?Si 1 % des opérations sont frauduleuses, un détecteur qui dit toujours « pas de fraude » est juste dans 99 % des cas, mais n'en trouve aucune. Un vrai détecteur qui repère 80 fraudes sur 100 avec 200 fausses alertes n'est juste qu'à 97,8 %, mais son rappel est de 80 % et sa précision de 29 %.Plan, tableau et questions du jury →
- Comment un filtre anti-spam décide-t-il qu'un message est indésirable à partir des mots qu'il contient ?Si 40 % des messages sont des spams, que « gratuit » apparaît dans 30 % des spams et 2 % des autres, la formule de Bayes donne P(spam | « gratuit ») ≈ 91 %. En ajoutant « urgent » (20 % des spams, 1 % des autres) et en supposant les mots indépendants, on passe à 99,5 %.Plan, tableau et questions du jury →
- Comment une machine peut-elle former des groupes dans des données sans qu'on lui dise lesquels ?L'algorithme des k-moyennes alterne deux étapes : affecter chaque point au centre le plus proche, puis remplacer chaque centre par la moyenne de son groupe. La moyenne minimise la somme des carrés des écarts, donc l'erreur ne peut que diminuer. Sur 1, 2, 3, 10, 11, 12, il trouve les centres 2 et 11 en deux tours.Plan, tableau et questions du jury →
Transmettre et compresser
Bits de contrôle, codes correcteurs, compression.
- Comment un ordinateur peut-il savoir qu'un message a été abîmé pendant sa transmission ?On ajoute à 8 bits un neuvième bit pour que le nombre de 1 soit pair. Une erreur isolée rend ce nombre impair : elle est détectée. Deux erreurs passent inaperçues ; si chaque bit est faussé avec une probabilité 0,01, la probabilité d'une erreur non détectée est d'environ 0,34 %.Plan, tableau et questions du jury →
- Comment un message peut-il se réparer tout seul quand un bit a été faussé ?Le code de Hamming (7, 4) ajoute 3 bits de contrôle à 4 bits de données. Les trois tests de parité, lus comme un nombre binaire, donnent directement la position du bit faussé : 101₂ = 5. Avec 3 bits on décrit 2³ = 8 situations, exactement « aucune erreur » ou une erreur parmi 7 positions.Plan, tableau et questions du jury →
- Comment un site marchand sait-il instantanément qu'un numéro de carte bancaire a été mal recopié ?Le dernier chiffre d'une carte bancaire est une clé de Luhn : on double un chiffre sur deux en partant de la droite, on retire 9 aux résultats supérieurs à 9, et la somme doit être un multiple de 10. Pour 7992739871, la clé vaut 3. Toute faute sur un chiffre est détectée, et presque toutes les inversions de deux chiffres voisins.Plan, tableau et questions du jury →
- Pourquoi la clé d'un IBAN repose-t-elle sur le reste de la division par 97 ?Un IBAN est valide si un grand nombre formé à partir de lui laisse le reste 1 dans la division par 97. Comme 97 est premier et ne divise ni 10 ni aucun nombre de 1 à 9, toute faute sur un chiffre change le reste. Une inversion de deux chiffres voisins change le nombre de 9(a − b) × 10ᵏ, jamais multiple de 97 : elle est aussi détectée.Plan, tableau et questions du jury →
- Répéter chaque bit trois fois suffit-il à rendre une transmission fiable ?En envoyant chaque bit trois fois et en gardant la valeur majoritaire, un bit est faux seulement si au moins 2 des 3 copies le sont : probabilité 3p² − 2p³, soit 2,8 % pour p = 10 %, et 0,03 % pour p = 1 %. Mais on divise le débit utile par trois : il existe des codes bien plus efficaces.Plan, tableau et questions du jury →
- Existe-t-il une limite au débit d'internet sur un câble ou une onde radio ?Shannon a montré qu'un canal de bande passante B et de rapport signal sur bruit S/N ne peut transmettre sans erreur plus de C = B log₂(1 + S/N) bits par seconde. Pour 1 MHz et S/N = 1 000, environ 10 Mbit/s. Doubler la bande double le débit ; doubler la puissance n'ajoute qu'environ 1 Mbit/s.Plan, tableau et questions du jury →
- Existe-t-il un logiciel capable de réduire la taille de n'importe quel fichier ?Il y a 2ⁿ fichiers de n bits, mais seulement 2ⁿ − 1 fichiers strictement plus courts (de 0 à n − 1 bits). Par le principe des tiroirs, aucun algorithme sans perte ne peut raccourcir tous les fichiers : s'il en raccourcit certains, il doit en allonger d'autres.Plan, tableau et questions du jury →
- Comment un fichier arrive-t-il intact alors qu'internet perd régulièrement des paquets ?Si chaque paquet est perdu avec une probabilité 2 %, la probabilité que 1 000 paquets arrivent tous du premier coup est 0,98¹⁰⁰⁰ ≈ 1,7 × 10⁻⁹ : presque nulle. Mais en renvoyant chaque paquet perdu, le nombre d'envois par paquet suit une loi géométrique d'espérance 1/0,98 ≈ 1,02 : le coût n'est que de 2 %.Plan, tableau et questions du jury →
- Combien d'erreurs un code peut-il corriger, et comment le savoir en mesurant des distances entre mots binaires ?La distance de Hamming compte les positions où deux mots diffèrent. Si les mots d'un code sont tous à distance au moins d, il détecte d − 1 erreurs et en corrige ⌊(d − 1)/2⌋. Le code de Hamming (7, 4) a d = 3 et ses 16 « boules » de 8 mots remplissent exactement les 128 mots de 7 bits.Plan, tableau et questions du jury →
- Comment un serveur peut-il perdre un disque dur sans perdre aucune donnée ?Avec trois disques de données et un disque de parité qui stocke leur OU exclusif, n'importe quel disque perdu se reconstruit : B = A ⊕ C ⊕ P. Si chaque disque a 2 % de risque de panne par an, perdre des données exige deux pannes : environ 0,23 % au lieu de près de 6 % sans protection.Plan, tableau et questions du jury →
Logique et calculabilité
Booléens, problème de l'arrêt, infinis de Cantor.
- Peut-on écrire un programme qui détecte tous les programmes qui tournent en boucle infinie ?Turing a démontré en 1936 qu'aucun programme ne peut décider, pour tout programme et toute entrée, s'il s'arrête. Si un tel programme « arrete » existait, on construirait un programme « paradoxe » qui boucle quand arrete dit qu'il s'arrête : appliqué à lui-même, il mène à une contradiction.Plan, tableau et questions du jury →
- Existe-t-il des nombres qu'aucun programme ne pourra jamais calculer ?Les programmes sont des textes finis : on peut les numéroter 1, 2, 3… Cantor a montré qu'on ne peut pas numéroter les réels : avec un argument diagonal, on construit un réel différent de chacun. Il y a donc des réels qu'aucun programme ne calcule, et même « presque tous ».Plan, tableau et questions du jury →
- Combien de fonctions logiques différentes peut-on construire avec n entrées, et peut-on toutes les réaliser avec ET, OU, NON ?Une table de vérité à n entrées a 2ⁿ lignes, et chaque ligne vaut 0 ou 1 : il y a 2^(2ⁿ) fonctions. 16 pour 2 entrées, 256 pour 3, plus de 10¹⁹ pour 6. Toutes s'écrivent pourtant avec ET, OU et NON, en réunissant les lignes où la fonction vaut 1.Plan, tableau et questions du jury →
- Pourquoi « non (a et b) » ne veut-il pas dire « non a et non b », et pourquoi cette erreur cause-t-elle tant de bugs ?Les lois de De Morgan affirment que non (a et b) = (non a) ou (non b), et non (a ou b) = (non a) et (non b). Une table de vérité à 4 lignes le démontre. Mal nier une condition, comme « tant que non (trouvé ou fin) », produit des boucles infinies ou des tests faux.Plan, tableau et questions du jury →
- Comment démontrer qu'un algorithme avec une boucle donne toujours le bon résultat ?Pour la division de a par b par soustractions successives, la propriété a = bq + r reste vraie à chaque tour : c'est un invariant. À la sortie, r < b, donc q et r sont le quotient et le reste. Une récurrence sur le nombre de tours le prouve, et la décroissance de r prouve que la boucle s'arrête.Plan, tableau et questions du jury →
- Comment une question aussi simple que « combien de temps peut tourner un petit programme ? » peut-elle être impossible à résoudre ?Parmi les machines de Turing à n états qui finissent par s'arrêter, combien d'étapes au maximum ? Les valeurs sont 1, 6, 21, 107, puis 47 176 870 pour n = 5, démontré en 2024. Cette fonction croît plus vite que toute fonction calculable : aucun programme ne peut la calculer pour tout n.Plan, tableau et questions du jury →
- Pourquoi est-il facile de vérifier une grille de sudoku remplie, mais difficile de la remplir ?Vérifier une grille de sudoku demande 243 contrôles simples. La remplir peut demander d'explorer un nombre énorme de possibilités : il existe environ 6,67 × 10²¹ grilles complètes. La question « P = NP ? » demande si tout problème facile à vérifier est aussi facile à résoudre. Elle est ouverte et dotée d'un million de dollars.Plan, tableau et questions du jury →
- Si un ordinateur vérifie une propriété pour des milliards de nombres, est-elle pour autant démontrée ?n² + n + 41 est premier pour n de 0 à 39, mais 40² + 40 + 41 = 1 681 = 41². La conjecture de Pólya, vraie au début, tombe pour n = 906 150 257. La somme de quatre puissances cinquièmes égale à une cinquième puissance, jugée impossible par Euler, a été trouvée par ordinateur en 1966. Seule la démonstration couvre l'infini.Plan, tableau et questions du jury →
- Quel lien y a-t-il entre une requête de base de données et les opérations sur les ensembles ?Une condition WHERE avec AND correspond à une intersection, OR à une réunion, NOT au complémentaire. Pour compter les élèves inscrits en maths ou en NSI, |A ∪ B| = |A| + |B| − |A ∩ B| : 120 + 60 − 45 = 135. Une jointure part d'un produit cartésien de n × m lignes.Plan, tableau et questions du jury →
- Comment une fonction définie par trois lignes peut-elle produire des nombres de 20 000 chiffres ?La fonction d'Ackermann est définie par une récursion double. On démontre par récurrence que A(1, n) = n + 2, A(2, n) = 2n + 3 et A(3, n) = 2ⁿ⁺³ − 3. Puis A(4, 1) = 65 533 et A(4, 2) = 2⁶⁵ ⁵³⁶ − 3, un nombre de 19 729 chiffres. Elle est calculable, mais croît plus vite que toute fonction écrite avec de simples boucles « pour ».Plan, tableau et questions du jury →
Questions fréquentes
Qu'est-ce qu'une question transversale maths et nsi ?
Une question qui s'appuie sur les deux spécialités à la fois : les mathématiques y fournissent l'outil (une fonction, une suite, une probabilité) et la NSI le contexte et le sens. Le texte officiel autorise deux questions transversales, ou une question transversale et une question propre à une spécialité.
Qui sera dans mon jury ?
Deux professeurs de disciplines différentes, dont l'un représente une de vos deux spécialités. Le jury choisit l'une de vos deux questions, en fonction des spécialités de ses membres. Pour une question maths et nsi, préparez-vous à être interrogé par un professeur de maths comme par un professeur de NSI : chaque fiche prévoit des questions des deux côtés.
Puis-je reprendre une de ces questions telle quelle ?
Vous pouvez vous en inspirer et même garder la formulation : le jury n'évalue ni la formulation ni la pertinence de la question. En revanche, la question doit avoir été préparée avec vos professeurs, qui signent la feuille remise au jury, et l'introduction doit raconter votre propre parcours. Une présentation récitée se repère tout de suite pendant l'échange.
Combien de temps dure l'exposé en 2027 ?
10 minutes, debout, après 20 minutes de préparation, puis 10 minutes d'échange avec le jury. Chaque plan de cette page est minuté pour tenir dans les 10 minutes. Aucun matériel n'est autorisé hormis de quoi écrire : pas de calculatrice.
Les 100 questions couvrent-elles tout le programme ?
Elles couvrent les grands enjeux du cycle terminal (première et terminale) des deux spécialités, thème par thème. Pendant l'échange, le jury peut vous interroger sur toute partie du programme de vos spécialités en lien avec la question : révisez les notions citées dans chaque fiche.