Я часто рассказываю математику тем, кто сам ею не занимается. Это непросто — и не только потому, что математика сложна сама по себе
Обычно математики интересуются тем, что связано с другими разделами самой математики, и людям «снаружи» непросто понять их мотивацию. Современная математика чаще всего развивается изнутри — из собственных понятий, задач и связей. Тем ценнее случаи, когда удаётся выстроить рассказ вокруг содержательных приложений
Больше текстов можно найти в моём телеграм канале Кроссворд Тьюринга, рекомендую канал про прикладную математику Все предельно. Подписывайтесь!)
Приложений у математики много, и про них написано немало. Но рассказать о них так, чтобы получилось коротко, по делу и интересно — непросто. Если объяснять подробно, получится курс лекций. А если пытаться ужаться — легко потерять суть или создать обманчивое впечатление простоты. Такие тексты требуют тонкого баланса: написать их трудно, и именно поэтому они особенно ценны
Пару дней назад я вернулся из байдарочного похода по Карелии, в котором прочёл книгу Нелли Литвак и Андрея Райгородского «Кому нужна математика?»
Она совсем небольшая (чуть больше 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
