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

Когда вы получаете посылку от курьерской службы UPS, вы можете подумать, что математика не имеет никакого отношения в процессе ее доставки к вашей двери. Но на самом деле математика играет важную роль в том, как работники в грузовиках доставляют посылки.

В самом сердце операций UPS лежит процесс определения кратчайшего маршрута, который выберет водитель. У UPS есть примерно 96 000 транспортных средств, среди которых можно найти как машины, фургоны, мотоциклы, так и средства с альтернативными видами топлива, и каждый водитель посещает в среднем 150 пунктов назначений каждый день. Увеличение маршрута водителем хотя бы на одну милю будет стоить компании миллионы долларов в год. Поэтому у них есть огромный стимул сделать маршрут как можно короче и эффективнее.

Такая проблема – нахождение лучшего маршрута – хорошо известна математикам, которые называют ее задачей коммивояжера. Название было придумано, когда была распространена торговля «от двери до двери»; коммивояжер должен был посетить определенное количество домов за один день, поэтому ему было необходимо продумать маршрут, который позволит обойти их за наименьшее количество времени. Задача коммивояжера является сложной для решения, так как нужно принимать во внимание огромное количество факторов. Например, если водитель запланировал объехать 25 мест назначений в один день, то количество возможных маршрутов достигает 15 триллионов вариантов. Но благодаря компьютерным алгоритмам – набору инструкций, служащих определенной цели, – UPS может снизить число возможных маршрутов за короткий срок.

Усилия UPS в улучшении алгоритмов дали свои плоды в 2000-х, когда они создали компьютерную программу ORION (комплексная оптимизация и навигация на дороге). Математические вычисления программы ORION сэкономили их водителям миллионы миль в год. Вы можете сделать это и сами, если вам нужно выполнить ряд заданий, мысленно вы продумываете наиболее эффективный маршрут, чтобы минимизировать время и энергозатраты, например, чтобы дважды не возвращаться в одно и то же место или не попасть в пробку в час пик.

Эта проблема появилась и на больших экранах. В 2012 году вышел фильм, рассказывающий о четырех математиках, перед которыми стоит вопрос: давать ли военному ведомству США решение о равенстве классов сложности P и NP (см. главу 3.17), зная что обнародование их работы будет нести моральные последствия, как только военные получат решение, они смогут взломать любой код в мире и получат беспрецедентную власть.

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

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

Алгоритмы особенно важны в повседневном использовании Интернета. Если вы активный пользователь сети, вы сталкиваетесь с алгоритмами постоянно. Например, когда заказываете фильм, который вам порекомендовал Netflix, вы пользуетесь вычислительной мощностью алгоритма. Когда вы ищете слово в Google, определяете свои музыкальные предпочтения в Pandora, ставя лайки и дислайки песням, или ищете что-то на Amazon, алгоритмы обогащают ваш опыт в работе онлайн, соотнося то, что вам нравится и не нравится. С этой информацией сайты и программы могут предложить вам особые варианты, основываясь на ваших предпочтениях.