Когда мы говорим об искусственном интеллекте, многие сразу представляют себе сложные нейронные сети, базирующиеся на непрерывной математике, производных и градиентных спусках. Однако огромный пласт машинного обучения (Machine Learning) прочно стоит на фундаменте дискретной математики и теории графов. Самым ярким примером классификаторов, интерпретируемых человеком, являются Деревья решений (Decision Trees) и их композиции, такие как алгоритм Случайного леса (Random Forest).

Если вы поцарапаете компакт-диск (CD/DVD), покроете QR-код пятнами грязи на 30% или отправите фотографию с космического зонда Вояджер-2 сквозь миллионы километров солнечной радиации, данные будут прочитаны абсолютно корректно и без единой ошибки. Эту цифровую магию восстановления безвозвратно утраченных байтов обеспечивает математический аппарат, разработанный Ирвингом Ридом и Густавом Соломоном в 1960 году — мощнейшие недвоичные циклические коды.

Задача поиска подстроки (паттерна) в большом тексте имеет множество решений. В то время как алгоритм Кнута-Морриса-Пратта (КМП) строит сложный префиксный автомат, Майкл Рабин и Ричард Карп в 1987 году подошли к проблеме с совершенно другой, алгебраической стороны. Они применили технику хеширования, создав изящный алгоритм, который до сих пор является стандартом для поиска плагиата в системах вроде Антиплагиат.

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