Каждый раз, когда вы начинаете вводить запрос в поисковую строку, система за миллисекунды предлагает вам подходящие слова (автокомплит). Искать совпадения прямым перебором по огромной базе словарей было бы катастрофически медленно. Для решения задач быстрого поиска по префиксу в дискретной математике была разработана специализированная древовидная структура — Trie (префиксное дерево).
В разработке программного обеспечения (сборка модулей), строительстве и управлении проектами постоянно возникает задача: в каком порядке выполнять работу, если одни задачи жестко зависят от других? Например, вы не можете начать красить стены, пока не построена крыша. В теории графов эта математическая проблема изящно решается с помощью алгоритма топологической сортировки.
Современные социальные сети математически представляют собой гигантские графы, где вершины — это пользователи, а ребра — их дружеские или профессиональные связи. Анализ этих структур методами дискретной математики (Social Network Analysis, SNA) позволяет выявлять лидеров мнений, предсказывать тренды распространения информации и рекомендовать новых друзей или товары.
Когда мы сталкиваемся с NP-полными задачами, такими как задача коммивояжера или задача о рюкзаке, надежда на быстрое и абсолютно точное решение на больших данных исчезает. Но бизнес не может ждать годы, пока суперкомпьютер перебирает все варианты. В дискретной математике и проектировании алгоритмов на этот случай существует мощный план "Б" — приближенные алгоритмы и эвристики.
Могут ли невероятно сложные, непредсказуемые и живые структуры возникать из нескольких примитивных и жестко заданных правил? Дискретная математика отвечает на этот вопрос утвердительно с помощью концепции Клеточных автоматов. Это дискретные динамические системы, состоящие из регулярной сетки ячеек, которые меняют свои состояния шаг за шагом на основе локальных математических законов. Наибольшую славу этому разделу принесла "Игра Жизнь", созданная английским математиком Джоном Конвеем в 1970 году.
Когда браузер Chrome проверяет, не является ли открываемый вами сайт вредоносным, он сверяется с базой из миллионов плохих URL-адресов. Но выкачивать эту многогигабайтную базу на устройство каждого пользователя невозможно, а делать сетевой запрос к серверу Google при каждом клике — слишком долго. Решение этой проблемы предложил Бертон Блум в 1970 году, создав уникальную вероятностную структуру данных, позволяющую хранить огромные множества в крошечном объеме оперативной памяти.
В III веке нашей эры китайский математик Сунь-цзы записал интригующую головоломку: "Имеются вещи, число их неизвестно. Если считать их тройками, остаток 2. Если считать пятерками, остаток 3. Если считать семерками, остаток 2. Сколько всего вещей?". Эта, казалось бы, тривиальная задача привела к созданию математического аппарата, который сегодня используется для ускорения вычислений в цифровой обработке сигналов (DSP) и современной криптографии.
При анализе социальных сетей, проектировании беспроводных сетей или планировании логистики часто возникают задачи поиска экстремальных структур: как найти самую большую группу людей, где абсолютно все знакомы друг с другом? Или, наоборот, как разместить максимальное число антенн так, чтобы ни одна из них не создавала помехи другой? Эти противоположные по смыслу вопросы в дискретной математике описываются понятиями клики и независимого множества графа.
Когда вы нажимаете Ctrl+F в текстовом редакторе, чтобы найти слово в документе, алгоритм последовательно сканирует текст, сравнивая символы. Это работает быстро для коротких файлов, но если вам нужно найти подстроку в геноме человека размером 3 гигабайта или найти плагиат в миллионе книг? Обычные методы потерпят крах. В дискретной математике и алгоритмике эта проблема решается с помощью мощнейших индексных структур: суффиксных деревьев и суффиксных массивов.
Один и тот же математический граф можно нарисовать на листе бумаги бесконечным множеством способов. Мы можем расположить вершины кругом, квадратом, в виде звезды или хаотично, распутав и запутав ребра. Визуально это будут совершенно разные картинки, но с точки зрения дискретной математики они могут представлять абсолютно идентичную структуру связей. Задача определения структурного тождества двух графов называется проблемой изоморфизма графов.