Среди всех проблем комбинаторной оптимизации Задача о рюкзаке (Knapsack problem) занимает особое, почетное место. Название задачи описывает понятную бытовую ситуацию: у вора есть рюкзак ограниченной вместимости, а перед ним лежат различные ценные вещи (часы, слитки золота, ноутбуки). Каждая вещь имеет свой вес и свою стоимость. Как вору набрать вещей в рюкзак так, чтобы их суммарный вес не порвал рюкзак, а суммарная стоимость добычи была максимально возможной?

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

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