Leçons Interactives de Mathématiques et Sciences

Informatique

Un ordinateur fait exactement ce qu'on lui a dit, assez vite pour rendre impossible d'ignorer l'écart entre un bon et un mauvais algorithme. Ici, les deux tournent et vous regardez l'écart se creuser.

Newest in this category

Chapitres

De courtes séquences plutôt que des outils isolés. Chaque étape transmet à la suivante quelque chose de précis : l’ordre a donc son importance.

L1 : bases

Comment un ordinateur exécute un programme

COMPDe la porte logique au programme en cours d’exécution. La porte NAND suffit à construire tous les circuits. Un additionneur composé de portes logiques sait aussi soustraire. Le Little Man Computer associe cet additionneur à cent boîtes aux lettres : le programme occupe la même mémoire que ses nombres, et la machine exécute ce qu’elle trouve à l’adresse indiquée par son compteur ordinal.

  1. 01Portes logiques
  2. 02Arithmétique binaire
  3. 03Le Little Man Computer
  4. 04Mémoire et octets
  5. 05La pile d’appels
  6. 06Localité et cache

L1 : bases

Comment casser les chiffres

COMPChacun des chiffres étudiés ici dissimule les lettres, mais laisse transparaître autre chose. La substitution conserve le décompte des caractères, le chiffrement à mot-clé le range en colonnes, et le masque jetable réutilisé trahit les espaces. Seule une clé aléatoire aussi longue que le message ne laisse absolument rien filtrer. Reste la vraie difficulté : la faire parvenir au destinataire. Les deux dernières pages relèvent ce défi au grand jour.

  1. 01Chiffre de substitution
  2. 02Chiffre de Vigenère
  3. 03Masque jetable
  4. 04Diffie–Hellman
  5. 05RSA

L2 : lycée

Ce qu’une structure de données rend peu coûteux

COMPChaque structure répond vite à une question, mais cette efficacité a un prix ailleurs. Un filtre de Bloom ne conserve aucune clé et peut pourtant affirmer avec certitude qu’une clé est absente ; un arbre préfixe permet des recherches par préfixe qu’une table de hachage ne sait pas faire ; un tas connaît toujours sa plus petite clé, mais guère plus. La dernière page pose la question du choix de la page à retirer de la mémoire. Pour faire le meilleur choix, il faudrait connaître l’avenir.

  1. 01Filtre de Bloom
  2. 02Arbre préfixe
  3. 03Tas binaire
  4. 04Remplacement de pages

L3 : licence

Protéger un flux : révoquer un appareil, puis identifier lequel

COMPDeux moitiés d'un même problème, dans l'ordre où un studio les rencontre. D'abord, une clé a fuité et la licence doit continuer à fonctionner pour tous les autres. Vous découvrez que cette protection exige un en-tête qui ne croît absolument pas avec la taille du système. Vient ensuite la phase la plus ardue : savoir à qui appartenait la clé, à partir d'une copie que plusieurs abonnés ont fabriquée ensemble avec l'intention expresse de ne nommer personne.

  1. 01Révocation d'appareils
  2. 02Tatouage numérique

L3 : licence

La transformée de Fourier en pratique

COMPUn signal est une somme de vecteurs tournants, et toute méthode pratique pour les analyser entraîne un coût que la formule théorique passe sous silence. Une fenêtre finie étale un son pur qui ne s'y ajuste pas sur tous les canaux ; une fenêtre plus courte vous fait gagner du temps mais se paie en hauteur ; une moyenne constitue un filtre possédant sa propre forme. La dernière page vous explique pourquoi tout cela reste calculable.

  1. 01Transformée de Fourier discrète
  2. 02Spectrogramme
  3. 03Moyenne mobile comme filtre
  4. 04Transformée de Fourier rapide

L3 : licence

Pourquoi un algorithme est correct

COMPUn algorithme est correct pour une raison démontrable, et erroné pour une faille qu'un simple test saura révéler. Chaque page oppose une version valide à une implémentation fausse mais plausible : quatorze des seize manières d'écrire la recherche dichotomique échouent, l'algorithme glouton du rendu de monnaie se trompe sur les anciennes pièces britanniques mais jamais sur les centimes américains, Kruskal et Prim aboutissent au même résultat pour une raison précise, et un code conçu pour corriger un bit altéré aggrave la situation face à deux erreurs.

  1. 01Recherche dichotomique
  2. 02Rendu de monnaie
  3. 03Arbre couvrant minimal
  4. 04Code de Hamming

Problèmes entièrement résolus

Ce que vous découvrirez ici

Articles écrits à partir de ces outils

Tous les outils de cette section

Algorithms & Data Structures

Arbre couvrant minimal : Kruskal et Prim
Douze villages, 66 routes possibles. Kruskal et Prim en retiennent 11, dans des ordres différents, et aboutissent aux mêmes 199,04 km : chaque route choisie est la moins chère à travers une coupe. Passer toujours au village le plus proche coûte au contraire 10,76 % de plus. Pour trois villes distantes de 40 km, un carrefour intermédiaire permet d’économiser 13,40 %.
Chiffre de Vigenère : trouver la longueur de la clé, puis le casser
Chiffrez les premières lignes d'Alice au pays des merveilles avec un mot-clé, puis menez l'attaque vous-même : déterminez la longueur de la clé grâce à l'indice de coïncidence de chaque k-ième lettre, confirmez-la par le test de Kasiski sur les répétitions, puis déduisez chaque lettre de la clé à l'aide du khi-deux.
Chiffrement par substitution : 26! clés brisées par le décompte des lettres
Cassez vous-même un chiffrement de César et une substitution générale grâce au décompte des lettres. Dès 31 lettres, le test du χ² désigne le bon décalage dans 99,1 % des cas ; en revanche, classer les lettres par fréquence sur une nouvelle entière de 32 725 lettres laisse encore cinq des 26 lettres au mauvais rang.
Course d'algorithmes de tri
64 éléments inversés coûtent au tri à bulles exactement 2 016 échanges, un par inversion, et tout algorithme échangeant des voisins possède ce même plancher. Le tri rapide les résout en 32 échanges, déplaçant les éléments de 63 places.
Diffie–Hellman : un secret convenu en public
Alice et Bob s’accordent sur un secret à découvert, et vous voilà aux écoutes. Suivez la force brute puis l’algorithme de Pohlig–Hellman pas à pas, essai après essai, pour comprendre pourquoi le premier 1621 capitule en 21 essais au plus, quand 1619, qui lui est inférieur de deux, résiste pendant 811 essais.
Explorateur d'arbres de récursivité
Comptez les appels, les sous-problèmes distincts et la profondeur de la pile d'un arbre d'appels récursif naïf pour Fibonacci, les tours de Hanoï, la formule de Pascal, le tri fusion et la montée de marches. Vous verrez ainsi précisément où un tableau de mémoïsation s'avère payant.
Explorateur de coloration de graphes
Coloriez les sommets d'un graphe, testez les contraintes chromatiques et explorez les bornes inférieures par clique.
Explorateur de complexité Big-O
Visualise comment les taux de croissance O(1), O(log N), O(N), O(N²), O(2ᴺ) et O(N!) se comparent à différentes échelles.
Filtre de Bloom : absence certaine, présence probable
Insérez des mots un à un dans un filtre de Bloom, recherchez-en d'autres et comptez les faux positifs parmi 10 000 chaînes jamais insérées. Comparez l'estimation classique aux résultats du filtre, trouvez le nombre optimal de fonctions de hachage et découvrez pourquoi un filtre de Bloom simple ne permet pas de supprimer un mot.
Masque jetable : inviolable une fois, brisé à la seconde
Chiffrez un message avec une clé aléatoire d’égale longueur, puis saisissez n’importe quel autre texte de même taille pour découvrir la clé qui l’aurait produit. Réutilisez ensuite la clé pour un second message : elle s’annule d’elle-même, et faire glisser un mot probable sur les deux textes permet de les lire simultanément.
Plus court chemin de Dijkstra
Le nœud 1 est à une arête de la source pour un coût de 4, et sa distance la plus courte est 3 en passant par le nœud 3. Chargez le préréglage à arête négative et le nœud 3 se fixe à −1 tandis que la reconstruction de l'itinéraire signale une boucle.
Recherche dichotomique : quatre choix, seize boucles
Une boucle de recherche dichotomique repose sur quatre choix. Sur les 16 combinaisons possibles, seules 2 sont correctes. Construisez la boucle, observez-la sur un petit tableau, puis testez-la sur tous les tableaux comptant jusqu’à 256 éléments : dès deux éléments, toutes les boucles erronées ont déjà échoué.
Remplacement de pages : FIFO, LRU et la politique optimale
Parcourez une chaîne de références avec quelques cadres de mémoire, selon FIFO, LRU ou la politique optimale de Bélády, et comptez les défauts de page. Pour 1 2 3 4 1 2 5 1 2 3 4 5, FIFO provoque 9 défauts avec trois cadres et 10 avec quatre. Avec LRU et OPT, ajouter de la mémoire n’augmente jamais le nombre de défauts.
Rendu de monnaie : glouton ou optimal
Pour rendre 48d dans l’ancien système monétaire britannique, la méthode gloutonne donne une demi-couronne, un shilling et une pièce de six pence, alors que deux florins suffiraient. Comparez-la à l’optimum obtenu par programmation dynamique pour n’importe quel système de pièces, observez le tableau se remplir case par case et découvrez la borne qui ramène la vérification d’un système à un calcul fini.
Tas binaire : une file de priorité dans un tableau
Pour 15 clés présentées par ordre décroissant, la construction demande 34 comparaisons par insertions successives, contre 22 en partant du dernier parent. Avec 1 023 clés, ces nombres passent à 8 194 et 2 026. Suivez chaque comparaison et chaque échange, avec l’arbre et le tableau côte à côte, puis extrayez les clés par ordre croissant.
Trie : l’arbre préfixe, pas à pas
Stockez des mots dans un trie et suivez pas à pas une recherche, une autocomplétion et une insertion. Comparez, lettre par lettre, le travail du trie, d’une recherche dichotomique et d’une table de hachage. Comptez aussi les octets : même en partageant 40 lettres sur 70, le trie occupe encore 2,6 fois la place d’une simple liste.
Visualiseur BFS vs DFS
Le nœud 15 se trouve à 6 arêtes du départ ; le parcours en profondeur peut vous fournir un chemin de 12 arêtes pour l'atteindre. La composante contient 15 nœuds sur 16 arêtes, donc 2 arêtes excédentaires causent tous les désaccords qu'ont les deux panneaux.
Visualiseur d'algorithmes de recherche de chemin
Observez A*, Dijkstra, Greedy Best-First et BFS parcourir une grille, étape par étape.
Visualiseur d'arbres BST / AVL
Insérez 10, 20, 30, 40, 50, 60, 70 dans cet ordre et l'arbre est une chaîne de hauteur 7, sept comparaisons pour trouver la dernière clé là où trois suffiraient. Les rotations AVL placent ces mêmes sept clés à une hauteur de 3.
Visualiseur de distance de Levenshtein
Calculez la distance d'édition (insertions, suppressions, substitutions) entre deux chaînes et visualisez la comparaison.
Visualiseur de table de hachage
Découvrez comment les tables de hachage stockent les données avec résolution de collisions par chaînage, sondage linéaire et sondage quadratique.

Information Theory & Encoding

Aire de jeu du codage entropique
Relie les distributions de symboles à l'entropie de Shannon, au gain de compression attendu et à la prédiction du prochain token dans l'IA/les LLM.
Arithmétique binaire et complément à deux
100 + 50 sur huit bits donne un octet valant 150 en non signé et −106 en signé, donc la retenue signale que tout va bien et le débordement signale une erreur. Additionnez 200 + 100 et les drapeaux s'inversent, c'est pourquoi un additionneur a besoin des deux.
Codage par plages (RLE)
Compresse les symboles répétés en paires valeur-nombre et examine les meilleurs et pires cas.
Démo du compresseur LZ77
Parcours pas à pas les références arrière à fenêtre glissante utilisées par DEFLATE, ZIP et gzip.
Détecteur/convertisseur d'encodage et de base
Détecte l'encodage ou le format structuré probable, puis décode et explique de quoi il s'agit vraisemblablement.
Laboratoire d'entropie en TAL
Entropie des jetons, entropie croisée, perplexité et divergence KL : les quatre grandeurs qui servent à entraîner et à évaluer un modèle de langage.
Transformée de Burrows-Wheeler (BWT)
Découvrez comment la BWT réorganise le texte en séquences répétées qui se compressent mieux, et comment l'inverser sans perte.
Virgule flottante
Saisissez un nombre décimal et observez l'ordinateur le convertir : signe, binaire, normalisation, décalage, arrondi. Vous verrez la valeur finalement conservée, l'erreur et la distance jusqu'au prochain nombre qu'il peut représenter.
Visualiseur de codage Huffman
L'encodage de hello world réduit 88 bits à 32 face à un plancher d'entropie de 31,3, ce 0,7 venant des longueurs de code arrondies aux bits entiers. Une source 90/10 porte 0,469 bit par symbole et Huffman en dépense toujours 1.

Signal & Media Processing

Aire de jeu convolution et cartes de caractéristiques
Quatorze couches 3×3 empilées permettent à un pixel de sortie de voir toute l'image 28×28, pour 126 multiplications-accumulations. Un noyau 29×29 de même portée en coûte 841, voilà pourquoi les réseaux de vision sont longs et étroits.
Détecteur de contours Sobel vs Canny
Applique les gradients de Sobel et l'hystérésis de Canny pour comparer les pipelines de détection de contours.
La transformée de Fourier rapide
La transformée de Fourier rapide calcule les mêmes N valeurs que la somme directe avec environ N log N multiplications au lieu de N². Suivez ses calculs en papillon, reprenez l'exemple à douze points que Gauss a laissé dans un manuscrit inédit vers 1805, et chronométrez les deux méthodes dans votre navigateur.
Laboratoire d'échantillonnage de pixels
Comprends l'échantillonnage, Nyquist et le repliement (aliasing) grâce à des visualisations de signal et de grille de pixels.
Laboratoire d'encodage vidéo
Découvrez le débit binaire, le codec, le CRF/CBR et les compromis de qualité grâce à des estimations visuelles en direct.
Laboratoire de quantification
La quantification sur huit bits affiche ici 56,18 dB là où la formule classique 6,02N + 1,76 donne 49,92. L'écart de 6,2 dB vient du facteur de crête : cette règle suppose un sinus pleine échelle, et cette rampe a plus de deux fois sa valeur efficace.
Laboratoire de sous-échantillonnage de la chrominance
Compare 4:4:4, 4:2:2 et 4:2:0 pour observer la perte de détail colorimétrique dans la compression d'image et de vidéo.
Simulateur d'estimation de mouvement
225 positions de recherche par bloc correspondent à une fenêtre 15×15, de −7 à +7 pixels, et le coût est quadratique selon le rayon : 961 à 15, 3 969 à 31. Une recherche en trois étapes en vérifie 27 à la place et accepte un vecteur de moindre qualité.
Simulateur de contrôle de débit
Le CRF et le CBR dépensent ici les mêmes 2 000 bits par image, et le CRF obtient tout de même un score de 89,8 contre 79. Ces 10,8 points achètent une crête plate : la plus grande image du CBR fait 2 000 bits là où celle du CRF en fait 4 078.
Spectrogramme
Un spectrogramme fait glisser une transformée de Fourier à court terme le long d'un morceau de musique, et la longueur de la fenêtre détermine ce qu'il peut révéler. Distinguer le La4 du La♯4 demande 72,0 ms avec une fenêtre de Hann. Un demi-ton au La1, à 55 Hz, exige 576,2 ms, soit plus de quatre doubles croches. Un trille de basse rapide indique donc quelle note est jouée dans moins d'un quart des tranches, pour toute fenêtre allant jusqu'à une seconde.
Transformée de Fourier discrète
Échantillonnez un son pur 64 fois et calculez sa transformée de Fourier discrète : à exactement 10 cycles, c'est une seule barre nette ; à 10,5, le son illumine chaque barre et la plus haute atteint 64,61 % de son amplitude. Chaque barre est dessinée comme la somme de 64 flèches, avec une fenêtre pour échanger l'étalement contre un pic plus large.
Vérificateur de contraste des couleurs (luminance WCAG)
Vérifiez le contraste entre la couleur du texte et celle de l'arrière-plan par rapport aux seuils d'accessibilité WCAG 2 — et découvrez comment la formule de luminance qui les sous-tend descend du besoin de la télévision couleur de 1953 de faire tenir la couleur dans un signal noir et blanc existant.
Visualisateur de structure GOP
Comprenez les structures d'images I/P/B, la latence de recherche et les compromis de compression dans les flux vidéo.

Automata & Cryptography

Animateur d'automate fini
Parcourez les transitions d'un AFD sur un diagramme d'états en direct — observez quel état est actif après chaque symbole et si l'entrée est acceptée.
Explorateur de portes logiques
Visualiseur interactif de portes logiques et petits circuits avec impulsions, chronogrammes et tables de vérité compactes.
La pile d’appels : cadres, adresses de retour et débordements
Observez les écritures en mémoire que provoque chaque appel de fonction : un argument, une adresse de retour et un pointeur de cadre sauvegardé sont empilés dans une pile de 128 octets. À chaque retour, l’exécution reprend à l’adresse contenue dans l’emplacement prévu à cet effet. Explorez la récursivité, le débordement de pile, un tableau qui écrase sa propre adresse de retour et une variable qui conserve la valeur laissée par l’appel précédent.
Le filigrane qui survit à une collusion
Chaque copie porte une chaîne de bits unique, ce qui permet à une fuite d'identifier l'abonné. Quatre d'entre eux peuvent comparer leurs copies pour en forger une qui n'accuse personne, à moins que la chaîne ne compte 2 490 bits, et il en faut 39 833 pour seize d'entre eux.
Localité mémoire : pourquoi l’ordre de lecture compte
Calculez la somme des éléments d’une même matrice par lignes, puis par colonnes, avec un petit cache à correspondance directe. Comptez chaque succès et chaque défaut de cache. Les mêmes additions aux mêmes adresses donnent 48 succès sur 64 dans un ordre, aucun dans l’autre. Quatre entiers inutilisés par ligne suffisent à mettre les deux parcours à égalité.
Mémoire et octets : boutisme, types et adresses
Trente-deux octets en mémoire, sans indication de ce qu'ils représentent. Lisez-les comme un entier sur 8, 16 ou 32 bits, un nombre à virgule flottante ou du texte, en ordre petit-boutiste ou grand-boutiste. Le poids de chaque octet s'affiche juste en dessous. Dans le mauvais ordre, 1 devient 16 777 216 ; les octets du nombre flottant π, lus comme un entier, donnent 1 078 530 011.
Révoquer un appareil sans avertir les autres
Soixante-quatre appareils compromis sur un million exigent un en-tête de licence de 846 clés, ou de 77, ou de 3. Le nombre exact dépend du schéma, ainsi que de l'appartenance de ces soixante-quatre appareils à un même lot.
RSA : chiffrement jouet
p = 61 et q = 53 donnent n = 3233, que seize essais de division brisent. Fuiter φ = 3120 le brise tout aussi complètement : p + q = 114 et pq = 3233 est une équation du second degré qui vous rend les deux nombres premiers.
Simulateur de machine de Turing
Un palindrome de 5 cellules coûte 21 mouvements et un de 21 cellules en coûte 253, car une tête doit parcourir toute la bande pour chaque paire. Une deuxième bande rend le travail linéaire, et Hennie a prouvé en 1965 qu'une seule bande ne le peut pas.
Solveur d'expressions booléennes
Saisissez des expressions logiques booléennes et générez une table de vérité complète avec des colonnes de sous-expressions intermédiaires.
Un processeur miniature : le Little Man Computer
Faites avancer le Little Man Computer transfert par transfert et suivez chaque lecture et chaque écriture en mémoire : PC, MAR, MDR, CIR, accumulateur, cent cases mémoire et des programmes que vous pouvez modifier. Le simulateur mesure la part des accès mémoire consacrée à la lecture des instructions du programme.

Demos & Utilities

Algorithme de recherche de Grover
Parcourez l'algorithme de Grover itération par itération. Observez l'amplitude cible croître — O(√N) vs O(N).
Explorateur de fractales
La dimension de Koch est log 4 / log 3 = 1,262 et celle de l'ensemble de Cantor est 0,631, moins qu'une ligne. Trois des huit courbes ici donnent exactement 2, et à une profondeur infinie, celles-ci remplissent le plan au lieu de le traverser.
Explorateur de la sphère de Bloch
Un qubit à θ = 90° donne 50/50 dans la base Z et 100/0 dans X, donc 50/50 est un fait concernant la base que vous avez choisie. Faites-lui faire une rotation complète de 360° et l'état bascule à −|ψ⟩ ; seul un second tour le restaure.
Extracteur de ressources HTML, images et Markdown
Collez du HTML et extrayez les fichiers liés par catégorie, avec une galerie centrée sur les images et un export du texte en Markdown.
Jeu de la vie de Conway
Le planeur se déplace à c/4, et la limite est la règle elle-même : une cellule voit huit voisines, donc rien ne va plus vite qu'une cellule par génération. Le diehard semble vigoureux jusqu'à ce qu'il disparaisse à la génération 130.
Laboratoire générateur de Lorem Ipsum
Le curseur d'entropie est un réglage de température de LLM, et il possède un plafond : le corpus contient 63 mots distincts, donc log₂ 63 = 5,9773 bits est le maximum qu'un passage puisse porter, quelle que soit la cible que vous demandiez.
Marche aléatoire quantique
Après 100 pas, un marcheur classique dépasse rarement 10 sites d'écart et un marcheur quantique en atteint environ 70. À 10 pas, les dispersions sont de 4,8924 contre 3,1623, le marcheur classique a donc besoin de 24 pas pour l'égaler.

Autres outils

Calculateur débit / taille
Un mégabit par seconde supplémentaire coûte 450 MB par heure, peu importe ce que contient l'image. Sur un extrait de dix minutes à 6 Mbit/s, l'audio représente 3,1 % d'un fichier de 478 MB, donc le réduire de moitié économise 7 MB et pénalise chaque auditeur.
Chiffrer un bloc sur dix (CENC cbcs)
Le schéma cbcs chiffre un bloc de 16 octets sur dix, et le tiers d'une tranche de 48 octets en ressort chiffré. Les neuf dixièmes en clair ne servent à rien sans la clé, car dans toute tranche atteinte par le motif, le premier octet qui suit l'en-tête est chiffré.
Code de Hamming : corriger un bit en repérant sa position
Quatre bits de données sur sept, et trois contrôles de parité dont les échecs écrivent en binaire la position du bit erroné : toute inversion unique est ainsi corrigée. Avec deux inversions, le décodeur en inverse une troisième en toute confiance ; un bit de plus permet de les signaler.
Explorateur de tokenisation BPE
Découvrez comment le codage par paires d'octets découpe le texte en tokens, ce qu'un modèle de langue lit réellement. Vocabulaire fixe, découpage en direct : l'anglais coûte 13 tokens là où la même phrase en allemand en coûte 36.
Résolution d'écran et distance de recul
La part de la résolution d'un écran qui atteint réellement votre œil, selon sa diagonale, son nombre de pixels et l'endroit où vous vous asseyez. Avec une acuité visuelle de 20/20, la réponse correspond au champ de vision mesuré en minutes d'arc, et sur un téléviseur de salon, elle tombe généralement sous le 1080p.
Rotation des clés d'un flux en direct
Une rotation des clés toutes les deux minutes pendant un an génère 262 800 clés de contenu, soit 4,20 Mo. Le véritable coût, ce sont un million de lecteurs qui réclament chaque nouvelle clé dans la même fenêtre de dix secondes. La hiérarchie de clés divise cette demande par 720, mais rend chaque fuite 720 fois plus importante.
Température et échantillonnage
Regardez une vraie distribution du token suivant se faire remodeler par la température puis tronquer par top-k et top-p. La température ne change jamais quel token mène — seulement de combien, de 278x à 1,76x.
Vecteurs de tokens et similarité
Des vecteurs construits en comptant quels tokens apparaissent près de quels autres, sur la prose de ce site. La paire la plus haute est ␣the et ␣is à 0,505 — plus que ␣Earth et ␣Sun à 0,299, et elle ne signifie rien.
Related categories: Mathématiques, Physique