Máquinas y algoritmos
L1: fundamentos
COMPDe una puerta lógica a un programa en marcha. Con puertas NAND puedes construir cualquier circuito. Un sumador hecho de puertas también permite restar. El Little Man Computer reúne ese sumador y cien buzones: el programa ocupa la misma memoria que los números con los que trabaja. La máquina ejecuta lo que encuentre en la dirección que indica su contador de programa.
L2: escuela
COMPCada estructura responde con rapidez a una pregunta concreta y lo paga en otra parte. Un filtro de Bloom no guarda ninguna clave y aun así puede decir seguro que no; un árbol de prefijos resuelve consultas por prefijo que una tabla de dispersión no puede resolver; un montículo siempre sabe cuál es su clave mínima y poco más. La última página plantea qué página expulsar de la memoria. Para elegir la mejor habría que conocer el futuro.
L3: universidad
COMPUn cronómetro mide tu portátil. Contar operaciones mide el algoritmo. Dos herramientas basadas en ese único hábito.
L3: universidad
COMPUn algoritmo es correcto por una razón que se puede enunciar, y falla por un error que una pequeña prueba puede descubrir. Cada página sitúa una versión correcta junto a una errónea pero verosímil: catorce de las dieciséis formas de escribir la búsqueda binaria fallan, el algoritmo voraz para dar cambio se equivoca con las antiguas monedas británicas y jamás con los centavos de Estados Unidos, Kruskal y Prim coinciden por un motivo lógico, y un código que corrige un bit invertido agrava el problema si se invierten dos.
Seguridad
L1: fundamentos
COMPCada cifrado de esta serie oculta las letras, pero deja otra cosa a la vista. La sustitución conserva el recuento de cada letra, el cifrado con palabra clave las alinea en columnas y una libreta de un solo uso empleada dos veces delata los espacios. Solo una clave aleatoria tan larga como el propio mensaje no revela absolutamente nada. El problema pasa a ser entonces cómo hacérsela llegar al destinatario, algo que las dos últimas páginas resuelven a la vista de todos.
L3: universidad
COMPDos mitades del mismo problema, en el orden en que un estudio se enfrenta a ellas. Primero, se ha filtrado una clave y la licencia debe seguir funcionando para los demás. Resulta que esto cuesta un encabezado que no crece en absoluto con el tamaño del sistema. Después llega la mitad más difícil: saber de quién era esa clave, a partir de una copia que varios suscriptores crearon juntos específicamente para que no identifique a nadie.
Señales e información
L2: escuela
COMPUn codificador de vídeo no es un algoritmo, sino ocho etapas en un orden fijo, y el orden no es arbitrario: cada etapa existe porque la anterior hizo posible su trabajo. Esta herramienta modela una de ellas. La cadena de abajo enlaza con las otras siete.
L3: universidad
COMPDos herramientas que te muestran el interior de un modelo de lenguaje grande en el instante en que elige una palabra. La segunda se ejecuta literalmente sobre la primera: los candidatos que clasifica son entradas del vocabulario que la primera construye.
L3: universidad
COMPUna señal es una suma de flechas giratorias, y cualquier método práctico para interpretarlas tiene un coste que la fórmula del libro de texto pasa por alto. Una ventana finita dispersa un tono que no encaja en ella por todas las bandas; una ventana más corta gana tiempo y lo paga en afinación; un promedio es un filtro con forma propia, y la última página es la razón por la que todo esto resulta viable.
L3: universidad
COMPCuatro codificadores que podrías ejecutar en papel, ordenados según lo que cada uno puede ver que el anterior no podía. El cuarto no comprime absolutamente nada, y es la razón por la que el primero funciona con texto.
Demostración, conteo y juegos
L2: escuela
MATHEl problema del cumpleaños parece un truco de salón, pero en realidad es la herramienta estándar para analizar colisiones. En el segundo paso es donde los informáticos se lo vuelven a encontrar, bajo un nombre distinto.
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.
