Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

PANOS LOURIDAS
ALGORITHMS

ПАНОС ЛУРИДАС
АЛГОРИТМЫ
Самый краткий и понятный курс
• Доступное изложение
• Вся основная информация в одной книге
• Графы, алгоритмы поиска, ранжирования и многое другое

УДК 510.5
ББК 22.12
Л86
Algorithms
Panos Louridas
© 2020 Massachusetts Institute of Technology
The rights to the Russian-language edition obtained through Alexander Korzhenevski Agency (Moscow)
Луридас, Панос.
Алгоритмы. Самый краткий и понятный курс / Панос Луридас ;
[перевод с английского М. А. Райтмана]. — Москва : Эксмо, 2022. —
192 с. — (Библиотека MIT).
ISBN 978-5-04-115765-4
Если вам нужно разобраться в том, что из себя представляют алгоритмы и гра- фы, как они работают и какими бывают, эта книга для вас. Ее автор, Панос Луридас, уже много лет использует алгоритмы при проектировании программного обеспечения, криптографии, машинном обучении и является научным сотрудником Афинского университета экономики и бизнеса. Очень доступным даже для новичков языком он знакомит читателей с концепцией алгоритмов и принципами их работы — для чтения книги достаточно базового школьного образования.
УДК 510.5
ББК 22.12
Л86
ISBN 978-5-04-115765-4
© Райтман М.А., перевод на русский язык, 2022
© Оформление. ООО «Издательство «Эксмо», 2022

Мир нестабилен, но его нельзя назвать непостижимым. Главное, не забывать простое правило: все, что он выражает в виде бесчисленных жизней и существ, всегда заканчивается знаками восклицания и не носит вопросительного характера.
Карл Уве Кнаусгор. «Лето»

ОГЛАВЛЕНИЕ
Предисловие
7
Благодарности
12
Глава 1. Что такое алгоритм?
13
Глава 2. Графы
38
Глава 3. Поиск
59
Глава 4. Сортировка
74
Глава 5. PageRank
97
Глава 6. Глубокое обучение
120
Послесловие
150
Глоссарий
158
Примечания
177
Предметный указатель
183
Библиография
185
Для дальнейшего чтения
190
Об авторе
191

ПРЕДИСЛОВИЕ 7
ПРЕДИСЛОВИЕ
Я знаком с двумя подростками, которые обладают знаниями, невообрази- мыми для любых ученых, философов и исследователей прошлых веков. Это мои сыновья. Нет, я не из тех, кто любит похвастаться экстраординарными талантами своих детей. Но у этих двух парней есть карманные устройства, дающие им доступ к самому обширному хранилищу информации из когда- либо созданных. Теперь, когда они овладели искусством поиска по Интернету, нет такого фактологического вопроса, на который они не в состоянии отве- тить. Они переводят тексты с любого иностранного языка, не листая огром- ные словари (к слову, мы их не выбрасываем, чтобы наши дети знали, как все обстояло лишь несколько лет назад). Они мгновенно получают новости со всех уголков мира. Они общаются со своими сверстниками так, что вы даже не замечаете, независимо от того, какое расстояние их разделяет. Они детально планируют свои прогулки. С другой стороны, они могут тратить время на видеоигры или следовать модным тенденциям, которые меняются настолько быстро, что я даже не знаю, почему они так важны.
Все перечисленное выше стало возможным благодаря огромному про- грессу цифровых технологий. Устройства, которые мы сегодня носим в на- ших карманах, обладают большей вычислительной мощью, чем те, с чьей помощью люди добрались до Луны. Как показывает пример с этими двумя подростками, наша жизнь претерпела огромные изменения; предсказания о будущем варьируются от утопий, в которых людям больше не придется ра- ботать, до антиутопий, где горстка счастливчиков сможет наслаждаться пол- ноценной жизнью, тогда как остальные окажутся обреченными на безысход- ность. К счастью, мы сами творцы своего будущего, и важную роль в этом играет то, насколько хорошо мы владеем технологиями, лежащими в основе потенциальных свершений и изменений. Мы живем в лучший период чело- веческой истории, хотя в суете повседневной жизни об этом можно забыть.
Мы здоровее, чем когда-либо, и средняя продолжительность нашей жизни больше, чем у любого предыдущего поколения. Несмотря на несправедли- вость вопиющего неравенства, огромная часть человечества освободилась из оков нищеты. Мы еще никогда не были так близко друг к другу — как в бук- вальном, так и в виртуальном смысле. Можно сетовать на коммерциализа- цию массового глобального туризма, но дешевые путешествия позволяют нам знакомиться с другими культурами и посещать места, которыми раньше

8 ПРЕДИСЛОВИЕ
мы любовались только в иллюстрированных журналах. Весь этот прогресс может и должен продолжаться.
Но, чтобы сделать свой вклад в этот прогресс, недостаточно просто ис- пользовать цифровые технологии. В них нужно разбираться. Во-первых, по сугубо практической причине: это открывает отличные карьерные воз- можности. Во-вторых, даже если вы не планируете работать в сфере техно- логий, вам нужно понимать их основополагающие принципы; это позволит как следует оценить их потенциал и поучаствовать в их развитии. Наряду с оборудованием (компонентами, из которых состоят компьютеры и цифро- вые устройства) не менее важной частью цифровых технологий является про- граммное обеспечение — приложения, позволяющие выполнять на этом обо- рудовании ту или иную задачу. В основе приложений лежат реализуемые ими алгоритмы — наборы инструкций, которые описывают способы решения этих задач (не самое точное определение алгоритма, но не волнуйтесь: у нас есть целая книга, чтобы его уточнить). Без алгоритмов компьютеры были бы бесполезными, а все современные технологии попросту не существовали бы.
Необходимые знания меняются со временем. На протяжении значи- тельной части истории человечества образование считалось необязатель- ным. Большинство людей были неграмотными, но даже если их чему-то об- учали, то только практическим навыкам и религиозным текстам. В начале девятнадцатого века более 80% мирового населения никогда не посещало школу; теперь же большинство людей обучались в ней хотя бы несколько лет. Ожидается, что к концу этого века число необразованных людей в мире упадет до нуля. Время, которое мы тратим на обучение, тоже выросло. Если в 1940 году менее 5% американцев имели степень магистра, то в 2015-м этот показатель почти достиг трети.
В девятнадцатом веке ни в одной школе не преподавали молекулярную биологию, так как о ней еще никто не знал; ДНК открыли лишь ближе к се- редине двадцатого века. И теперь это часть любой учебной программы. Не- что похожее можно сказать об алгоритмах: их придумали еще в древние вре- мена, но до изобретения современных компьютеров ими интересовались лишь немногие. Автор этой книги убежден, что мы достигли уровня, на кото- ром алгоритмы являются одним из ключевых аспектов того, что мы считаем базовыми знаниями. Тот, кто не знает, что они представляют собой и как ра- ботают, не может оценить их потенциал и понять, как они влияют на нашу жизнь, чего от них следует ожидать, какие у них ограничения и что требу- ется для их работы. Поскольку наше общество все больше полагается на алго- ритмы, нам, как осведомленным гражданам, следует в них ориентироваться.

ПРЕДИСЛОВИЕ 9
Наряду с оборудованием (компонентами, из которых состоят компью- теры и цифровые устройства) не менее важной частью цифровых техноло- гий является программное обеспечение — приложения, позволяющие выпол- нять на этом оборудовании ту или иную задачу. В основе приложений лежат реализуемые ими алгоритмы.
Изучение алгоритмов может иметь и другие преимущества. Если мате- матика знакомит нас с формальным видом мышления, знание алгоритмов позволяет рассуждать о вещах новым, алгоритмическим образом, направ- ленным на практическое решение задач. Благодаря этому эффективные реа- лизации алгоритмов в виде программ могут быстро выполняться на компью- терах. Подход, в котором акцент делается на практичных и эффективных процессах проектирования, может пригодиться не только профессиональ- ным программистам.
Эта книга призвана познакомить с алгоритмами читателя, далекого от компьютерных наук, и объяснить ему, как они работают. Мы не стремимся показать, как алгоритмы влияют на наши жизни, — с этим отлично справ- ляются другие книги, в которых речь идет о том, как прогресс в обработке больших данных, искусственный интеллект и повсеместное внедрение вы- числительных устройств могут изменить человеческую природу. Нас в пер- вую очередь интересует не то, что может произойти в будущем, а, скорее, как это может случиться. Для этого мы представим здесь настоящие алгоритмы и покажем не только то, что они делают, но и принцип их работы. Вместо об- щих фраз вас ждут подробные объяснения.
Знание алгоритмов позволяет рассуждать о вещах новым, алгоритми- ческим образом, направленным на практическое решение задач. Благодаря этому эффективные реализации алгоритмов в виде программ могут быстро выполняться на компьютерах.
На вопрос «что такое алгоритм?» есть удивительно простой ответ. Это определенный способ решения задачи, который можно описать в виде про- стых шагов и затем выполнить на компьютере с поразительной скоростью и эффективностью. Однако в таких решениях нет ничего волшебного. Тот факт, что они состоят из элементарных шагов, означает, что в них способны разобраться большинство людей.
На самом деле для чтения этой книги достаточно знаний, полученных в средней школе. Конечно, в некоторых главах есть немного математики, так как невозможно рассуждать об алгоритмах вообще без формул и формаль- ных обозначений. В тексте объясняются любые концепции, распространен- ные в мире алгоритмов, но малоизвестные за пределами компьютерных наук.

10 ПРЕДИСЛОВИЕ
Вот что написал недавно скончавшийся физик во введении в свою самую популярную книгу, «Краткая история времени», изданную в 1988 году: «Мне сказали, что каждая включенная в книгу формула уменьшит число покупа- телей вдвое». Это звучит довольно угрожающе для настоящей книги, так как математика в ней встречается не раз. Но я решил не обращать на это внима- ние по двум причинам. Во-первых, для понимания физики Хокинга требуется знание математики университетского уровня; здесь все намного доступнее.
Во-вторых, эта книга призвана показать не только назначение алгоритмов, но и то, как они работают внутри, поэтому читателю должны быть знакомы некоторые термины, используемые здесь, в том числе математические. Си- стема обозначений не является прерогативой технической интеллигенции, и владение ею поможет развеять ореол загадочности, окружающий данную тему; в конце вы увидите, что это в основном сводится к умению рассуждать о вещах четко и поддающимся измерению способом.
Книга вроде этой не может полностью охватить тему алгоритмов, но мы попытаемся провести краткий обзор и познакомить читателя с алгоритми- ческим образом мышления. Основа будет заложена в первой главе, из нее вы узнаете, что такое алгоритмы и как измерить их эффективность. Сразу отметим, что алгоритм — это конечная последовательность шагов, которые можно выполнить с помощью ручки и листа бумаги, и это простое опреде- ление не так уж далеко от истины. Дальше в главе 1 будет исследована взаи- мосвязь между алгоритмами и математикой. Отличаются же они практич- ностью: при написании алгоритмов нас интересуют прикладные способы решения задач. Это означает, что нам нужно как-то оценивать практичность и эффективность наших алгоритмов. Вы увидите, что эти аспекты можно рас- сматривать в строго очерченных рамках вычислительной сложности; именно в этом контексте будет проходить обсуждение алгоритмов на страницах дан- ной книги.
Следующие три главы посвящены трем наиболее важным сферам приме- нения алгоритмов. В главе 2 рассматриваются алгоритмы для решения задач, связанных с сетями, известными как графы. В число этих задач входит по- иск маршрута на дороге или последовательности звеньев, соединяющих вас с другими людьми в социальной сети. Сюда же отнесем задачи из других обла- стей с не такими очевидными связями: секвенирование ДНК и планирование соревнований; это проиллюстрирует тот факт, что разного рода задачи могут быть эффективно решены с помощью одних и тех же инструментов.
В главах 3 и 4 вы узнаете, как искать и упорядочивать элементы. Тема мо- жет показаться прозаической, но она одна из самых важных с точки зрения

практического применения компьютеров. Компьютеры тратят много вре- мени на сортировку и поиск, однако мы редко обращаем на это внимание, поскольку указанные операции — неотъемлемая и невидимая часть боль- шинства приложений. Сортировка и поиск даже дают некоторое представ- ление о важном аспекте алгоритмов. Многие задачи можно решать разными способами. Выбор подходящего алгоритма зависит от его характеристик; не- которые алгоритмы больше подходят для определенных задач, чем другие.
Поэтому вам полезно увидеть, как разные алгоритмы с разными характери- стиками справляются с решением одной и той же задачи.
В следующих двух главах представлены важные способы применения ал- горитмов в широких масштабах. В главе 5 мы снова вернемся к графам, чтобы объяснить алгоритм, который можно применять для ранжирования веб-стра- ниц в порядке их значимости. PageRank использовался компанией Google в момент ее основания. Успех этого алгоритма в ранжировании результатов поиска сыграл ключевую роль в феноменальном успехе Google как компании.
К счастью, разобраться в его работе не так уж сложно. Это позволит увидеть, как алгоритмы справляются с задачей, которую, на первый взгляд, нельзя ре- шить с помощью компьютеров: как оценить важность тех или иных вещей?
В главе 6 будет представлена одна из самых динамично развивающихся об- ластей компьютерных наук: нейронные сети и глубокое обучение. Об успеш- ном применении нейронных сетей можно узнать даже из популярных средств массовой информации. Наибольший интерес проявляется к сюжетам о систе- мах, которые выполняют такие задачи, как анализ изображений, автоматиче- ский перевод и медицинская диагностика. Мы начнем с отдельных нейронов и постепенно перейдем к построению все больших и больших нейронных се- тей, способных выполнять все более сложные задачи. Вы увидите, что все они основаны на общих фундаментальных принципах. Их эффективность объяс- няется взаимосвязанностью множества простых компонентов и примене- нием алгоритма, который позволяет нейронным сетям учиться.
Вслед за демонстрацией возможностей алгоритмов идет послесловие, по- священное тому, как ограничены компьютерные вычисления. Мы знаем, что компьютеры способны на многое, и ожидаем от них еще большего, но есть вещи, которые им не под силу. Обсуждение пределов их возможностей позво- лит более точно объяснить природу алгоритмов и вычислений. Мы уже гово- рили, что алгоритм можно описать в виде конечной последовательности ша- гов, которые можно выполнить с помощью ручки и листа бумаги, но какими могут быть эти шаги? И насколько близка аналогия с ручкой и бумагой к на- стоящим алгоритмам?