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

Обычные Цепи Маркова описывают системы, которые изменяются сами по себе, случайным образом, словно погода. Но как математически описать робота, который перемещается по лабиринту? Робот сам влияет на свое будущее: он принимает решения, тратит энергию и получает вознаграждение за правильные шаги. В дискретной математике и теории оптимального управления эта задача формализуется через Марковские процессы принятия решений (Markov Decision Processes, MDP).

Когда веб-сервис вырастает до миллионов пользователей, одна база данных или один кэш-сервер (например, Memcached) перестает справляться с нагрузкой. Данные нужно шардировать — распределить по десяткам серверов. Как алгоритмически определить, на какой именно сервер положить фотографию пользователя? Стандартный подход с остатком от деления ломается при изменении архитектуры. Эту проблему в 1997 году решило консистентное хеширование (Consistent Hashing).