Как убедиться, что файл размером в несколько терабайт, скачанный вами через торренты у сотен незнакомых людей, не содержит вирусов и не поврежден? Проверять весь файл целиком долго и ресурсозатратно. Если поврежден один байт, придется скачивать весь терабайт заново. В 1979 году Ральф Меркл запатентовал структуру данных на стыке графов и криптографии, которая позволила элегантно решить эту проблему — Хеш-дерево (Merkle Tree).
Иногда бросить монетку — это лучший способ решить сложную математическую задачу. В информатике существует класс рандомизированных алгоритмов, которые сознательно используют случайные числа в своей логике. Они могут ошибаться, но за счет своей невероятной простоты и скорости позволяют, запустив их тысячу раз, гарантированно получить правильный ответ. Самый красивый пример такого подхода — Алгоритм Каргера для поиска минимального разреза графа.
Обычные Цепи Маркова описывают системы, которые изменяются сами по себе, случайным образом, словно погода. Но как математически описать робота, который перемещается по лабиринту? Робот сам влияет на свое будущее: он принимает решения, тратит энергию и получает вознаграждение за правильные шаги. В дискретной математике и теории оптимального управления эта задача формализуется через Марковские процессы принятия решений (Markov Decision Processes, MDP).
Когда веб-сервис вырастает до миллионов пользователей, одна база данных или один кэш-сервер (например, Memcached) перестает справляться с нагрузкой. Данные нужно шардировать — распределить по десяткам серверов. Как алгоритмически определить, на какой именно сервер положить фотографию пользователя? Стандартный подход с остатком от деления ломается при изменении архитектуры. Эту проблему в 1997 году решило консистентное хеширование (Consistent Hashing).
При проектировании распределенных систем часто возникает ситуация, когда данные физически разделены между двумя компьютерами, и им необходимо совместно вычислить какую-то функцию. Пересылка всех данных целиком по сети слишком дорога или невозможна из-за узкого канала. В 1979 году Эндрю Яо создал новый раздел дискретной математики — коммуникационную сложность (Communication Complexity), который изучает, какое минимальное количество битов необходимо передать для решения задачи.
Когда вы разговариваете по сотовому телефону, слушаете MP3 музыку или отправляете JPEG фотографию, ваши устройства непрерывно выполняют одну из важнейших математических операций в истории человечества — Дискретное преобразование Фурье (DFT). Изначально Фурье-анализ применялся к непрерывным физическим волнам, но дискретная математика адаптировала его для работы с цифровыми массивами чисел, породив цифровую обработку сигналов (DSP).
Современная цифровая экономика держится на одном математическом допущении: классические компьютеры не могут быстро раскладывать гигантские числа на простые множители (факторизация) и не могут вычислять дискретные логарифмы. На этом базируются RSA, ECC и Диффи-Хеллман. Но в 1994 году американский математик Питер Шор создал алгоритм, который потряс основы мировой безопасности. Этот алгоритм предназначен для компьютеров совершенно новой архитектуры — квантовых.
Каждый разработчик мечтает о существовании идеального статического анализатора кода — волшебной программы, которая просканирует исходный код проекта и со 100% точностью скажет: "Здесь программа упадет с ошибкой деления на ноль", или "Эта функция никогда не вернет отрицательное число". К сожалению, дискретная математика и теория вычислимости ставят на этих мечтах жирный крест. Имя этому приговору — Теорема Райса.
Среди тысяч алгоритмических задач существует одна, которая носит титул "самой важной задачи теоретической информатики". Это задача о выполнимости булевых формул, сокращенно SAT (от англ. Satisfiability). Она стала первой в истории задачей, для которой была математически доказана принадлежность к классу NP-полных задач, и именно к ней сводятся все доказательства сложности в дискретной математике.
В любом классическом учебнике по алгоритмам написано, что лучшая возможная сложность для сортировки массива — это O(N log N). Эту асимптотику выдают быстрая сортировка (QuickSort) и сортировка слиянием (MergeSort). В дискретной математике существует строгое доказательство того, что сортировки, основанные на сравнении элементов, физически не могут работать быстрее. Но что, если мы откажемся от операций сравнения? Здесь на сцену выходят алгоритмы сортировки за линейное время O(N).
