Поисковая система Google
В настоящее время поисковая система Google стала одним из основных инструментов поиска в интернете, и у нее огромное количество пользователей. Одной из причин такого успеха является ее эффективность, так как для каждого поискового запроса система быстро выдает упорядоченный список результатов, и первые из них, как правило, содержат то, что мы ищем. Способ упорядочивания результатов поиска, то есть присвоения числового рейтинга каждой странице, использует сложную математику — смесь линейной алгебры, теории графов и теории вероятностей.
При разработке поисковых систем, подобных системе Google, приходится решать и математические, и технические задачи. Другими словами, главный вопрос заключается в том, как упорядочить результаты поиска. Можно предположить, что рейтинг определенной веб-страницы зависит от количества других страниц, ссылающихся на нее. Однако существуют страницы, на которые мало ссылок, но которые очень важны для данного поиска. Поэтому такая модель невыгодна для пользователей. К тому же она может быть легко использована веб-сайтами для искусственного повышения рейтинга.
Создатели Google Сергей Брин и Ларри Пейдж разработали алгоритм для определения рейтинга страницы не по количеству ссылок на нее, а пропорционально важности этой страницы для данного поиска. Этот алгоритм требует решения системы алгебраических уравнений. Фактически задача сводится к линейной алгебре, а именно к вычислению собственных векторов и собственных значений некой матрицы. Если обозначить важность веб-страниц в интернете набором чисел (x1, …., xn), где n — число страниц, существующих в интернете, а хi — число, означающее важность конкретной веб-страницы i, то задача сводится к поиску в n-мерном пространстве элемента (x1, …., xn), который является решением некой системы уравнений.
В 2006 г. было подсчитано, что в интернете существует около 600 миллиардов веб-страниц. Это число и соответствует числу измерений рассматриваемого пространства. Такое пространство, безусловно, является многомерным!
* * *
АЛГОРИТМ, КОТОРЫЙ ИЗМЕНИЛ ИНТЕРНЕТ
В 1998 г. два молодых студента-информатика Стэнфордского университета в Калифорнии Ларри Пейдж и Сергей Брин заканчивали исследовательский проекте несколько загадочным названием «Анатомия системы крупномасштабного гипертекстного интернет-поиска». Он содержал первую версию простого и элегантного алгоритма PageRank, используемого для упорядочивания списка
страниц в зависимости от их значимости. PageRank стал основой поисковой системы Google, которая через несколько лет обошла Yahoo, Altavista и многие другие поисковые системы. Поиск в Google даже стал синонимом поиска в интернете (слово «гуглить»» еще не вошло в словари, но активно употребляется в разговорной речи).
Алгоритм PageRank действительно элегантен и прост и может быть записан следующим образом:
где Wj — рейтинг страницы j; Wi — рейтинг страницы i, которая содержит ссылку на страницу j; число d — коэффициент затухания со значением между 0 и 1, необходимый для сходимости рядов; ni, — число ссылок на странице Wi, на другие страницы; N — общее количество страниц, которые содержат ссылку на страницу j.
Рейтинг любой страницы является суммой рейтингов всех страниц, которые ссылаются на нее, с весовым коэффициентом, зависящим от общего числа ссылок на каждой.
Глава 3. Революция в геометрии XIX века
Геометрические аксиомы не являются экспериментальными данными. Лишь наблюдение физических явлений определяет выбор гипотез среди всех возможных. Тот или иной выбор может быть только более удобным, чем другие возможные.
Поэтому вопрос, какая геометрия истинна — Лобачевского или евклидова, — не имеет смысла. Это все равно что спрашивать, какие координаты вернее — декартовы или полярные.
А. Пуанкаре. О фундаментальных гипотезах геометрии (1887)
Нечасто математические проблемы представляют общий интерес. Однако вопросы четвертого измерения после двух геометрических революций XIX в. глубоко проникли в общество. Они заинтересовали ученых и философов, теологов и медиумов, писателей и художников, музыкантов и поэтов — общественность в целом.
Неевклидовы геометрии
Примерно в 300 г. до н. э. Евклид Александрийский опубликовал свою главную работу «Начала», в которой собрал все геометрические, арифметические и алгебраические сведения, известные в то время. Его труд начинался с изложения элементарных понятий и упорядочения имеющихся знаний; затем Евклид использовал дедуктивный метод и систему доказательств, в которой, среди прочего, важную роль играли более неформальные подходы, такие как интуиция, аналогии и симметрия.
Наряду с Библией «Начала» являются одной из наиболее влиятельных книг всех времен. Они неоднократно копировались, переводились на многие языки, а после изобретения книгопечатания постоянно переиздавались. На протяжении более двух тысячелетий этот труд использовался в качестве учебника и был стандартом математического мышления.
Одним из важнейших достижений Евклида был выбор группы основных постулатов, из которых с помощью аксиом и дедуктивного метода могут быть выведены все другие теоремы. Таким образом, для геометрии на плоскости сначала давались некоторые интуитивно понятные определения: точка, прямая линия, угол и так далее. Затем формулировались аксиомы — очевидные истины, не требующие доказательства. Например, «равные одному и тому же равны и между собой» или «целое больше части». И, наконец, пять постулатов Евклида, которые лежат в основе его геометрии, хотя он их не доказывает:
1. От всякой точки до всякой точки можно провести прямую.
2. Ограниченную прямую можно непрерывно продолжать по прямой.
3. Из всякого центра всяким раствором может быть описан круг.
4. Все прямые углы равны между собой.
5. Если прямая, пересекающая две прямые, образует внутренние односторонние углы, меньшие двух прямых, то, продолженные неограниченно, эти две прямые встретятся с той стороны, где углы меньше двух прямых.
Пятый постулат в современных терминах формулируется следующим образом: «Через точку, не лежащую на данной прямой, можно провести только одну прямую, не пересекающую данную». Очевидно, что эта аксиома не зависит от предыдущих.
К тому же ее формулировка длиннее и содержит в себе условие. Многие математики думали, что пятый постулат можно вывести из предыдущих аксиом, и попытались доказать это. Некоторые из них до конца жизни были уверены, что им удалось сделать это, а другие сомневались даже в том, что его можно считать постулатом.
* * *
ЕВКЛИД АЛЕКСАНДРИЙСКИЙ
Удивительно, как мало нам известно о жизни автора «Начал»». Его называют Евклид Александрийский, потому что он заведовал музеем в Александрии. Это учреждение наряду с великолепной библиотекой являлось хранилищем всех знаний того времени.
Евклид был скромен и доброжелателен, хотя часто саркастичен. «Нет царского пути к геометрии»», — так ответил он Птолемею, правителю города, когда тот спросил его, есть ли более короткий путь изучения геометрии, нежели «Начала»». А когда один ученик спросил, какова выгода от геометрии, Евклид приказал дать ему три монеты, «раз он хочет извлекать прибыль из учебы»». Считается, что Евклид также написал труды по широкому кругу других вопросов, таких как оптика, астрономия, геометрия, музыка и дидактика, хотя историки не уверены в том, один и тот же ли Евклид является автором всех этих текстов, приписываемых ему.
