Я часто рассказываю математику тем, кто сам ею не занимается. Это непросто — и не только потому, что математика сложна сама по себе
Обычно математики интересуются тем, что связано с другими разделами самой математики, и людям «снаружи» непросто понять их мотивацию. Современная математика чаще всего развивается изнутри — из собственных понятий, задач и связей. Тем ценнее случаи, когда удаётся выстроить рассказ вокруг содержательных приложений
Больше текстов можно найти в моём телеграм канале Кроссворд Тьюринга, рекомендую канал про прикладную математику Все предельно. Подписывайтесь!)
Приложений у математики много, и про них написано немало. Но рассказать о них так, чтобы получилось коротко, по делу и интересно — непросто. Если объяснять подробно, получится курс лекций. А если пытаться ужаться — легко потерять суть или создать обманчивое впечатление простоты. Такие тексты требуют тонкого баланса: написать их трудно, и именно поэтому они особенно ценны
Пару дней назад я вернулся из байдарочного похода по Карелии, в котором прочёл книгу Нелли Литвак и Андрея Райгородского «Кому нужна математика?»
Она совсем небольшая (чуть больше 150 страниц) и устроена как серия коротких рассказов, каждый из которых посвящён одной теме на стыке чистой и прикладной математики
Это не учебник, а серия коротких историй — о математике, её приложениях и людях, которые эти приложения создавали
Каждый сюжет начинается с реальной проблемы: например, как составлять расписания, шифровать сообщения или продавать рекламу в поисковиках. После этого рассказано про метод её решения и математику, которая для неё нужна. Тут и попытка объяснить суть метода, и интересные исторические байки, и примеры того, как эти идеи реально работают в системах, которыми мы пользуемся каждый день
Это идеальное чтение для дороги: за полчаса погружаешься в один сюжет, а потом размышляешь о нём целый день
В этой статье я расскажу о книге поподробнее и перескажу три истории из неё, которые меня удивили
Для кого эта книга
«Кому нужна математика» — это путеводитель по задачам и методам прикладной математики, прежде всего в области интернета, передачи, хранения и анализа данных. Она не рассчитана на случайного читателя: её аудитория — те, кому всерьёз интересно, как работает окружающий нас цифровой мир
Для человека с хорошей математической базой, но без широкого прикладного бэкграунда, это отличный первый шаг, чтобы составить общее представление о том, как устроены приложения. А для тех, кто хорошо знаком с прикладной математикой, многое здесь будет знакомо — но, возможно, впервые собрано в одном месте и уложено в цельную картину
Книга несложная — основной текст доступен любому матшкольнику, но в конце каждой главы есть небольшое приложение для продвинутого читателя — с формулами и доказательствами
Всего в книге семь глав. Все темы разные, но их объединяет общий сюжет — как математика помогает делать интернет быстрым, точным и надёжным. Вот эти темы:
линейное программирование и составление расписаний
кодирование информации
связность интернета
обработка запросов
шифрование и защита данных
обработка больших данных при ограниченной памяти
механизмы интернет-рекламы
Книга попала в шорт-лист премии «Просветитель», а недавно её переиздали первой в серии «Математические основы ИИ» Альянса в сфере искусственного интеллекта
Фокус книги кажется естественным — но в таком формате я почти не встречал других текстов. Если вы знаете что-то похожее — буду рад рекомендациям
Три неожиданных истории
В этом тексте я не буду пересказывать книгу — её стоит читать целиком. Возможно, позже я напишу отдельные статьи по мотивам некоторых глав, но сейчас хочу рассказать о трёх эпизодах, которые особенно меня зацепили
Они не самые центральные в книге, но в них ярко проявляется то, что делает математику настолько полезной: способность решать задачи, которые иначе казались бы безнадёжными
Первая — о том, как математические трюки позволили решать задачи линейного программирования в десятки раз быстрее, чем любые аппаратные улучшения
Вторая — про неожиданную атаку на RSA, в которой использовалась только чистая математика и перебор
Третья — про то, как в Facebook проверяли гипотезу о «шести рукопожатиях» и с помощью нетривиального счётчика нашли среднюю длину пути на графе в миллионы узлов
Все они — про изящество и мощь идей. Формул в этом тексте не будет, но, надеюсь, удивление передать удастся
Математика быстрее процессоров
Многие практические задачи — от составления расписаний до управления складом, от оптимизации логистики до анализа стратегий в теории игр — сводятся к одной и той же математической постановке
У вас есть сотни, а то и тысячи переменных и набор условий, заданных линейными уравнениями или неравенствами. Нужно найти значения, удовлетворяющие этим условиям, при которых максимизируется заданная линейная функция. Это задача линейного программирования — фундаментальной области прикладной математики
В реальности часто требуется, чтобы переменные принимали только целые значения. Это ещё труднее. Тем не менее, уже десятилетиями эти задачи успешно решаются — с помощью симплекс-метода, метода ветвей и границ и их многочисленных улучшений
Алгоритмы продолжают развиваться, и это развитие даёт потрясающие плоды
В 2007 году американский математик Роберт Биксби провёл эксперимент: он взял все версии промышленного решателя CPLEX с 1991 года и проверил, как изменилась за это время скорость решения почти 2000 задач
Оказалось, что за 15 лет производительность выросла в 29 000 раз — и это на одном и том же компьютере. А в 2012 году появилась новая система Gurobi, которая ускорилась ещё в 16 раз. В сумме — почти полмиллиона
За это же время прирост мощности компьютеров, согласно закону Мура, составил около 8000 раз
Сравните: 8000 против 500 000. Получается, если вам нужно решить задачу линейного программирования, то выгоднее использовать старый компьютер с новыми алгоритмами, чем наоборот
Совместный эффект улучшения алгоритмов и роста производительности компьютеров поразительный!
Пример из книги: задача, которая в 1991 году решалась 126 лет, в 2012 году укладывается в одну секунду
А по оценкам 2015 года, общее ускорение достигло 450 миллиардов раз
Всё это стало возможным благодаря математике — методам, теоремам и идеям, разработанным задолго до того, как они стали частью промышленного кода
Как взломать интернет
Представьте: вы хотите передать код от банковской карты через интернет, при этом не раскрывая его провайдеру. Как передать секрет через незащищённый канал так, чтобы даже тот, кто перехватил сообщение, не смог его расшифровать? Это задача асимметричного шифрования — одного из краеугольных камней современной криптографии
Один из самых известных алгоритмов — схема Диффи–Хеллмана. Она устроена так, что обе стороны могут договориться о ключе, не раскрывая его в явном виде, используя открытые данные. Ключевую роль в этом играет очень большое простое число, которое известно всем. Само по себе это число не является секретом — наоборот, оно встроено в протокол
В 1977 году Мартин Гарднер опубликовал в Scientific American зашифрованное сообщение, созданное по подобной схеме
Его удалось расшифровать только через 15 лет, в 1992 году, с помощью суперкомпьютеров, распределённых вычислений и колоссальных усилий криптографов со всего мира
Долгие годы в большинстве систем использовалось одно и то же число — потому что менять его сложно, а риски казались чисто теоретическими. Но в 2015 году ситуация изменилась
Исследователи продемонстрировали новый метод атаки: можно заранее, за год вычислений и примерно за 100 миллионов долларов, провести подготовительную фазу, после которой дешифровка конкретных сообщений занимает доли секунды
Это стало возможным именно потому, что многие системы использовали одно и то же число: достаточно потратиться один раз — и потом можно расшифровывать весь трафик, проходящий через публичные каналы — от VPN до HTTPS
По оценкам, такая атака вполне лежит в пределах бюджета крупных госструктур, занимающихся кибербезопасностью. Авторы статьи прямо указывали на Агентство национальной безопасности США и предполагали, что некоторые ключи уже могли быть заранее взломаны
После этой публикации ведущие интернет-протоколы начали обновлять встроенные параметры, чтобы избежать массовой уязвимости
Facebook и шесть рукопожатий
Мы все слышали про «шесть рукопожатий»: мол, между любыми двумя людьми на Земле — всего шесть шагов знакомства. Эта гипотеза восходит к знаменитому эксперименту социолога Стэнли Милгрэма
В 1960-е годы он рассылал письма случайным жителям Небраски с просьбой передавать их своим знакомым, пока они не дойдут до нужного адресата в Бостоне
Из почти трёхсот писем дошли 64, и путь в среднем занимал шесть шагов
Спустя полвека у нас появилась идеальная площадка для проверки этой идеи — социальные сети. В 2011 году Facebook совместно с учёными Миланского университета решил выяснить, сколько рукопожатий в действительности отделяют пользователей друг от друга
Казалось бы, задача простая: взять данные о дружбе и для каждой пары пользователей посчитать минимальную длину цепочки. Но Facebook — это сотни миллионов человек и десятки триллионов пар. Никакая оперативная память не справится с такой нагрузкой
Чтобы посчитать количество рукопожатий, каждому пользователю сопоставляют вложенные списки:
в первый включают всех его друзей
во второй — друзей друзей
в третий — друзей третьего уровня
и так далее
На каждом шаге нужно определить, сколько новых пользователей мы увидели — то есть сколько уникальных имён встретилось в очередном списке. Но хранить все эти имена в оперативной памяти — совершенно нереально
Точно посчитать число различных элементов почти невозможно, но приблизительно — можно. Один из стандартных подходов — алгоритм K-Minimum Values: он запоминает несколько самых маленьких хешей и по ним оценивает общее количество. Метод надёжный, но всё же достаточно затратный по памяти
Настоящий прорыв произошёл в 2007 году, когда французский математик Филипп Флажоле предложил алгоритм HyperLogLog
Его идея — не хранить все элементы, а оценивать их число по частоте появления редких хешей
Алгоритм оказался не только в тысячи раз быстрее старых, но и на порядки экономнее по памяти
Благодаря этому его можно запускать сразу для всех пар пользователей — даже в таких гигантских сетях, как Facebook
Результаты оказались впечатляющими: средняя длина цепочки между двумя пользователями Facebook составила не шесть, а 4,74 рукопожатия
Филипп Флажоле умер в 2011 году — в разгар внедрения своего метода в индустрию. В его честь в системе Redis счётчики, использующие HyperLogLog, обозначаются префиксом PF
А сам алгоритм сегодня называют краеугольным камнем инфраструктуры работы с большими данными
P.S.
Я рассказал здесь всего о трёх историях — и то не самых центральных. В каждой главе есть моменты, которые заинтересуют и новичка, и специалиста. Книгу хочется похвалить и за точность изложения, и за вкус в выборе примеров, и за умение увлекать, не упрощая. Это очень редкое сочетание
Если вам интересно, как работает цифровой мир, «Кому нужна математика» будет отличным проводником
А если вы уже работаете в прикладной математике — вам будет приятно встретить знакомые идеи в хорошем изложении и неожиданном контексте
Очень советую прочесть книгу целиком. Она стоит того
📘 Нелли Литвак, Андрей Райгородский. Кому нужна математика? М.: МЦНМО, 2024
