Level up!

Математическая игра про рюкзак от N + 1 и компании Level Group

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

N + 1 совместно с компанией Level Group предлагают читателям попробовать на практике, насколько сложны такие задачи. В качестве модели мы предлагаем задачу о рюкзаке в нашей собственной геометрической трактовке: пользователю нужно сложить неправильные фигуры пентамино (это фигурки, составленные из пяти кубиков) так, чтобы затягивающий их контур — тот самый условный рюкзак из названия — имел минимальную возможную площадь. Похожего рода задачи приходится решать строителям для оптимизации стройки ежедневно: роль фигур здесь играют процессы, поставки, сроки зависящих друг от друга работ, параметры нагрузок и стоимость материалов, а объем рюкзака — эффективность реализации конечного проекта. Разумеется, главный интерес тут в том, чтобы эта эффективность была максимальной. То есть, когда все фигурки в модели сложены наилучшим образом.


В общем, хватит болтать, играйте!

Нашли опечатку? Выделите фрагмент и нажмите Ctrl+Enter.
Город изо льда

Как выглядит строительство в Арктике

В ХХ веке человечество, активно осваивающее природные ресурсы, добралось до Арктики, и на многолетней мерзлоте начали возникать города. Но оказалось, что дома и дороги, возведенные традиционными способами, в таких условиях долго не живут: даже там, где бывает смертельно холодно, грунт имеет свойство оттаивать. Вместе с платформой Homo Science рассказываем, как построить здание на многолетней мерзлоте и чем самым северным городам угрожает глобальное потепление.