160 интерактивных модулей делают наглядными геометрию, топологию, фракталы, математический анализ, алгебру, теорию вероятностей и алгоритмы. Поверните поверхность, измените построение или проследите алгоритм шаг за шагом.
Цепочка, которую можно прочесть, — исход, сумма, среднее — и два графика на одной оси log n с одним курсором: отклонение среднего входит в воронку ±2σ/√n, а перевес S_n − nμ растёт как √n и не садится никогда. Сначала предскажи, уходит ли перевес к нулю тоже, потом дай серии расти; рядом шесть других прогонов в тех же условиях. Навязанную серию среднее забывает, а счёт хранит; для монеты числа точные из биномиального; а источник Коши, у которого нет среднего, не садится вовсе.
Две тысячи экспериментов спрашивают, равно ли среднее нулю; доля отвергнувших при α = 0,05 считается. Без эффекта это 5 % — ошибка первого рода — и p-значения равномерны. С эффектом это мощность, растущая с эффектом и с n: половина σ находится в 32 % случаев при десяти наблюдениях и в 82 % при тридцати четырёх. Подглядывай в данные каждые пять наблюдений и останавливайся, когда p упало ниже 0,05, — и доля ложных срабатываний четверть. Всё сосчитано; кривая Стьюдента — из кода.
Монти Холл: смена двери выигрывает в 2/3 случаев — и только в 1/2, если ведущий не знал, где приз, хотя открыл ту же дверь. Двое детей: «хотя бы один мальчик» даёт двух мальчиков с вероятностью 1/3, «старший — мальчик» — 1/2, «мальчик, родившийся во вторник» — 13/27. Хорда Бертрана: случайная хорда длиннее стороны треугольника с вероятностью 1/3, 1/2 или 1/4 — смотря что значит «случайная». Каждый ответ — точная дробь и счёт по двадцати тысячам испытаний по зерну, а картинка показывает процедуру, которая его дала.
Способов сделать случайное число с заданным распределением немного, и все начинаются с равномерного. Пропусти его через обратную функцию распределения (показательное, Коши, треугольное). Возьми два и преврати в пару нормальных (Бокс–Мюллер). Кидай дротики в коробку вокруг плотности и оставляй попавшие под кривую (отбраковка — и доля оставленных π/4 у полукруга). Считай показательные ожидания в единице времени (Пуассон) или орлы в десяти монетах (биномиальное). Проследи один нумерованный жетон через машину, потом сверь всю выборку с точной кривой.
Исследуйте усиление амплитуды при неструктурированном поиске. Фазовый оракул меняет знак амплитуды отмеченного состояния, не меняя вероятностей в вычислительном базисе. Шаг диффузии превращает относительную фазу в увеличение вероятности успеха. Слишком много итераций снова уменьшают эту вероятность.
Четыре маленькие схемы с одной поворачиваемой фазой, читаемые в базисе Z, X или Y. Фаза — настоящее, расположенное свойство состояния: вектор Блоха ходит с ней по экватору, — и в неправильном базисе она совершенно невидима: за целый оборот наибольшее изменение любой вероятности исхода равно 1e-16. Поставь в конец второй Адамар — и та же фаза решает ответ достоверно. Это и есть интерференция, и в ней вся разница между квантовым компьютером и монеткой.
На станции Алисы — кубит-сообщение и половина общей пары, на станции Боба — другая половина. Пройди протокол по шагам — CNOT, H, измерение — и отправь два бита по обычному каналу. Останови их до прибытия и попробуй угадать; потом выбери поправку Боба и сравни то, что у него, с сообщением. Пока биты не пришли, кубит Боба — I/2 при любом сообщении, а после измерения у Алисы не остаётся копии.
Чёрный ящик считает функцию f из n битов в один бит, и спрашивать его можно только про входы. Чтобы наверняка узнать, постоянна она или сбалансирована, классически нужно полтаблицы плюс один вызов. Адамар на все, ОДИН вызов с ответом в виде знака, снова Адамар — и исход «все нули» решает дело. Таблица истинности здесь кликается, так что обещание можно нарушить руками: для любой таблицы ответ выпадает с вероятностью (1 − 2k/N)². А если таблица оказалась f(x) = s·x, тот же один вызов возвращает саму строку s.
Внесите X, Z или Y на объёмной плате, прочитайте синдром и раскройте исправление. Сравните остаточный логический оператор и верность входного состояния, затем проверьте точную вероятность серией прогонов.
На столе из дерева и латуни видно, почему НОД(a,b)=НОД(b,r). Переносите остаток, изучайте точные коэффициенты Безу и цепную дробь, сравнивайте пары и воспроизводимые выборки.
Циферблат из m делений и одна стрелка. Сложение рисует звезду, замыкающуюся за m/НОД(s, m) ходов; умножение — цикл, длина которого делит φ(m). У некоторых модулей первообразных корней нет вовсе, и карточка это говорит: такова теорема, а не неудача поиска.
Проведите решето руками на пронумерованных плитках: возьмите следующий делитель, предскажите, откуда начнётся его волна, и смотрите, как она вычёркивает кратные — уже вычеркнутые лишь задеваются. Рядом — pi(x) по счёту против приближений x/ln x и Li(x).
Сообщение проходит две степени по модулю на столе из дерева и латуни. Выполняйте целочисленные шаги, исследуйте перестановку и ищите делитель с точным счётчиком.
Сортировочный стол: ключи — бумажные бирки, каретка хеширует каждую и бросает в корзину с номером хеша, коллизия — два разных ключа в одной корзине. Хеш — именованная функция: сумма кодов, многочлен с основанием 31, FNV-1a — или равномерный оракул, стоящий за кривой дней рождения. Отредактируй ключ, посмотри вычисление хеша по символам, переверни один бит и сосчитай сдвинувшиеся биты хеша; сравни две функции на одних ключах.
Три сортировки бегут по одному массиву с одинаковой скоростью в сравнениях, и первой финиширует та, которая спросила меньше. Решает гонку не размер, а беспорядок: на отсортированном входе вставки берут 63 сравнения, а быстрая — 2016.
Два одинаковых лабиринта, два обхода, клетка в такт. Слой, на котором ширина нашла клетку, равен кратчайшему пути — это тождество. Глубина не короче никогда, а насколько длиннее — зависит от того, куда идти.
Местность, где шаг стоит цену клетки, в которую входишь, и волна закрытых вершин расходится по ЦЕНЕ, а не по расстоянию. Ползунок кладёт на карту отрицательное ребро, и у него три измеренных участка: права, ошибается, пути нет вовсе.
Кучи камней, а под ними их двоичная запись. Разряд, в котором единиц нечётное число, горит красным; когда красных нет, ходящий уже проиграл. Правило проверено разбором всей игры, а не пересказано.
Некоторые модули входят в несколько Suites. Здесь у общего эксперимента одна страница.
