Máquinas e algoritmos
L1: fundamentos
COMPDe uma porta lógica a um programa em execução. Só com portas NAND podemos construir qualquer circuito. Um somador construído com portas lógicas também faz subtrações. No Little Man Computer, esse somador trabalha com uma centena de caixas de correio: o programa ocupa a mesma memória que os números, e a máquina executa o que encontrar no endereço indicado pelo contador de programa.
L2: escola
COMPCada estrutura responde depressa a uma pergunta, mas paga por isso noutro ponto. Um filtro de Bloom não guarda nenhuma chave e ainda assim consegue dizer de certeza que não. Uma árvore de prefixos responde a perguntas sobre prefixos que uma tabela de dispersão não consegue resolver; um amontoado sabe sempre qual é a sua menor chave e pouco mais. Na última página, é preciso decidir que página retirar da memória. A melhor escolha exige conhecer o futuro.
L3: universidade
COMPUm cronômetro mede o seu computador. Contar operações mede o algoritmo. Duas ferramentas nascidas desse único hábito.
L3: universidade
COMPUm algoritmo está correto por uma razão que se pode enunciar, e incorreto por uma falha que um pequeno teste revela. Cada página confronta uma versão correta com uma alternativa plausível mas errada: catorze das dezasseis formas de programar uma busca binária falham. O algoritmo guloso para o troco perde nas antigas moedas britânicas. Nunca falha com os cêntimos americanos. Kruskal e Prim concordam por um motivo claro. E um código concebido para corrigir um bit invertido torna duas inversões ainda piores.
Segurança
L1: fundamentos
COMPCada cifra aqui esconde as letras e deixa outra coisa à vista. A substituição preserva a contagem das letras, a cifra com palavra-chave organiza-as em colunas e o bloco de uso único usado duas vezes expõe os espaços. Só uma chave aleatória tão longa quanto a mensagem não revela rigorosamente nada. O difícil é fazer chegar essa chave ao outro lado, proeza que as duas últimas páginas realizam em público.
L3: universidade
COMPDuas metades do mesmo problema, na ordem em que um estúdio se depara com elas. Primeiro, uma chave foi exposta e a licença tem de continuar a funcionar para todos os outros, o que acaba por custar um cabeçalho que não cresce de todo com a dimensão do sistema. Depois vem a parte mais complexa: saber de quem era a chave a partir de uma cópia que vários subscritores construíram em conjunto com o propósito expresso de não identificar ninguém.
Sinais e informação
L2: escola
COMPUm codificador de vídeo não é um algoritmo, mas oito etapas numa ordem fixa, e a ordem não é arbitrária: cada etapa existe porque a anterior tornou o seu trabalho possível. Esta ferramenta modela uma delas. A cadeia abaixo liga às outras sete.
L3: universidade
COMPDuas ferramentas que desvendam um grande modelo de linguagem no instante em que ele escolhe uma palavra. A segunda opera literalmente sobre a primeira: os candidatos que ela classifica são entradas do vocabulário que a primeira constrói.
L3: universidade
COMPUm sinal é uma soma de setas giratórias. Na prática, qualquer interpretação acarreta custos que as fórmulas dos manuais omitem. Uma janela finita dispersa por todas as bandas os tons que nela não couberem. Janelas curtas compram tempo. Pagam em afinação. Uma média também atua como um filtro com forma própria. A última página explica a lógica que permite calcular tudo isto atempadamente.
L3: universidade
COMPQuatro codificadores que poderia fazer no papel, ordenados por aquilo que cada um consegue ver e que o anterior não conseguia. O quarto não comprime absolutamente nada, e é a razão pela qual o primeiro funciona com texto.
Demonstração, contagem e jogos
L2: escola
MATHO problema do aniversário parece um truque de salão, mas é, na verdade, a ferramenta padrão para analisar colisões. É na segunda etapa que os cientistas da computação o reencontram, sob um nome diferente.
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.
