Математические понятия: геометрия, алгоритмы
За последние несколько десятилетий компьютерная анимация шагнула далеко вперед, и самую большую эффективность в этом продвижении сыграли аниматоры из Pixar. Но компьютеры могут лишь следовать инструкциям, которые основаны на математике. Поэтому, когда перед аниматорами возникает новая проблема, такая, как изображение движения вьющихся волос Мериды из «Храброй сердцем», они обращаются за помощью к математике.
Pixar опирается на алгоритмы – наборы инструкций – для моделирования сложных объектов и поведения, и они поняли, что им потребуется совершенно новый набор для создания волос Мериды, которые будут состоять из 100 тысяч различных элементов. Насколько это будет сложно сделать? Согласно правилам комбинаторики – если существует n элементов, то существует n² путей для их столкновения, – существует 10 миллиардов вероятностей взаимодействия элементов волос Мериды.
В Pixar также впервые разработали математический метод для того, чтобы сглаживать острые края, а это крайне важно для изображения гладких контуров кожи и одежды. Компьютерные аниматоры создают трехмерные фигуры, используя многоугольники – фигуры, у которых есть как минимум три стороны, но на получаемых объектах появляются бороздки, как будто их сделали из блоков. С помощью их разбиения на более мелкие части аниматоры находят средние точки каждой из сторон и усредняют их. После многократных повторов этого действия блочные линии изображения с острыми краями превращаются в настоящие плавные кривые. Прямые линии становятся параболами, и на экранах появляется отличительная манера Pixar.
Аниматоры и инженеры в Pixar, может, и достаточны умны для создания новых алгоритмов, но одна из их самых успешных картин «История игрушек 2» (1999) была практически утеряна из-за неосторожной ошибки. Эта лента одна из немногих оценена в 100 % на Rotten Tomatoes, она также взяла «Золотой глобус» за лучший фильм (комедия или мюзикл), но ее могли и вовсе не выпустить, так как кто-то случайным образом удалил файлы с компьютеров в Pixar. Это будет вам дружеским напоминанием, чтобы вы всегда делали резервную копию.
3.17. Сага Candy Crush
Математическое понятие: компьютерное программирование
В последние несколько лет математики обнаружили, что популярная игра, в которую сейчас играют на Facebook и на мобильных устройствах, на самом деле является примером одной из самых сложных проблем в математической вселенной. Математические гуру доказали, что игра «Сага Candy Crush» является так называемым классом NP, то есть не существует простого прямого решения этой проблемы, хотя очень легко это решение проверить. Задачи класса NP отличаются от класса P, которые можно быстро решить.
Компьютерные ученые и математики с радостью хотели бы определить раз и навсегда, являются ли задачи класса Р и класса NP принципиально одинаковыми; то есть является ли каждая задача, которую можно легко проверить, той же задачей, которую можно легко решить. Решение этой задачи выдвинуто на премию задачи тысячелетия Институтом Клэя, и тот, кто сможет доказать, правдиво ли равенство P = NP или нет, получит заветный миллион долларов.
Одна из самых популярных игр на Facebook и на мобильных устройствах, игра «Сага Candy Crush» представляет собой игровую доску с разноцветными конфетами, включая лимонные леденцы и красные мармеладки. Игроки должны передвигать конфеты горизонтально или вертикально, чтобы создавать группу из трех одинаковых конфет.
Исследователи проанализировали скрывающуюся математику в игре «Candy Crush», отчасти используя сведение, то есть преобразование одной задачи в другую. Сведение помогает математикам определить, насколько трудно решить ту или иную задачу. Если новую задачу можно преобразовать в изначальную проблему, тогда обе задачи могут считаться одинаково сложными.
3.18. Вы вдохнули последний выдох Цезаря?
Математическое понятие: теория вероятности
Математика может показать основные аспекты человеческого существования, которые, откровенно говоря, поражают разум. Например, какова вероятность того, что вы только что вдохнули молекулы, которые выдохнул на смертном одре тот, кто жил тысячи лет назад? Математика может ответить на этот вопрос с удивительно высокой степенью точности. Как такое возможно?
Проблема и ее решение изложены в книге «Математическая безграмотность и ее последствия» Джона Аллена Паулоса, профессора математики в Темпльском университете в Филадельфии. Паулос спрашивает, можем ли мы определить, вдохнули ли мы в этот самый момент молекулы, которые выдохнул Юлий Цезарь в последнюю секунду своей жизни после того, как Брут нанес ему роковой удар кинжалом. Оказывается, если вы принимаете несколько предварительных условий, то вероятность этого больше, чем 99 %!
1. Во-первых, вы должны считать, что те молекулы, которые выдохнул Цезарь, распространились более или менее равномерно по всей земной атмосфере. (В конце концов, прошло более 2000 лет с момента его смерти.)
2. Во-вторых, вы должны считать, что большинство из них до сих пор свободны (не связаны с другими молекулами).
Теперь начнем: допустим, что в атмосфере всего G (какое-то число) молекул. Еще предположим, что Цезарь выдохнул Z (другое число) из них. Так что вероятность того, что вы вдохнули одну из этих молекул, равна Z/G. Так как вероятности всегда меньше 1, то шанс, что вы не вдохнули одну из этих молекул, равен 1–Z/G.
Теперь представим, что вы вдохнули три молекулы: из-за принципа умножения, вероятность того, что ни одна из этих молекул не была выдохнута Цезарем, равна [1–Z/G]3. Естественно, этот принцип применим к любому числу, поэтому мы можем обобщить, что если вы сейчас вдохнули Т молекул, то вероятность того, что ни одну из них не выдохнул Цезарь, равна [1–Z/G]T.
Поэтому вероятность того, что вы вдохнули хотя бы одну из этих молекул, можно представить, как 1–[1–Z/G]T. А так как Паулос вычислил, что Z и Т, возможно, равны 2,2 × 1022, а G равна 1044, то вероятность составляет около 99. Невероятно.
В этих расчетах о дыхании Цезаря мы сделали ряд (разумных) предположений. Предположения на самом деле играют большую роль в математике в целом. Например, Евклид основывал свои геометрические соображения на пяти постулатах, один из которых утверждает, что прямая линия может быть проведена между двумя любыми точками. А другой – что все прямые углы равны.
3.19. Как работают компьютеры?
Математическое понятие: булева алгебра
Компьютеры повсюду: начиная со смартфонов в вашем кармане до ноутбука в рюкзаке и гигантских серверов, которые позволяют Amazon обрабатывать онлайн-покупки, – вычислительные устройства проникли во все уголки повседневной жизни. Но как именно они работают? Как металлические компоненты внутри корпуса компьютера позволяют вам сидеть в Интернете, делиться фотографиями с друзьями или просто складывать или вычитать числа?
Ответ кроется в математике. Компьютерные схемы создаются в соответствии с принципами, изложенными Джорджем Булем, английским математиком, который жил с 1815 по 1864 год. Буль стал известен тем, что применил алгебраические методы к логике, дисциплине, которая концентрируется на правилах, по которым можно приходить к выводам, основанным на предпосылках. Классический пример логического аргумента – или набора утверждений, которые в сочетании с разумом обосновывают положение, – приводит нас к Сократу, древнегреческому философу. Вот этот аспект:
Все люди смертны.
Сократ – человек.
Следовательно, Сократ смертен.
Этот вид аргумента, известный как силлогизм, интересен, так как если первые два утверждения верны, то третье утверждение тоже должно быть правдой. И нам не обязательно использовать «люди», «смертен» и «Сократ». Мы могли бы их заменить на что угодно. Вот другая версия:
У всех птиц есть крылья.
Тукан – птица.
Следовательно, у тукана есть крылья.
Но логика может применяться не только к таким простым понятиям, как «люди» и «туканы». Она также относится к высказываниям, то есть утверждениям, которые могут быть истинными или ложными. Эти утверждения можно объединить с помощью слов «и», «или» и «не». Получившиеся комбинации могут иметь свою истинность значения. Вот несколько примеров высказываний:
В настоящее время существует король Франции.
Собаки могут дышать под водой.
Когда светофор красный, автомобили должны остановиться.
Первые два высказывания ложные; третье – истинное. Вот несколько примеров смешанных высказываний:
Солнце светит, и коровы пасутся на холме.
Либо идет дождь, либо снег.
Автомобиль движется, и его колеса поворачиваются.
Давайте разберем каждый пример:
• В случае первой комбинации, если оба высказывания о коровах и о солнце являются истинными, тогда конечное высказывание тоже истина. Если одно из них ложное (или они оба ложные), тогда все высказывание тоже ложное.
• Во втором примере целое высказывание является истиной, если истиной является высказывание о дожде или снеге.
• И опять-таки в третьем примере высказывание истинное, если оба высказывания являются истинными. Если хотя бы одно из них ложное, тогда все высказывание тоже ложное.
Нововведением Буля было то, что он заметил, что можно представлять логические высказывания при помощи символов, которые используются в математике. Если, например, высказывание о солнце было представлено как Х, а высказывание о коровах как Y, вы в некотором смысле могли бы сложить два высказывания и получить значение истинности: 1 для истины, 0 для лжи.
Хотя «и», «или» и «не» – это не просто абстрактные идеи. Инженеры в ХХ веке научились представлять их физическим способом, в виде логических элементов. Эти элементы в конечном итоге стали включаться в транзисторы и компьютерные чипы и лежат в основе вычислительных расчетов, которые делает каждый компьютер и по сей день. Все расчеты выполняются на основе определенной электрической ситуации, будучи «правдой» или «ложью». Таким образом, под каждым модным экраном бьется математическое сердце.
Историки утверждают, что Джордж Буль в детстве сам выучил латынь. Позже он стал деканом факультета естественных наук в Квинс Колледже в городе Корк и женился на Мэри Эверест (племяннице Джорджа Эвереста, в честь которого была названа гора Эверест).