Могут ли невероятно сложные, непредсказуемые и живые структуры возникать из нескольких примитивных и жестко заданных правил? Дискретная математика отвечает на этот вопрос утвердительно с помощью концепции Клеточных автоматов. Это дискретные динамические системы, состоящие из регулярной сетки ячеек, которые меняют свои состояния шаг за шагом на основе локальных математических законов. Наибольшую славу этому разделу принесла "Игра Жизнь", созданная английским математиком Джоном Конвеем в 1970 году.

Когда браузер Chrome проверяет, не является ли открываемый вами сайт вредоносным, он сверяется с базой из миллионов плохих URL-адресов. Но выкачивать эту многогигабайтную базу на устройство каждого пользователя невозможно, а делать сетевой запрос к серверу Google при каждом клике — слишком долго. Решение этой проблемы предложил Бертон Блум в 1970 году, создав уникальную вероятностную структуру данных, позволяющую хранить огромные множества в крошечном объеме оперативной памяти.

В III веке нашей эры китайский математик Сунь-цзы записал интригующую головоломку: "Имеются вещи, число их неизвестно. Если считать их тройками, остаток 2. Если считать пятерками, остаток 3. Если считать семерками, остаток 2. Сколько всего вещей?". Эта, казалось бы, тривиальная задача привела к созданию математического аппарата, который сегодня используется для ускорения вычислений в цифровой обработке сигналов (DSP) и современной криптографии.

При анализе социальных сетей, проектировании беспроводных сетей или планировании логистики часто возникают задачи поиска экстремальных структур: как найти самую большую группу людей, где абсолютно все знакомы друг с другом? Или, наоборот, как разместить максимальное число антенн так, чтобы ни одна из них не создавала помехи другой? Эти противоположные по смыслу вопросы в дискретной математике описываются понятиями клики и независимого множества графа.