Рауль Ибаньес - Мир математики: т.6 Четвертое измерение. Является ли наш мир тенью другой Вселенной? Страница 7

Кодировка ASCII содержит 256 возможных кодов для выражения различных символов, другими словами, с помощью этих кодов можно закодировать 256 печатных символов. Бит каждого «слова» можно рассматривать как координату, хотя она принимает только значения 0 и 1. Каждое «слово» из k бит представляет собой точку в координатном пространстве размерности k, другими словами, количество размерностей равно длине слов. Например, шестнадцатеричное слово ООН отождествляется с точкой (0, 0, 1, 1) четырехмерного координатного пространства. В этом пространстве можно задать расстояние — способ измерения, насколько далеко друг от друга находятся точки (двоичные «слова») этого геометрического пространства.

Например, так называемое расстояние Хэмминга между двумя словами определяется количеством цифр, которыми эти слова различаются (так, слова ООН и 1011 находятся на расстоянии 1). В этом координатном пространстве мы можем использовать все математические инструменты арифметики, алгебры, анализа и геометрии.

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

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

Самокорректирующийся код американского инженера Ричарда Уэсли Хэмминга устроен так: к каждому шестнадцатеричному слову с помощью математического алгоритма добавляются еще три бита (например, слово ООП превратится в 0011101). К тому же, этот код способен исправить ошибку в одном из битов слова.

Код Хэмминга очень прост, но существуют и другие, гораздо более сложные коды обнаружения и исправления ошибок. Например, код Рида — Соломона, который используется в компакт-дисках и в телеметрии с гражданских спутников, где применяются 65- и 265-битовые слова соответственно, то есть каждое слово представляет собой точку в координатном пространстве с 65 и 265 измерениями. Таким образом, использование математического аппарата в координатном пространстве оказывается очень полезным, особенно при создании кодов для обнаружения и исправления ошибок.

Поисковая система 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. От всякой точки до всякой точки можно провести прямую.