Когда мы описываем зависимости в данных, мы часто используем направленные графы — Байесовские сети. Они отлично показывают причинно-следственные связи (Болезнь -> Симптом). Но как описать систему, где зависимости взаимны и симметричны? Например, пиксели на цифровой фотографии: цвет одного пикселя сильно зависит от цвета соседнего, но здесь нет "причины" и "следствия", они влияют друг на друга равноправно. Для моделирования таких структур дискретная математика использует неориентированные Марковские случайные поля (Markov Random Fields, MRF).

Классические криптографические хеш-функции (MD5, SHA-256) созданы с одной целью: обеспечить строгий лавинный эффект. Изменение всего одной запятой в томе "Войны и мира" приведет к совершенно другому, неузнаваемому хешу. Однако в машинном обучении, биоинформатике и системах рекомендаций нам нужно нечто диаметрально противоположное. Нам нужно, чтобы похожие объекты получали одинаковые хеши. Эту математическую магию обеспечивает Locality-Sensitive Hashing (LSH).

Проблема проверки графа на планарность (можно ли нарисовать его на плоскости без пересечения ребер) имеет важнейшее значение в проектировании топологии печатных плат и микрочипов (VLSI). Теорема Куратовского дает точный критерий (отсутствие подграфов K5 и K3,3), но наивный поиск этих подструктур занимает катастрофическое время O(V^6). В 1974 году Джон Хопкрофт и Роберт Тарьян совершили алгоритмическую революцию, создав алгоритм проверки, работающий за абсолютно линейное время O(V).

Обычные бинарные деревья поиска обладают отличным временем операций O(log N), но только если данные поступают в случайном порядке. Если загрузить в дерево уже отсортированный массив, оно выродится в длинную "макаронину", и время поиска деградирует до O(N). Строгие балансировщики (АВЛ-деревья или Красно-черные деревья) решают проблему, но их реализация требует сотен строк сложного кода с вращениями. Дискретная математика предлагает невероятно элегантную альтернативу — рандомизированное Декартово дерево (Treap).