При решении NP-трудных комбинаторных задач, таких как задача коммивояжера или целочисленное линейное программирование, полный перебор всех вариантов (Brute Force) занимает экспоненциальное время. Для 20 городов количество маршрутов превышает квинтиллион. Чтобы находить абсолютно точные оптимальные решения для задач такого масштаба без использования слепых эвристик, дискретная математика применяет метод ветвей и границ (Branch and Bound), который элегантно отсекает бесполезные ветви дерева решений.

Как убедиться, что файл размером в несколько терабайт, скачанный вами через торренты у сотен незнакомых людей, не содержит вирусов и не поврежден? Проверять весь файл целиком долго и ресурсозатратно. Если поврежден один байт, придется скачивать весь терабайт заново. В 1979 году Ральф Меркл запатентовал структуру данных на стыке графов и криптографии, которая позволила элегантно решить эту проблему — Хеш-дерево (Merkle Tree).

Иногда бросить монетку — это лучший способ решить сложную математическую задачу. В информатике существует класс рандомизированных алгоритмов, которые сознательно используют случайные числа в своей логике. Они могут ошибаться, но за счет своей невероятной простоты и скорости позволяют, запустив их тысячу раз, гарантированно получить правильный ответ. Самый красивый пример такого подхода — Алгоритм Каргера для поиска минимального разреза графа.