Рафаель Роузен - Математика для гиков

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

За последние несколько десятилетий компьютерная анимация шагнула далеко вперед, и самую большую эффективность в этом продвижении сыграли аниматоры из Pixar. Но компьютеры могут лишь следовать инструкциям, которые основаны на математике. Поэтому, когда перед аниматорами возникает новая проблема, такая, как изображение движения вьющихся волос Мериды из «Храброй сердцем», они обращаются за помощью к математике.

Pixar опирается на алгоритмы – наборы инструкций – для моделирования сложных объектов и поведения, и они поняли, что им потребуется совершенно новый набор для создания волос Мериды, которые будут состоять из 100 тысяч различных элементов. Насколько это будет сложно сделать? Согласно правилам комбинаторики – если существует n элементов, то существует n² путей для их столкновения, – существует 10 миллиардов вероятностей взаимодействия элементов волос Мериды.

В Pixar также впервые разработали математический метод для того, чтобы сглаживать острые края, а это крайне важно для изображения гладких контуров кожи и одежды. Компьютерные аниматоры создают трехмерные фигуры, используя многоугольники – фигуры, у которых есть как минимум три стороны, но на получаемых объектах появляются бороздки, как будто их сделали из блоков. С помощью их разбиения на более мелкие части аниматоры находят средние точки каждой из сторон и усредняют их. После многократных повторов этого действия блочные линии изображения с острыми краями превращаются в настоящие плавные кривые. Прямые линии становятся параболами, и на экранах появляется отличительная манера Pixar.

Аниматоры и инженеры в Pixar, может, и достаточны умны для создания новых алгоритмов, но одна из их самых успешных картин «История игрушек 2» (1999) была практически утеряна из-за неосторожной ошибки. Эта лента одна из немногих оценена в 100 % на Rotten Tomatoes, она также взяла «Золотой глобус» за лучший фильм (комедия или мюзикл), но ее могли и вовсе не выпустить, так как кто-то случайным образом удалил файлы с компьютеров в Pixar. Это будет вам дружеским напоминанием, чтобы вы всегда делали резервную копию.

В последние несколько лет математики обнаружили, что популярная игра, в которую сейчас играют на Facebook и на мобильных устройствах, на самом деле является примером одной из самых сложных проблем в математической вселенной. Математические гуру доказали, что игра «Сага Candy Crush» является так называемым классом NP, то есть не существует простого прямого решения этой проблемы, хотя очень легко это решение проверить. Задачи класса NP отличаются от класса P, которые можно быстро решить.

Компьютерные ученые и математики с радостью хотели бы определить раз и навсегда, являются ли задачи класса Р и класса NP принципиально одинаковыми; то есть является ли каждая задача, которую можно легко проверить, той же задачей, которую можно легко решить. Решение этой задачи выдвинуто на премию задачи тысячелетия Институтом Клэя, и тот, кто сможет доказать, правдиво ли равенство P = NP или нет, получит заветный миллион долларов.

Одна из самых популярных игр на Facebook и на мобильных устройствах, игра «Сага Candy Crush» представляет собой игровую доску с разноцветными конфетами, включая лимонные леденцы и красные мармеладки. Игроки должны передвигать конфеты горизонтально или вертикально, чтобы создавать группу из трех одинаковых конфет.

Исследователи проанализировали скрывающуюся математику в игре «Candy Crush», отчасти используя сведение, то есть преобразование одной задачи в другую. Сведение помогает математикам определить, насколько трудно решить ту или иную задачу. Если новую задачу можно преобразовать в изначальную проблему, тогда обе задачи могут считаться одинаково сложными.