Machines et algorithmes
L1 : bases
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.
L2 : lycée
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.
L3 : licence
COMPUn chronomètre mesure votre ordinateur. Compter les opérations mesure l'algorithme. Deux outils bâtis sur cette unique habitude.
L3 : licence
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.
Sécurité
L1 : bases
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.
L3 : licence
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.
Signaux et information
L2 : lycée
COMPUn encodeur vidéo n'est pas un algorithme mais huit étapes dans un ordre fixe, et cet ordre n'est pas arbitraire : chaque étape existe parce que la précédente a rendu son travail possible. Cet outil modélise l'une d'elles. La chaîne ci-dessous renvoie aux sept autres.
L3 : licence
COMPDeux outils qui vous dévoilent un grand modèle de langage au moment où il choisit un mot. Le second s'exécute littéralement sur le premier : les candidats qu'il classe sont des entrées du vocabulaire que le premier construit.
L3 : licence
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.
L3 : licence
COMPQuatre encodeurs que vous pourriez exécuter sur papier, classés selon ce que chacun perçoit et qui échappait au précédent. Le quatrième ne compresse absolument rien, et c'est la raison pour laquelle le premier fonctionne sur du texte.
Preuve, dénombrement et jeux
L2 : lycée
MATHLe paradoxe des anniversaires ressemble à un tour de magie, mais il constitue en réalité l'outil de référence pour l'étude des collisions. C'est à la deuxième étape que les informaticiens le retrouvent, sous un autre nom.
Switching off a thousand devices can cost less than switching off one
A disc cannot ask who is playing it, so a revocation has to be broadcast to everybody at once. The scheme every Blu-ray uses prices that broadcast by how the broken devices are arranged in the key tree, and the size of the audience does not appear in the bound at all.
Half of written Japanese is 158 characters. The next 45% costs a thousand more.
Word frequencies follow the same lopsided law in every language anyone has checked. It makes the first stage of learning feel miraculous and the last stage feel impossible, and both feelings are the same curve.
Why sorting cannot get faster
Sorting a hundred items takes at least 525 comparisons and no future algorithm will improve on it. The proof does not examine any algorithm at all: it counts how many arrangements exist and how much a yes-or-no question can possibly tell you.
Why a language model struggles to count the letters in a word
It never sees the letters. Text is split into tokens before the model reads anything, and a great many puzzling failures follow directly from where the splits land.
No compressor can shrink every file, and the proof takes one paragraph
Lossless compression works by exploiting predictability, so a file with none of it cannot be made smaller at all. The proof is counting: nine things will not fit into eight boxes.
