Rechner und Algorithmen
L1: Grundlagen
COMPVom Logikgatter zum laufenden Programm. Mit NAND-Gattern lässt sich jede logische Schaltung bauen. Ein Addierwerk aus Gattern kann auch subtrahieren. Im Little Man Computer steht dieses Addierwerk neben hundert Postfächern: Das Programm liegt im selben Speicher wie seine Zahlen. Die Maschine führt aus, was an der Adresse steht, auf die der Programmzähler zeigt.
L2: Schule
COMPJede dieser Strukturen beantwortet eine bestimmte Frage schnell und nimmt dafür an anderer Stelle Nachteile in Kauf. Ein Bloom-Filter speichert keinen einzigen Schlüssel und kann trotzdem sicher ausschließen, dass ein Element enthalten ist; ein Trie ermöglicht Präfixsuchen, die eine Hashtabelle nicht bietet; ein Heap kennt stets seinen kleinsten Schlüssel, aber sonst nur wenig. Auf der letzten Seite geht es darum, welche Seite aus dem Speicher entfernt werden soll. Für die beste Entscheidung müsste man die Zukunft kennen.
L3: Grundstudium
COMPEine Stoppuhr misst deinen Laptop. Das Zählen von Rechenschritten misst den Algorithmus. Zwei Werkzeuge, die auf dieser einen Gewohnheit aufbauen.
L3: Grundstudium
COMPDass ein Algorithmus korrekt ist, hat einen klaren Grund, den du benennen kannst. Ist er falsch, deckt schon ein kleiner Test die Ursache auf. Jede Seite stellt einer korrekten Version eine plausibel wirkende, aber fehlerhafte gegenüber: Vierzehn der sechzehn Wege, eine binäre Suche zu schreiben, schlagen fehl. Der Greedy-Algorithmus beim Geldwechseln scheitert an alten britischen Münzen, funktioniert bei US-Cents aber ausnahmslos. Kruskal und Prim liefern aus einem ganz bestimmten Grund das gleiche Ergebnis. Und ein Code, der ein einziges gekipptes Bit repariert, macht bei zwei gekippten Bits alles nur noch schlimmer.
Sicherheit
L1: Grundlagen
COMPJede Chiffre hier verbirgt die Buchstaben, lässt dafür aber etwas anderes durchscheinen. Eine Substitution verrät die Häufigkeiten der Buchstaben. Ein Schlüsselwort ordnet sie in Spalten an. Und wird ein One-Time-Pad zweimal verwendet, treten die Leerzeichen hervor. Erst ein Zufallsschlüssel, der genauso lang ist wie die Nachricht selbst, gibt überhaupt nichts mehr preis. Dann aber beginnt die eigentliche Kunst: Wie gelangt dieser Schlüssel zur Gegenseite? Genau das zeigen die beiden letzten Seiten vor aller Augen.
L3: Grundstudium
COMPZwei Hälften desselben Problems, genau in der Reihenfolge, in der ein Studio damit konfrontiert wird. Zuerst: Ein Schlüssel wurde geleakt, und die Lizenz muss für alle anderen weiterhin funktionieren. Das erfordert überraschenderweise einen Header, der gar nicht mit der Größe des Systems wächst. Dann die schwierigere Hälfte: herauszufinden, wessen Schlüssel das war. Und zwar anhand einer Kopie, die mehrere Abonnenten gezielt gemeinsam erstellt haben, damit sie genau niemanden verrät.
Signale und Information
L2: Schule
COMPEin Video-Encoder ist kein einzelner Algorithmus, sondern acht Stufen in fester Reihenfolge — und die Reihenfolge ist nicht beliebig: Jede Stufe existiert, weil die vorherige ihre Arbeit erst möglich gemacht hat. Dieses Werkzeug modelliert eine davon. Die Kette unten verlinkt die anderen sieben.
L3: Grundstudium
COMPZwei Werkzeuge, die dir ein großes Sprachmodell genau in dem Moment öffnen, in dem es ein Wort wählt. Das zweite baut buchstäblich auf dem ersten auf: Die Kandidaten, die es bewertet, sind Einträge aus dem Vokabular, das das erste erstellt.
L3: Grundstudium
COMPEin Signal ist die Summe rotierender Pfeile, und jede praktische Methode, sie auszulesen, kostet etwas, das die Lehrbuchformel verschweigt. Ein endliches Fenster verschmiert jeden Ton, der nicht genau hineinpasst, über alle Bins. Ein kürzeres Fenster erkauft sich Zeit und bezahlt mit der Tonhöhe. Ein Mittelwert ist ein Filter mit ganz eigener Form, und die letzte Seite liefert den Grund, warum wir uns all das rechnerisch überhaupt leisten können.
L3: Grundstudium
COMPVier Encoder, die du auf Papier durchrechnen könntest, geordnet danach, was jeder von ihnen erkennt, das dem Vorgänger entging. Der vierte komprimiert rein gar nichts und ist der Grund dafür, dass der erste mit Text funktioniert.
Beweisen, Abzählen, Spiele
L2: Schule
MATHDas Geburtstagsproblem wirkt wie ein Partytrick, ist aber in Wahrheit das Standardwerkzeug zur Analyse von Kollisionen. Im zweiten Schritt begegnen Informatiker ihm erneut, unter einem anderen Namen.
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.
