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

Жадные алгоритмы (Greedy algorithms) — это популярный класс алгоритмов оптимизации, которые на каждом шаге принимают локально наилучшее решение, надеясь, что эта последовательность приведет к глобально оптимальному ответу. Увы, жадный подход работает не всегда: в задаче о рюкзаке или поиске кратчайшего пути с отрицательными весами он терпит фиаско. Но как заранее узнать, сработает ли жадный алгоритм для конкретной задачи? Ответ на этот вопрос дает теория матроидов.

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

Теория игр — это раздел математики, изучающий оптимальные стратегии в ситуациях конфликта интересов. В то время как экономическая теория игр изучает непрерывные вероятностные модели (равновесие Нэша, дилемма заключенного), в дискретной математике и искусственном интеллекте акцент делается на комбинаторные игры с полной информацией. Шахматы, шашки, крестики-нолики — все эти игры поддаются строгому математическому анализу через построение деревьев решений.