Обычные цепи Маркова отлично работают, если мы можем точно наблюдать состояние системы (например, какая сегодня погода или на какой веб-странице находится пользователь). Но что делать, если реальные состояния системы от нас скрыты, а мы можем наблюдать лишь косвенные, зашумленные сигналы (эмиссии), порождаемые этими состояниями? Для решения этой проблемы в 1960-х годах были разработаны Скрытые марковские модели (Hidden Markov Models, HMM) — один из главных столпов современного искусственного интеллекта.

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

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