Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.11.2023
Просмотров: 176
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
БЛАГОДАРНОСТИ
Прежде всего, благодарю Мари Лафкин Ли из издательства MIT Press — ей принадлежит идея создания этой книги; Стефани Коэн, которая мягко под- гоняла меня в процессе написания; Синди Милстрейн за ее тщательную ре- дактуру и Вирджинию Кроссмэн за превосходное внимание к деталям и за- боту обо всех аспектах этой книги. Книга об алгоритмах должна войти в цикл
Essential Knowledge (необходимые знания), и я горжусь тем, что являюсь ее ав- тором.
Я признателен Диомидису Спинеллису за его комментарии к разным ча- стям книги. Отдельное спасибо Константиносу Маринакосу, который прочи- тал мой черновик, нашел ошибки, за которые мне теперь стыдно, и подска- зал, как их исправить.
Наконец, моя огромная благодарность двум подросткам, Адрианосу и Эк- тору, чьи жизни в какой-то степени будут определяться темой данной книги, и их матери, Элени; эта работа проделана благодаря им.
ЧТО ТАКОЕ АЛГОРИТМ? 13
ГЛАВА 1
ЧТО ТАКОЕ АЛГОРИТМ?
Алгоритмическая эра
Мы любим давать названия временным периодам — наверное, потому, что это позволяет нам совладать со скоротечностью времени. Поэтому мы начали говорить о настоящем как о новой алгоритмической эре, в которой алгорит- мам отводится все более важная роль. Интересно, что речь больше не идет об эпохе компьютеров или Интернета. Их мы воспринимаем как само со- бой разумеющееся. Но именно алгоритмы дают нам ощущение качествен- ного сдвига. «Вот он, всемогущий алгоритм, отрывок компьютерного кода, претендующий на высшую власть в нашу светскую эпоху, своего рода бог», — пишет Кристофер Лайдон, бывший журналист в New York Time, ведущий Radio
Open Source. И в самом деле, алгоритмы воспринимают как некую вышестоя- щую инстанцию, которая участвует в организации политических кампаний, отслеживает нашу активность онлайн, помогает нам с покупками, показы- вает рекламу, подсказывает, с кем пойти на свидание, следит за нашим здо- ровьем.
Вокруг всего этого существует аура таинственности, которая, наверное, льстит служителям алгоритмов. Должность «программиста» или «специали- ста в области информационных технологий» делает вас достойным челове- ком, хоть и технарем. Приятно принадлежать к племени, стоящему в шаге от того, чтобы перевернуть все с ног на голову, не так ли?
Алгоритмам, несомненно, свойственно нечто божественное. Как и боги, они в основном выходят сухими из воды; события случаются не из-за чело- веческой деятельности, а потому, что так решил алгоритм и с алгоритма спроса нет. Компьютеры, которые выполняют алгоритмы, превосходят чело- века во все большем количестве отраслей, поэтому кажется, что наша роль
14 ГЛАВА 1
уменьшается день ото дня; кто-то верит, что не за горами день, когда компью- теры превзойдут нас во всех аспектах умственной деятельности.
Но, если посмотреть на вещи с другой стороны, алгоритмы совсем не по- хожи на богов, и мы часто об этом забываем. Результаты, которые производят алгоритмы, не являются откровением свыше. Мы в точности знаем, каким правилам они подчиняются и какие шаги они выполняют. Каким бы чудес- ным ни был результат, его всегда можно свести к элементарным операциям.
Люди, для которых алгоритмы в новинку, могут удивиться тому, насколько тривиальными они бывают внутри. Это вовсе не умаляет их значимость; про- сто понимание того, что происходит за кулисами, снимает налет таинствен- ности. Но в то же время это позволяет по достоинству оценить, насколько эле- гантно написан алгоритм.
Идея этой книги в том, что в алгоритмах и в самом деле нет ничего та- инственного. Это инструменты, позволяющие нам легко справляться с опре- деленными задачами; они заточены на решение проблем. В этом смысле их можно считать «умственными» инструментами, включающими числа и ариф- метику. У нас ушли тысячелетия на выработку системы счисления, с помо- щью которой дети в школе могут решать математические задачи; без нее эти задачи остались бы нерешенными. Мы считаем этот навык само собой разу- меющимся, но несколько поколений назад им владела лишь небольшая часть людей.
Точно так же знание алгоритмов не должно быть прерогативой крошеч- ного элитного меньшинства; это умственные инструменты, которыми может овладеть кто угодно, а не только специалисты по компьютерам. Более того, этот навык должен быть доступен большему числу людей, так как он позво- ляет взглянуть на алгоритмы в более широком контексте: понять, что они де- лают, как они это делают и чего от них можно ожидать.
Основная цель этой книги — дать базовое понимание алгоритмов, ко- торое позволит принять полноценное участие в дискуссиях, происходящих в алгоритмическую эру. Начало этой эре мы положили сами, используя ра- нее разработанные инструменты. Изучение этих инструментов и будет темой данной книги. Алгоритмы прекрасны, и представление о том, как они созда- ются и работают, может улучшить наш собственный образ мышления.
Но для начала развеем распространенное заблуждение о том, что алго- ритмы неотделимы от компьютеров. Это так же неверно, как связывать числа с калькуляторами.
ЧТО ТАКОЕ АЛГОРИТМ? 15
Способ решения задач
Головоломки, музыка, делимость чисел и ускорители нейтронов в физике элементарных частиц — вы увидите, что у всего этого есть общий алгоритм, который применяется в разных предметных областях, но при этом основан на тех же фундаментальных принципах. Как так?
Само слово «алгоритм» не раскрывает своего значения в полной мере.
Оно происходит от имени Мухаммада ибн Мусы аль-Хорезми (ок. 783 — ок.
850), персидского ученого, который работал в областях математики, астро- номии и географии. Аль-Хорезми внес большой вклад во многие сферы науки.
Термин «алгебра» происходит от арабского названия его самой фундамен- тальной работы, «Краткая книга о восполнении и противопоставлении». Его вторая по известности работа, «Книга об индийском счете», была посвящена арифметике и переведена на латынь; именно из нее европейцы узнали об ин- до-арабской системе счисления. Имя Аль-Хорезми в латинском варианте вы- глядит как Algorismus; его стали использовать для обозначения численных методов с десятичными числами. Впоследствии термин Algorismus под влия- нием греческого слова arithmos
(ἀριθμός — число) превратился в algorithm
(алгоритм) и все так же обозначал десятичную арифметику, пока в девятна- дцатом веке не обзавелся современным значением.
Многие думают, что алгоритмы имеют какое-то отношение к компьюте- рам, но это не так. Они существовали задолго до появления компьютеров.
Первый алгоритм, о котором нам известно, существовал еще во времена древнего Вавилона. Кроме того, алгоритмы решают не компьютерные про- блемы. Они описывают, что и как нужно делать, в виде последовательности шагов. Звучит немного туманно. Вы можете спросить, о каких шагах идет речь? Мы могли бы внести ясность и дать четкое математическое определе- ние самого алгоритма и того, что он делает (оно действительно существует), но это было бы излишним. Вам, скорее всего, будет достаточно знать, что алгоритм — это набор шагов, которые можно выполнить с помощью ручки и листа бумаги; несмотря на внешнюю простоту, это определение достаточно близко к тем, которые используют математики и специалисты в области ин- форматики.
Начнем наше знакомство с алгоритмами с задачи, которую можно решить вручную. Представьте, что у нас есть два множества объектов и мы хотим как можно равномернее распределить объекты одного множества среди объек- тов другого. Объекты в первом множестве будут обозначаться как ×, а во вто- ром — как •. Мы хотим распределить крестики между точками.
Многие думают, что алгоритмы имеют какое-то отношение к компьютерам, но это не так. Они существовали задолго до появления компьютеров.
ЧТО ТАКОЕ АЛГОРИТМ? 17
Если количество крестиков точно делится на количество точек, все просто: крестики между точками достаточно разместить так, как будто мы выполняем деление. Например, если всего у нас 12 объектов, из которых три — это кре- стики, а остальные девять — точки, мы рисуем один крестик, затем три точки, затем один крестик, затем три точки и, наконец, еще один крестик и три точки.
×
×
×
• • •
• • •
• • •
Но что, если общее количество объектов нельзя точно разделить на число крестиков? Что, если крестиков у нас пять, а точек семь?
Вначале мы размещаем в один ряд все крестики и затем все точки, как по- казано ниже:
× × × × × • • • • • • •
После этого помещаем пять точек снизу от крестиков:
× × × × × • •
• • • • •
В результате справа остаются два столбца с одной точкой в каждом. Поме- стим их под двумя первыми столбцами, образуя третью строку:
× × × × ×
• • • • •
• •
Теперь можно заметить три оставшихся столбца. Два из них (крайние справа) помещаем под двумя первыми столбцами:
× × ×
× ×
• • •
• •
• •
Остается всего один лишний столбец, поэтому мы останавливаемся. Объ- единим столбцы, перемещаясь слева направо, и получим:
×
×
×
×
×
• •
•
• •
•
•
Это наш результат. Мы распределили крестики между точками. Не так равномерно, как раньше, но это закономерно, ведь, как вы помните, пять
18 ГЛАВА 1
не делится ровно на 12. Тем не менее мы избежали нагромождения крестиков и создали последовательность, которая не выглядит совсем уж бессистемной.
Вам, наверное, интересно, есть ли у этой последовательности какая-то особенность; попробуйте подставить DUM вместо крестиков и da вместо то- чек. У вас получится что-то вроде DUM-da-da-DUM-da-DUM-da-da-DUM-da-
DUM-da. Это ритм. Ритм состоит из акцентированных и тихих отрезков. Тот, который был получен выше, придумали не мы. Идея принадлежит пигмеям ака из Центральноафриканской республики; ритм под названием «Венда», ко- торый отбивают руками, служит аккомпанементом одной южноафриканской песни; аналогичный ритм встречается в Македонии и на Балканах. Но это еще не все. Если начать его со второго крестика (то есть с акцентированной части), получится следующее:
×
×
×
×
×
•
• •
•
•
• •
Это популярный ритм колоколов на Кубе и в Западной Африке, а также ба- рабанный ритм в Кении, хотя он используется и в Македонии (опять). Если начать его с третьей, четвертой или пятой акцентированной части, получатся другие ритмы, популярные в разных уголках мира.
Уникальное ли это явление? Мы можем создать 12-элементный ритм из семи акцентированных и пяти тихих частей — своеобразное зеркаль- ное отражение последовательности, которую мы рассматривали выше. Если в точности следовать той же процедуре, получится следующее:
×
× ×
×
× ×
×
•
•
•
•
•
Это тоже ритм. Он встречается в провинции Ашанти, Гана; а если его на- чать с последней акцентированной части, получится ритм, который исполь- зует народность йоруба в Нигерии, а также население Центральной Африки и Сьерра-Леоне.
Давайте расширим нашу географию. Начнем с пяти ударов и 11 тихих от- резков. Получится следующее:
×
×
×
×
×
• •
• •
• •
• •
• • •
Это ритм босанова, только немного смещенный. Оригинал начинается с третьего ударения и выглядит так: