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

При решении задач о поиске максимального потока в транспортных сетях классический алгоритм Форда-Фалкерсона имеет фатальный недостаток: его время работы зависит от величины самого потока. Если пропускные способности ребер иррациональны, алгоритм может вообще никогда не завершиться. Эту проблему блестяще решил советский математик Ефим Диниц в 1970 году, предложив алгоритм, работающий за строго полиномиальное время, не зависящее от значений пропускных способностей.

Две самые известные NP-трудные задачи в теории графов — это поиск Хроматического числа (минимального числа цветов для правильной раскраски вершин) и поиск Кликового числа (размера самой большой клики — полностью связанного подграфа). Очевидно, что хроматическое число не может быть меньше кликового (вершины клики обязаны иметь разные цвета). Но в общем случае хроматическое число может быть сколь угодно большим, даже если клик нет вообще. Однако существует элитный класс графов, для которых эти два числа всегда равны. Это Совершенные графы.

Как математически доказать серверу, что вы знаете пароль от своего аккаунта, не пересылая по сети сам пароль (и даже его хеш)? Как доказать налоговой, что ваша зарплата превышает нужный порог, не раскрывая точную сумму? В дискретной математике и криптографии этот кажущийся неразрешимым парадокс элегантно решается с помощью протоколов Доказательства с нулевым разглашением (Zero-Knowledge Proof, ZKP), созданных в 1985 году.