Arvutid ja algoritmid
L1: alused
COMPLoogikaelemendist töötava programmini. NAND-elemendist piisab mis tahes loogikaskeemi ehitamiseks. Loogikaelementidest koostatud summaator oskab ka lahutada. Little Man Computer paigutab selle summaatori kõrvale sada postkasti: programm asub samas mälus kui arvud. Arvuti täidab seda, millele käsuloendur parasjagu osutab.
L2: kool
COMPIga siinne andmestruktuur vastab ühele küsimusele kiiresti, kuid maksab selle eest mujal lõivu. Bloomi filter ei säilita ühtegi võtit, ent suudab siiski öelda kindlasti mitte. Prefiksipuu vastab prefiksite kohta küsimustele, millele paisktabel vastata ei oska; kuhi teab alati oma vähimat võtit ja suurt muud ei teagi. Viimasel lehel tuleb otsustada, milline lehekülg mälust välja heita. Parima valiku tegemiseks oleks vaja teada tulevikku.
L3: ülikool
COMPStopper mõõdab sinu sülearvutit. Tehete loendamine mõõdab algoritmi. Kaks tööriista, mis tuginevad sellele ühele harjumusele.
L3: ülikool
COMPAlgoritm on õige kindlal, selgelt sõnastataval põhjusel. Vale algoritmi reedab aga viga, mille leiab üles juba lihtne test. Igal lehel on siin kõrvutatud õige ja esmapilgul usutav vigane lahendus: kuueteistkümnest binaarotsingu koodist neliteist ebaõnnestuvad. Ahne algoritm annab vanade Briti müntidega raha tagasi valesti, kuid USA sentidega ei eksi see kunagi. Kruskal ja Prim jõuavad samale tulemusele täiesti põhjendatult. Üht muundunud bitti parandav kood teeb aga kahe vea korral olukorra hoopis hullemaks.
Turve
L1: alused
COMPIga siinne šiffer peidab tähed, kuid jätab midagi muud nähtavale. Asendus jätab alles tähesagedused, märksõnašiffer seab need tulpadesse ning kahel korral kasutatud ühekordne võti paljastab tühikud. Üksnes sõnumipikkune juhuslik võti ei reeda vähimatki. Siis aga muutub keeruliseks selle võtme teisele poole toimetamine – kaks viimast lehekülge teevad seda kõigi silme all.
L3: ülikool
COMPSama probleemi kaks poolt, täpselt selles järjekorras, kuidas stuudio nendega silmitsi seisab. Kõigepealt olukord, kus võti on lekkinud ja litsents peab kõigi teiste jaoks edasi toimima. Selgub, et selle saavutamiseks vajalik päis ei kasva süsteemi suurenedes vähimalgi määral. Seejärel tuleb raskem pool: teada saada, kelle võti see oli, uurides koopiat, mille mitu tellijat panid kokku spetsiaalselt eesmärgiga mitte kedagi reeta.
Signaalid ja informatsioon
L2: kool
COMPVideokodeerija ei ole üks algoritm, vaid kaheksa astet kindlas järjekorras — ja järjekord ei ole suvaline: iga aste on olemas seetõttu, et eelmine tegi tema töö võimalikuks. See tööriist modelleerib neist üht. Allolev ahel viitab ülejäänud seitsmele.
L3: ülikool
COMPKaks tööriista, mis avavad suure keelemudeli just sõna valimise hetkel. Teine töötab sõna otseses mõttes esimese peal: selle järjestatavad kandidaadid on kirjed sõnavarast, mille esimene üles ehitab.
L3: ülikool
COMPSignaal on pöörlevate noolte summa, ent iga reaalne katse neid lugeda nõuab lõivu, millest õpikuvalem vaikib. Lõplik aken hajutab sinna mittemahtuva tooni laiali üle kõikide sageduslahtrite. Lühem aken võidab ajas, kuid kaotab helikõrguses. Keskmistamine toimib täiesti iseloomuliku kujuga filtrina ning viimane lehekülg näitab, miks kogu see arvutus meile üldse jõukohane on.
L3: ülikool
COMPNeli koodrit, mida võiksid paberil läbi teha, järjestatud selle järgi, mida märkab iga järgmine, mis eelmisel märkamata jäi. Neljas ei tihenda absoluutselt midagi. Ja just see on põhjus, miks esimene tekstiga töötab.
Tõestamine, loendamine ja mängud
L2: kool
MATHSünnipäevaprobleem näib seltskonnatrikina, kuid on tegelikult standardne vahend kollisioonide analüüsimiseks. Teises sammus kohtavad arvutiteadlased seda uuesti, teise nime all.
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.
