Придумывая различные определения понятия связи – более специфические, чем простое знакомство, – можно исследовать и анализировать людские сообщества. Иногда таким образом возникают салонные игры, в которых требуется вычислить расстояние от произвольного человека до некой «центровой» персоны, обладающей, как правило, большим количеством связей. В 1994 году Кевин Бэйкон, выступая в поддержку своего фильма «Дикая река», в шутку заметил, что все актеры в Голливуде снимались либо с ним самим, либо с теми, кто с ним снимался. Тут же родилась игра под названием «Шесть шагов до Кевина Бэйкона», цель которой – найти кратчайший путь между заданным актером и Бэйконом через актеров, с которыми они вместе снимались. Для многих актеров путь до Бэйкона (и, соответственно, друг до друга) оказался очень коротким. Например, Чарли Чаплин находится от Бэйкона всего в трех шагах: в 1967 году он снял фильм «Графиня из Гонконга», в котором сам сыграл второстепенную роль; графиню играла Софи Лорен, которая в 1979 году снялась в малоизвестном фильме «Сила огня»; одну из главных ролей в этом фильме сыграл Илай Уоллак, позднее появившийся в эпизодической роли в фильме «Таинственная река»; в этом же фильме снимался и Бэйкон.

У математиков тоже есть похожая игра: через совместные публикации они ищут расстояние до Пола Эрдёша – гения комбинаторики и рекордсмена по количеству публикаций [2] .

В Королевском технологическом решили выяснить, выполняется ли закон «шести степеней» для дружеских связей между жителями Королевства. Как проверить, существует ли цепочка из шести связей между Элис и Джорджем? Простейший способ – перебрать все существующие цепочки длины шесть. Вот только в Королевстве, насчитывающем 20000 жителей, таких цепочек может набраться 3198400279980000480000. Даже если предположить, что компьютер будет проверять триллион цепочек в секунду, на решение задачи уйдет более ста лет. Неужели нет способа получше?

Оказывается, есть. Существует совсем не сложная процедура, позволяющая быстро определить расстояние между Элис и Джорджем.

• Присвоим Элис число 0.

• Присвоим всем друзьям Элис число 1.

• Присвоим число 2 всем друзьям тех, кто получил число 1 и у кого пока еще нет числа.

• Присвоим число 3 всем друзьям тех, кто получил число 2 и у кого пока еще нет числа.

• Продолжаем до тех пор, пока Джордж не получит число.

• Число Джорджа и будет расстоянием между ним и Элис.

Подобные неформальные описания вычислительных процессов называются алгоритмами. Своим названием алгоритмы обязаны персидскому математику по имени Мухаммад ибн Муса Аль-Хорезми, жившему в VIII–IX веке н. э. В 825 году Аль-Хорезми написал трактат «Книга об индийском счете», благодаря которому индийская система счисления широко распространилась сначала на Востоке, а затем и в Европе. В латинском переводе книга получила название Algoritmi de numero Indorum. Имя Аль-Хорезми превратилось на латыни в Algoritmi, что в конечном итоге и привело к возникновению термина «алгоритм».

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

Не стоит недооценивать важность этого события. В институте, конечно, могли бы написать программу, которая методично перебирает все возможные пути, пытаясь найти минимальное количество связей между Элис и Джорджем; вот только этой программе пришлось бы проверить столько путей, что она просто не закончила бы работу за разумное время. Более эффективный алгоритм позволил вычислить степень отчуждения для Элис и Джорджа за ничтожную долю секунды, а для всех пар жителей – за каких-то две минуты.

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

Институтские исследователи вскоре поняли, что их база может принести пользу обществу, и решили с ее помощью повысить число удачных браков. На сайте института появилось объявление о наборе 200 волонтеров: по 100 мужчин и женщин гетеросексуальной ориентации. Волонтеры откликнулись очень быстро. Теперь ученым предстояло «поженить» как можно больше участников.

Сколько вариантов должен рассмотреть каждый участник? Первому мужчине потенциально подходят 100 женщин. Когда выбор сделан, у второго мужчины остается 99 вариантов, у третьего – 98, и так далее. Итого получается 100 умножить на 99 умножить на 98 умножить на… умножить на 2 умножить на 1 – величина, называемая факториалом числа 100 и записываемая в виде «100!». Факториал числа 100 состоит из 158 цифр и намного превосходит гугол – число, изображаемое единицей со ста нулями. Термин «гугол» изобрел девятилетний племянник математика Эдварда Казнера, когда тот попросил мальчика придумать числу название.