Такая проблема – нахождение лучшего маршрута – хорошо известна математикам, которые называют ее задачей коммивояжера. Название было придумано, когда была распространена торговля «от двери до двери»; коммивояжер должен был посетить определенное количество домов за один день, поэтому ему было необходимо продумать маршрут, который позволит обойти их за наименьшее количество времени. Задача коммивояжера является сложной для решения, так как нужно принимать во внимание огромное количество факторов. Например, если водитель запланировал объехать 25 мест назначений в один день, то количество возможных маршрутов достигает 15 триллионов вариантов. Но благодаря компьютерным алгоритмам – набору инструкций, служащих определенной цели, – UPS может снизить число возможных маршрутов за короткий срок.
Усилия UPS в улучшении алгоритмов дали свои плоды в 2000-х, когда они создали компьютерную программу ORION (комплексная оптимизация и навигация на дороге). Математические вычисления программы ORION сэкономили их водителям миллионы миль в год. Вы можете сделать это и сами, если вам нужно выполнить ряд заданий, мысленно вы продумываете наиболее эффективный маршрут, чтобы минимизировать время и энергозатраты, например, чтобы дважды не возвращаться в одно и то же место или не попасть в пробку в час пик.
Эта проблема появилась и на больших экранах. В 2012 году вышел фильм, рассказывающий о четырех математиках, перед которыми стоит вопрос: давать ли военному ведомству США решение о равенстве классов сложности P и NP (см. главу 3.17), зная что обнародование их работы будет нести моральные последствия, как только военные получат решение, они смогут взломать любой код в мире и получат беспрецедентную власть.
2.11. Как алгоритмы влияют на ваш опыт работы в интернете?
Математическое понятие: алгоритмы
В сущности, алгоритм – это набор инструкций, который говорит вам, как достичь определенной цели за ограниченное число шагов. В теории алгоритмы не ограничены сферами математики и компьютеров. Если вы хотите смастерить скворечник, вам нужно следовать определенному набору инструкций. Если вы хотите сделать чашку на гончарном круге, вам опять же нужно будет следовать набору инструкций. Каждый из таких наборов инструкций является алгоритмом.
Вы наверняка знакомы с алгоритмами лучше, чем можете себе представить. В начальной школе, когда вы учились делить числа и складывать дроби, вы учились алгоритмам. Вы также учились алгоритмам, когда изучали последовательности действий при решении примеров (начать вычисления нужно всегда с того, что находится в скобках, а потом умножать, делить, прибавлять и вычитать). Другими словами, когда вы пытаетесь посчитать чаевые официанту в ресторане или сложить числа на салфетке, вы используете алгоритм.
Алгоритмы особенно важны в повседневном использовании Интернета. Если вы активный пользователь сети, вы сталкиваетесь с алгоритмами постоянно. Например, когда заказываете фильм, который вам порекомендовал Netflix, вы пользуетесь вычислительной мощностью алгоритма. Когда вы ищете слово в Google, определяете свои музыкальные предпочтения в Pandora, ставя лайки и дислайки песням, или ищете что-то на Amazon, алгоритмы обогащают ваш опыт в работе онлайн, соотнося то, что вам нравится и не нравится. С этой информацией сайты и программы могут предложить вам особые варианты, основываясь на ваших предпочтениях.
Приз NetflixВ 2006 году Netflix организовал соревнование, чтобы улучшить свой алгоритм по рекомендациям на 10 %, главный приз размером в 1 миллион долларов получила команда BellKor’sPragmatic Chaos. Ключом к победе стало то, что они предсказывали фильмы, которые понравятся людям, основываясь на разной информации, а потом сравнивали эти предсказания с оценками, которые зрители действительно в дальнейшем ставили фильмам. А рекомендации много значат для Netflix.
2.12. Объяснение парадокса Монти Холла
Математическое понятие: теория вероятности
Некоторые примеры математического мышления, такие, как парадокс дней рождения (см. главу 3.20), являются странными и нелогичными, но другие являются настолько ненормальными, что даже профессиональные математики с трудом верят в их подлинность. Одним из таких примеров является парадокс Монти Холла, названный в честь ведущего телешоу Let’s make a deal. Решение этой проблемы настолько удивительное, что даже после тщательного объяснения большинство людей будут чувствовать, что оно не может быть верным. В какой-то степени это математический эквивалент квантовой механики (область физики, которая изучает мельчайшие компоненты веществ): странный, в него трудно поверить, но он является верным.
В передаче ведущий предлагает игроку три двери. За одной из них находится новая машина; за двумя оставшимися – коза (или что-либо другое, не такое классное, как машина). Ведущий просит игрока выбрать дверь, за которой, по его мнению, находится машина. Потом, не открывая эту дверь, ведущий открывает другую дверь, показывая козу. Теперь игрок может изменить свой изначальный выбор. Вопрос состоит в том, стоит ли игроку придерживаться первоначального выбора или выбрать другую дверь.
Ответ: игрок всегда должен выбирать другую дверь. В начале игры вероятность выбора двери с машиной равна 1 к 3, но выбор другой двери на этом этапе удваивает шансы до 2 к 3. Как это возможно? Большинство людей считает, что изменение решения не имеет значения: после того, как ведущий открывает дверь, показывая одну из двух коз, шансы на выигрыш теперь составляют 1 к 2, так как одна дверь теперь прячет машину, а другая – вторую козу.
Но это убеждение не является правильным. Вы поймете почему, если возьмете лист бумаги и напишете все возможные варианты. Суть в том, что ведущий всегда открывает дверь, за которой находится коза. (Он никогда не откроет дверь, за которой прячется машина, иначе он испортит всю игру!) Теперь без опоры на нашу интуицию давайте выясним возможные перестановки:
• Вариант 1: Игрок выбирает дверь с козой № 1. Ведущий открывает дверь с козой № 2. Первоначальный выбор приведет к козе № 1, изменение решения приведет к машине.
• Вариант 2: Игрок выбирает дверь с козой № 2. Ведущий открывает дверь с козой № 1. Первоначальный выбор приведет к козе, изменение решения приведет к машине.
• Вариант 3: Игрок выбирает дверь с машиной. Ведущий открывает дверь с козой № 1 или козой № 2. Первоначальный выбор приведет к машине, изменение решения приведет к козе.
Итак, из этих трех вариантов можно сделать вывод, что в 2 из 3 случаев изменение решения ведет к машине. Результат абсолютно нелогичный, но абсолютно верный. Такова сила математики.
Парадокс коробки БертранаПохожей проблемой является коробка Бертрана, названная в честь Джозефа Бертрана, который написал о ней в книге, вышедшей в 1889 году. Представьте три коробки: одна с двумя золотыми монетами; одна с двумя серебряными монетами; и одна с одной золотой и одной серебряной монетами. Теперь выберите одну любую коробку и любую монету. Если она золотая, то какова вероятность того, что вторая монета тоже будет золотой? Вы можете подумать, что шансы составляют 1 к 2, но на самом деле 2 к 3.
2.13. Математика в жонглировании
Математическое понятие: комбинаторика
Когда вы думаете о жонглировании, вам, наверное, приходят на ум клоуны на днях рождения или цирк. Но вы, может быть, не знаете, что жонглирование стало темой для математических размышлений, одержимостью для людей, интересующихся головоломками и схемами. И как и математика, жонглирование обладает своей собственной нотацией.
Жонглерская нотация была создана независимо друг от друга жонглерами из Калифорнийского технологического института, Кембриджского университета и Калифорнийского университета в Санта-Круз в 1980-х. В жонглерской нотации каждому броску присваивается число. Нечетное число значит, что объект – скажем, мяч – подбрасывается одной рукой, а ловится другой, а четное число значит, что мяч остается в одной руке. Величина числа тоже очень важна: чем больше число, тем выше мяч подбрасывается в воздух. В броске с нотацией 3, например, мяч взлетит на уровне лица и в процессе перекинется на другую руку. В броске с нотацией 2 мяч взлетит на несколько сантиметров и будет пойман той же рукой. Страстные любители жонглирования могут делиться своими программами, записывая их с помощью жонглерской нотации, и могут использовать нотации других людей, чтобы попробовать новые конфигурации. Жонглеры также поняли, что нотация также отображает количество мячей, необходимых для той или иной программы. Количество мячей равно среднему числу всех чисел в нотации, таким образом, для программы 5551 вам понадобятся четыре мяча.
Жонглированием увлекался и Клод Шеннон, которого считают отцом теории информации. На самом деле Шеннон создал уравнение жонглирования: (F + D)H = (V + D) N (F – это время, которое мяч находится в воздухе, D – сколько мяч находится в руке, Н – количество рук, V – сколько рука остается пустой и N – количество жонглируемых мячей). А еще с помощью деталей конструктора Шеннон построил машину, в которой маленькие металлические мячи отскакивали от натянутой мембраны. В самом деле, клоуны и цирк!
Рекорды в жонглированииСогласно Книге рекордов Гиннесса, рекорд по жонглированию наибольшим количеством мячей принадлежит Алексу Баррону из Великобритании. 3 апреля 2012 года восемнадцатилетнему молодому человеку удалось жонглировать одиннадцатью мячами и ловить их 23 раза подряд.
2.14. Равновесие Нэша
Математическое понятие: теория игр
Математика не занимается лишь свойствами чисел. Некоторые области математики также пытаются изучить человеческое поведение, особенно то, как люди взаимодействуют друг с другом. Одной из таких областей является теория игр.
Теория игр была впервые представлена Джоном Форбсом Нэшем-младшим, математиком из Принстонского университета, который стал главным героем книги «Прекрасный ум. Жизнь математического гения и нобелевского лауреата Джона Нэша», по которой был снят фильм, вышедший в 2001 году с Расселом Кроу в главной роли. Игры, которые изучают теоретики игр, включают в себя не только шахматы и шашки. Они включают в себя разного рода взаимодействия между людьми, в которых решения, принимаемые одним человеком, зависят от решений, принимаемых другим человеком, включая деловые решения, войны и всякого рода экономические воздействия. Поэтому теория игр включает в себя не только чистые факты и правила, но и психическое состояние игроков, а также то, что каждый игрок думает об этих психических состояниях.
Один центральный элемент теории игр был назван в честь самого Нэша. Он называется равновесием Нэша, этот термин описывает игру, в которой каждый игрок не должен менять свою стратегию, даже если он знает стратегии всех остальных игроков. Другими словами, игра находится в равновесии Нэша, если никто не будет иметь преимуществ и не будет менять стратегии.
Вы, возможно, уже знакомы с примером равновесия Нэша: дилеммой заключенного. В этом случае два человека обвиняются в преступлении, и им грозит, предположим, три года тюрьмы. Но прокурор подозревает, что двое заключенных являются сообщниками, и предлагает каждому из них сделку. (Заключенные не могут никаким образом общаться друг с другом, поэтому они не знают, какое решение примет другой человек.) Если заключенный А признает, что заключенный Б – его сообщник, а заключенный Б не признает, то заключенный А получит один год тюрьмы – смягченный приговор, а заключенный Б получит пять лет тюрьмы. Верным будет и обратное: если заключенный Б признает, что заключенный А – его сообщник, а заключенный А не признает, то заключенный Б получит один год тюрьмы, а заключенный А получит пять лет тюрьмы. Если они оба сознаются, тогда оба получат по два года. Если посмотреть на общую картину, то кажется, что им обоим лучше во всем признаться. Но если каждый из них будет искать лучший выход, не зная, что решит другой, они оба решат ничего не говорить и получить по три года тюрьмы – первоначальный приговор, – хотя они и могли получить смягченный приговор, если бы признались во всем. Оказывается, случай, когда оба заключенных не признаются, соответствует равновесию Нэша, а остальное не соответствует.
Теория игрТеория игр проникает во все уголки нашей жизни, даже в те, которые, кажется, не связаны с играми и принятием решений. Одним примером является недавнее решение авиакомпании Southwest Airlines позволить людям за дополнительную плату сесть в самолет раньше, чтобы у них точно было свободное место на багажных полках над головой для их сумок. Перед каждым пассажиром стоял одинаковый выбор, так что, решая, заплатить ли лишние деньги, каждый пассажир должен был помнить, что остальные тоже могли это сделать. (Оказывается, что дополнительная плата является наилучшим выбором.)
2.15. Математика в стае скворцов
Математическое понятие: безмасштабная корреляция
Возможно, вы видели видео на YouTube, где летит большая стая скворцов, или, может быть, вам посчастливилось наблюдать за ними вживую. В любом случае, вы наверняка были удивлены тем, как каждая птица скоординирована друг с другом, каждый скворец летит синхронно с другими птицами. (Ни один скворец, например, не делает резких поворотов и не сталкивается с соседом.) Вы также, возможно, восхищались тем, как внезапное движение нескольких скворцов с краю передавалось практически в ту же секунду на всю группу, и все скопление парящих тел в перьях, казалось, ведет себя как единый организм.
Такое поведение соответствует принципу безмасштабной корреляции. Когда группа особей организована таким образом, любое движение, сделанное одним, влияет на всех других участников, несмотря на размер группы. В группе скорость и направление одного скворца напрямую влияют только на скорость и направление его ближайших семи соседей, но информация быстро распространяется на всю стаю. Их поведение придерживается статистической модели, которая похожа на то, как намагничивается металл или как ведут себя кристаллы снега перед лавиной. (Недавно команда ученых выяснила, что стаи скворцов соблюдают безмасштабную корреляцию, создав компьютерную модель, которая воссоздала позиции и скорость в трехмерном пространстве настоящих скворцов в стае численностью от 122 до 4268 особей.) И скворцы показывают мастерство координации без лидера, который ведет всех остальных скворцов; вместо этого каждый скворец будто следует простым правилам: «Лети с той же скоростью, что и твой сосед» и «Не столкнись ни с кем». Однако, несмотря на все исследования, никто точно не знает, как скворцы или другие животные, которые обладают таким же групповым поведением, так быстро передают информацию.
АнчоусыДругие животные обладают похожим поведением. Анчоусы, например, плавают большими группами или косяками, которые поворачиваются и меняют направление не хуже скворцов. А косяки анчоусов могут быть огромными: в 2014 году у берегов Сан-Диего был замечен косяк, в котором насчитывалось около 100 млн рыб.
2.16. Приводим в порядок кучу беспорядка
Математическое понятие: комбинаторика
Математика может найти смысл даже в вашем завтраке. Представьте, что вы заказали три пышных американских блинчика в своем любимом кафе, и когда официант приносит их и кладет на стол, вы замечаете, что они разного размера и лежат как попало: самый большой лежит сверху, самый маленький – в середине, а средний в самом низу. Предположим, что вы хотите, чтобы ваши блинчики лежали по порядку, чтобы самый маленький лежал сверху, средний – в центре, а большой – снизу. Давайте также представим, что для того, чтобы переложить блинчики, вам нужно следовать такому правилу: вам нужно взять лопатку, вставить в любое место между блинчиками и перевернуть те блинчики, которые находятся поверх лопатки так, чтобы то, что было сверху, оказалось снизу, а то, что снизу, – сверху. Сколько раз вам придется перевернуть блинчики, чтобы они лежали по порядку, используя эту процедуру?
Если у вас всего три блинчика, то вам понадобится перевернуть их два раза. В первый раз вы вставите лопатку под нижний блинчик и перевернете все три блинчика. Теперь самый большой блинчик будет снизу, самый маленький – в центре, а средний – сверху. На этом этапе вам надо вставить лопатку под самый маленький блинчик и перевернуть его и средний блинчик, тогда они поменяются местами. Теперь они лежат идеально!
Но математики обычно хотят узнать правила на общий случай, в нашем примере это будет стопка блинчиков из любого их количества и расположения. Какое максимальное количество переворачиваний потребуется, чтобы изменить порядок стопки из n-количества блинов? (Математики называют это число Pn, то есть количество блинов.) Pn для трех блинчиков равно трем, и это если рассматривать самое трудное расположение: маленький сверху, большой в центре, а средний снизу. (Математики обычно ищут максимальное число, а не минимальное, так как они хотят найти внешнюю границу.)
Так сложилось, что это очень трудная проблема. Математики нашли Pn, когда в стопке было 19 блинов, оно равно 22, но если блинчиков больше 19, то это число неверно. На самом деле никто не нашел общую формулу, которая выводит максимальное количество переворачиваний, нужных для того, чтобы сложить стопку из n-количества блинов по порядку.
Вторник на Масленой неделе – это время для католиков, когда они могут наслаждаться едой из сахара и масла перед Великим постом, традиционным периодом покаяния.