Удовольствие от Х.Увлекательная экскурсия в мир математики от одного из лучших преподавателей в мир

Строгац Стивен

Значения PageRank после одного обновления

В последующих кругах правило обновления остается прежним. Если обозначить через x, y, z текущий счет страниц X, Y и Z, то в результате обновления получим такой счет:

х' = z

y' = 1/2 x

z' = 1/2 x + y,

где штрихи говорят о том, что произошло обновление. Подобные многократно повторяющиеся вычисления удобно выполнять в электронной таблице (или вручную, если сеть маленькая, как в нашем случае).

После десяти повторений обнаружим, что от обновления к обновлению цифры практически не меняются. К этому моменту доля X составит 40,6 % от всего PageRank, доля Y — 19,8 %, а Z — 39,6 %. Эти значения подозрительно близки к числам 40, 20 и 40 %,

что говорит о том, что алгоритм должен к ним сходиться.

Так и есть. Эти предельные значения алгоритм Google и определяет для сети как PageRank.

Предельные значения PageRank

Вывод для данной маленькой сети такой: страницы X и Z одинаково важны, несмотря на то что у Z в два раза больше входящих ссылок. Это и понятно: страница X равна Z по значимости, поскольку она получает от нее полное одобрение, однако взамен дает ей лишь половину своего одобрения. Вторая половина отправляется Y. Это также объясняет, почему Y достается только половина от долей X и Z.

Интересно, что эти значения можно получить, не прибегая к многократным итерациям. Надо просто подумать над условиями, определяющими стационарное состояние. Если после очередного обновления ничего не меняется, то x' = x, y' = y и z' = z. Поэтому, заменив переменные со штрихом в уравнениях обновлений на их эквиваленты без штрихов, получим систему уравнений

х = z

y = 1/2 x

z = 1/2 x + y,

при решении которой x = 2y = z. Поскольку сумма значений x, y и z должна равняться 1, отсюда следует, что x = 2/5, y = 1/5 и z = 2/5, что соответствует ранее найденным значениям.

Давайте на мгновение вернемся назад и посмотрим, как все это вписывается в широкий контекст линейной алгебры. Приведенное выше уравнение стационарного состояния, так же как и уравнения обновления, содержащие штрихи, — типичные примеры линейных уравнений. Они называются линейными, поскольку описывают прямые линии: переменные x, y, z в этих уравнениях в первой степени, так же как и в знакомом нам из курса алгебры средней школы уравнении прямой y = mx + b.

Линейные уравнения, в противоположность уравнениям, содержащим нелинейные члены, например x² или yz, либо sin x, решаются относительно просто. Сложности начинаются там, где в уравнениях присутствует огромное количество переменных, как это происходит в реальной сети. Поэтому одной из центральных задач линейной алгебры является разработка более быстрых алгоритмов для решения больших систем уравнений. Даже незначительные усовершенствования этих алгоритмов ощущаются практически во всех сферах жизни — от расписания авиарейсов до сжатия изображения.

Однако самой существенной победой линейной алгебры, с точки зрения ее роли в повседневной жизни, безусловно, стало решение парадокса дзен-буддизма для ранжирования страниц. «Страница хороша в той мере, в какой хорошие страницы ссылаются на нее». Переведенный в математические символы, этот критерий становится алгоритмом PageRank.

Поисковик Google стал тем, чем он есть сегодня, после решения уравнения, которое и мы с вами только что решили, но с миллиардами переменных — и, соответственно, с миллиардными прибылями.

Часть VI. Границы возможного

25. Самые одинокие числа

Как поется в знаменитой песне 1960-х годов, один — самое одинокое число [141] , хотя, вдвоем порой бывает еще хуже, чем одному. Возможно, так и есть, но и с простыми числами тоже все непросто.

Паоло Джордано объясняет почему в своем бестселлере The Solitude of Prime Numbers («Одиночество простых чисел») [142] . Это меланхолическая история любви двух затерянных в жизни людей, двух простых чисел, Маттиа и Аличе. В детстве им пришлось пережить трагедию, вследствие которой они практически перестали общаться с окружающими, но нашли друг в друге родственные души. Джордано пишет.

141

Гарри Нилссон написал песню One, получившую известность под названием Three Dog Night. Она стала хитом, заняв пятое место в горячей сотне хитов Billboard Hot 100, а Эйми Манн создала ее великолепную версию для фильма «Магнолия».

142

См. P. Giordano, The Solitude of Prime Numbers (Pamela Dorman Books/Viking Penguin, 2010).

Простые

числа делятся только на единицу и самих себя. Они занимают свое место в бесконечном ряду простых чисел, которые, как и остальные числа, зажаты между двумя другими, но на один шаг дальше, чем предыдущие. Эти числа подозрительны и одиноки, и Маттиа казалось, что они волшебные. Иногда он думал, что они очутились в этом ряду по ошибке, как жемчужины, нанизанные на нитку ожерелья. А порой ловил себя на мысли, что они тоже предпочли бы быть обычными числами, однако по какой-то причине не сложилось. […]

Учась на первом курсе университета, Маттиа узнал, что среди простых чисел есть еще более причудливые экземпляры. Математики называют их простыми числами-близнецами: это пара близлежащих друг к другу чисел, находящихся почти рядом, но между ними всегда стоит четное число, которое не дает им по-настоящему воссоединиться. Это, например, числа 11 и 13, 17 и 19, 41 и 43. Если набраться терпения и продолжить считать дальше, то вы увидите, что постепенно такие пары встречаются все реже. Вы сталкиваетесь с простыми числами, которые становятся все более одинокими, потерянными в этом молчаливом, измеренном пространстве, состоящем только из цифр, и у вас возникает тяжелое предчувствие того, что предыдущие пары чисел были случайными, и их истинное предназначение — одиночество. Потом, когда вы уже готовы сдаться и вам больше не хочется считать, вы встречаете еще одну пару близнецов, крепко держащихся друг за друга. Среди математиков существует убеждение, что, как бы далеко ты ни зашел, всегда можно найти еще пару чисел, даже если никто точно не знает, где они будут обнаружены.

Маттиа думал, что они с Аличе похожи на эти простые числа-близнецы, одинокие и потерянные, близкие, но не до такой степени, чтобы прикоснуться друг к другу.

Здесь я хотел бы остановиться на нескольких красивых идеях из приведенного отрывка, в частности на моменте, касающемся одиночества простых чисел и простых чисел-близнецов. Эти проблемы — центральные в теории чисел [143] , самой чистой области математики, изучающей целые числа и их свойства.

Однако прежде чем подняться в облака, давайте разберемся с вопросом, который часто возникает у прагматиков. Есть ли какая-либо польза от теории чисел? Есть. Теория чисел представляет собой основу алгоритмов [144] , ежедневно используемых, чтобы обеспечить безопасность проведения транзакций в интернете, а также для шифрования секретных переговоров, имеющих стратегическое значение. Эти алгоритмы построены на сложности разложения очень больших чисел на простые множители.

143

Сложно сказать, с чего начать, чтобы поближе познакомиться с теорией чисел, и особенно с загадками простых чисел. Вы можете выбрать одну из следующих трех замечательных книг. Все они выпущены примерно в одно и то же время и все обращаются к гипотезе Римана, которая рассматривается как самая большая нерешенная задача в математике. Чтобы глубже познакомиться с математическими подробностями и историей гипотезы Римана, я рекомендую книгу J. Derbyshire, Prime Obsession (Joseph Henry Press, 2003). В книгах D. Rockmore, Stalking the Riemann Hypothesis (Pantheon, 2005) и M. du Sautoy, The Music of the Primes (Harper Collins, 2003) больше внимания уделяется последующему развитию этой темы, однако они тоже написаны в очень доступной форме.

Прим. ред.: По теории чисел существует такая обширная литература, что трудно остановиться на чем-то одном. Вот несколько «классических» введений в эту теорию: Боревич З. И., Шафаревич И. Р… Теория чисел. М.: Наука, 1972; Виноградов И. М. Основы теории чисел. М.-Л.: Гостехиздат, 1952; Хинчин А. Я. Три жемчужины теории чисел. М.: Наука, 1979. Литература по простым числам: Гальперин Г. «Просто о простых числах» // Квант. 1987. № 4; Генри С. Уоррен. Формулы для простых чисел // Алгоритмические трюки для программистов. М.: «Вильямс», 2007; Матиясевич Ю. Формулы для простых чисел // Квант. 1975. № 5; Карпушина Н. Палиндромы и «перевертыши» среди простых чисел // Наука и жизнь. 2010. № 5. О гипотезе Римана и ее связи с простыми числами см. интересную статью Николенко С. Проблемы 2000 года: гипотеза Римана // Компьютерра. 2005. Рекомендуем также интересный и познавательный сайт «Числонавтика», посвященный теории чисел (и не только) по адресу http://www.numbernautics.ru/.

Дж. Дербишир. Простая одержимость. Бернхард Риман и величайшая нерешенная проблема в математике. М.: Астрель, 2010.

144

Использование теории чисел в криптографии описано в работе M. Gardner, Penrose Tiles to Trapdoor Ciphers (Mathematical Association of America, 1997), главы 13 и 14. В первой из этих глав приводится знаменитая статья Гарднера, опубликованная в августе 1977 года в журнале Scientific American, где он рассказывает о создании криптографической системы RSA, взломать которую практически невозможно. В главе 2 описывается «ужас», который вызвало это открытие в Национальном агентстве безопасности. О последних исследованиях в этой области говорится в главе 10 книги du Sautoy, The Music of the Primes.

Прим. ред.: Литература по криптографии: Нестеренко Ю. В. Алгоритмические проблемы теории чисел // Введение в криптографию / Под редакцией В. В. Ященко. СПб: Питер, 2014. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003; Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. М.: МЦНМО, 2002; Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты. М.: УРСС, Либроком, 2011.