Ознакомительная версия. Доступно 18 страниц из 89
Вернемся теперь к задаче о мощении пола. Сначала найдем самую большую квадратную плиту, которая входит в помещение заданной формы. Затем найдем самую большую квадратную плиту, которая помещается на оставшийся участок, – и так далее, пока не дойдем до последней квадратной плиты, которая целиком заполнит все оставшееся место. Это и есть самая большая квадратная плита, которая позволит покрыть весь пол, не разрезая плит.
Если M = 36, а N = 15, то при делении M на N получится остаток N1 = 6. При делении N на N1 получится остаток N2 = 3. Но при делении N1 на N2 никакого остатка не получится, и таким образом мы выясняем, что наибольшее число, на которое делятся и 36, и 15, равно 3.
Как вы видите, в этой процедуре много выражений типа «если…, то…». Это характерно для алгоритмов, и именно это обеспечивает столь превосходную пригодность алгоритмов для программирования и компьютеров. Древняя инструкция Евклида затрагивает самую суть четырех ключевых свойств, которыми в идеале должен обладать любой алгоритм:
1. Он должен состоять из точно сформулированных и однозначных инструкций.
2. Процедура всегда должна заканчиваться (а не уходить в бесконечный цикл!), какие бы числа в нее ни ввели.
3. Она должна выдавать ответ для любых значений, введенных в алгоритм.
4. В оптимальном варианте алгоритм должен быть быстрым.
Ни в каком из шагов алгоритма Евклида нет никакой неоднозначности. Поскольку остаток от деления уменьшается на каждом шаге, он неизбежно доходит до нуля за конечное число шагов, после чего алгоритм останавливается и выдает ответ. Чем больше числа, тем больше время работы алгоритма, но работает он все же относительно быстро. (Если вас интересует точное значение, число шагов в пять раз больше числа знаков в меньшем из двух чисел.)
Если самые старые алгоритмы появились более 2000 лет назад, почему же само это название происходит от имени персидского математика IX века? Мухаммад Аль-Хорезми был одним из первых руководителей великого «Дома мудрости» в Багдаде и отвечал за перевод многочисленных древнегреческих текстов по математике на арабский язык.
Слово «алгоритм» происходит от латинской транскрипции его имени. Хотя все инструкции к алгоритму Евклида приведены в его «Началах», язык Евклида чрезвычайно невразумителен. Мышление древних греков было очень геометрическим; вместо чисел они говорили о длинах отрезков, а их доказательства состояли из изображений – приблизительно как в нашем примере с мощением пола. Но изображений недостаточно для строгих математических утверждений. Для них требуется язык алгебры, в котором буква может обозначать любое число. Именно в этом и состояло изобретение Аль-Хорезми.
Чтобы суметь ясно изложить, как работает алгоритм, нужен язык, позволяющий говорить о любом числе, не указывая, какое именно это число. Мы уже видели, как работает этот принцип, в объяснении действия алгоритма Евклида. Мы присвоили числам, которые пытались анализировать, имена – N и M. Эти переменные могут представлять любые числа. Могущество этого нового лингвистического подхода к математике состояло в том, что он позволял математикам понять грамматику, лежащую в основе операций с числами. Можно было не говорить о конкретных примерах работы того или иного метода. Новый язык алгебры дал возможность объяснять закономерности, определяющие поведение чисел. Подобно коду компьютерной программы он показывает, почему метод работает независимо от того, какие числа мы выберем, – в соответствии с третьим критерием нашего определения хорошего алгоритма.
Алгоритмы так распространились в наше время, потому что они идеально подходят для компьютеров. Алгоритм приводит нас к ответу задачи, опираясь на схему, лежащую в основе нашего метода ее решения. Компьютеру не нужно думать. Он просто снова и снова следует инструкциям, заложенным в алгоритм, и как будто по волшебству выдает нужный нам ответ.
Алгоритм длянеобитаемого острова
Один из самых замечательных алгоритмов нашего времени – это алгоритм, ежедневно помогающий миллионам людей путешествовать по интернету. Если бы я оказался на необитаемом острове и мог взять с собой только один алгоритм, я, вероятно, выбрал бы тот, который управляет поисковой системой Google (хотя толку от него было бы мало, так как у меня, скорее всего, не было бы подключения к интернету).
На заре интернета (я говорю о начале 1990-х) существовал каталог, в котором были перечислены все имеющиеся веб-сайты. В 1994 году их было всего 3000. Интернет был настолько мал, что было достаточно легко пролистать этот перечень и найти в нем то, что нужно. С тех пор ситуация сильно изменилась. Когда я начинал писать этот абзац, в интернете был 1 267 084 131 активный вебсайт. Спустя несколько предложений это число возросло до 1 267 085 440 (текущее состояние можно проверить по адресу http://www.internetlivestats.com).
Как же Google решает, какой именно из миллиардов сайтов рекомендовать? Мэри Эшвуд, 86-летняя бабушка из города Уигана[22], всегда тщательно вставляла в свои поисковые запросы вежливые «пожалуйста» и «спасибо», возможно представляя себе, что обращается к группе энергичных практикантов, которые просеивают бесконечные запросы вручную. Когда ее внук Бен открыл ее лэптоп и увидел запрос «пожалуйста переведите римское число mcmxcviii спасибо», он не смог устоять перед искушением рассказать всему миру о заблуждениях своей бабушки через твиттер. Каково же было его удивление, когда кто-то из сотрудников Google ответил на его сообщение:
Дорогая бабушка Бена,
как вы поживаете?
Вы порадовали нас в мире миллиардов поисковых запросов.
Кстати, ответ – 1998.
Спасибо ВАМ
В этом случае бабушка Бена достучалась до человеческой части Google, но компания, разумеется, никак не может лично отвечать на все те запросы, которые поступают в систему Google – по миллиону каждые 15 секунд. Но, если в Google нет волшебных эльфов, прочесывающих интернет, как же поисковой системе удается столь поразительно эффективно находить ответы, нужные пользователю?
Причина всего этого – в мощности и красоте алгоритма, который Ларри Пейдж и Сергей Брин сочинили в стэнфордском студенческом общежитии в 1996 году. Сначала они собирались назвать свой алгоритм Backrub[23], но в конце концов остановились на имени Google, от принятого в математике названия числа, равного единице со ста нулями, – «гугол» (англ. googol). Их целью было ранжировать страницы интернета, что должно было помочь в ориентировании в этой постоянно растущей базе данных, так что название огромного числа казалось вполне уместным.
Ознакомительная версия. Доступно 18 страниц из 89
