Алгоритмы разработка и применение. Клейнберг Дж., Тардос Е

Алгоритмы: разработка и применение. Клейнберг Дж., Тардос Е.

СПб.: 2016. - 8 00 с.

Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов. Алгоритмы - это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных. Вы познакомитесь с базовыми аспектами построения алгоритмов, основными понятиями и определениями, структурами данных, затем перейдете к основным методам построения алгоритмов, неразрешимости и методам решения неразрешимых задач, и, наконец, изучите рандомизацию при проектировании алгоритмов. Самые сложные темы объясняются на четких и простых примерах, поэтому книга может использоваться как для самостоятельного изучения студентами, так и учеными-исследователями или профессионалами в области компьютерных технологий, которые хотят получить представление о применении тех или иных методов проектирования алгоритмов.
Алгоритмический анализ состоит из двух фундаментальных компонентов: выделения математически чистого ядра задачи и выявления методов проектирования подходящего алгоритма на основании структуры задачи. И чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быстрее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира.

Формат: pdf

Размер: 11 ,5 Мб

Скачать: drive.google

Краткое содержание
Глава 1. Введение: некоторые типичные задачи 27
Глава 2. Основы анализа алгоритмов 56
Глава 3. Графы 98
Глава 4. Жадные алгоритмы 137
Глава 5. Разделяй и властвуй 226
Глава 6. Динамическое программирование 266
Глава 7. Нахождение потока в сети 347
Глава 8. Л/Р-полнота и вычислительная неразрешимость 458
Глава 9. PSPACE: класс задач за пределами NP 534
Глава 10. Расширение пределов разрешимости 555
Глава 11. Аппроксимирующие алгоритмы 599
Глава 12. Локальный поиск 659
Глава 13. Рандомизированные алгоритмы 704

Алгоритмические идеи вездесущи, а широта их применения наглядно проявляется в примерах как из области информатики, так и за ее пределами. Некоторые серьезные изменения стандартов маршрутизации в Интернете произошли вследствие обсуждения недостатков одного алгоритма кратчайшего пути и относительных преимуществ другого. Базовые понятия, используемые биологами для выражения сходства между генами и геномами, имеют алгоритмические определения. Озабоченность, высказываемая экономистами в контексте практической приемлемости комбинаторных аукционов, отчасти обусловлена тем фактом, что особыми случаями таких аукционов являются вычислительно трудноразрешимые задачи поиска. При этом алгоритмические концепции не ограничиваются хорошо известными, устоявшимися задачами; эти идеи регулярно проявляются в совершенно новых проблемах, возникающих в самых разных областях. Ученый из Yahoo!, однажды рассказавший нам за обедом о системе поставки рекламы пользователям, описывал совокупность задач, которые, по сути, можно было смоделировать как задачу нахождения потока в сети. То же произошло в общении с нашим бывшим студентом (ныне консультантом по вопросам управления, занимающимся правилами подбора персонала для крупных больниц), с которым мы встретились во время поездки в Нью-Йорк.

Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов. Алгоритмы - это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных.
Вы познакомитесь с базовыми аспектами построения алгоритмов, основными понятиями и определениями, структурами данных, затем перейдете к основным методам построения алгоритмов, неразрешимости и методам решения неразрешимых задач, и. наконец, изучите рандомизацию при проектировании алгоритмов.
Самые сложные темы объясняются на четких и простых примерах, поэтому книга может использоваться как для самостоятельного изучения студентами, так и учеными-исследователями или профессионалами в области компьютерных технологий, которые хотят получить представление о применении тех или иных методов проектирования алгоритмов.
Алгоритмический анализ состоит из двух фундаментальных компонентов: выделения математически чистого ядра задачи и выявления методов проектирования подходящего алгоритма на основании структуры задачи. И чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быстрее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира.

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

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

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

Содержание
Глава 1. Введение: некоторые типичные задачи
Глава 2. Основы анализа алгоритмов
Глава 3. Графы
Глава 4. Жадные алгоритмы
Глава 5. Разделяй и властвуй
Глава 6. Динамическое программирование
Глава 7. Нахождение потока в сети
Глава 8. NР-полнота и вычислительная неразрешимость
Глава 9. PSPACE: класс задач за пределами NP
Глава 10. Расширение пределов разрешимости
Глава 11. Аппроксимирующие алгоритмы
Глава 12. Локальный поиск
Глава 13. Рандомизированные алгоритмы.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Алгоритмы, Разработка и применение, Классика Computers Science, Клейнберг Д., Тардос Е., 2016 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.

Привет, Хаброжители! У нас вышла новинка:

Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов. Алгоритмы - это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных.

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

Алгоритмический анализ состоит из двух фундаментальных компонентов: выделения математи-чески чистого ядра задачи и выявления методов проектирования подходящего алгоритма на осно-вании структуры задачи. И чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быст-рее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира.

Алгоритмические задачи образуют ядро компьютерной науки, однако они редко появляются в виде аккуратно упакованных, математи-чески точных вопросов. Чаще они отягощаются множеством хлопотных подробностей, привязанных к конкретному случаю; одни из этих подробностей важны, другие избыточны. В результате алгоритмический анализ состоит из двух фундаментальных компонентов: выде-ления математически чистого ядра задачи и выявления методов проектирования подходящего алгоритма на основании структуры зада-чи. Эти два компонента взаимосвязаны: чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быст-рее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира. Таким образом, при ис-пользовании с максимальной эффективностью алгоритмические идеи не просто предоставляют решения четко поставленных задач - они формируют язык для четкого выражения вопросов, заложенных в их основу.

Цель этой книги - донести до читателя этот подход к алгоритмам в форме процесса проектирования, который начинается с задач, встречающихся по всему диапазону вычислительных приложений, использует хорошее понимание методов проектирования алгоритмов и конечным результатом которого является разработка эффективных решений таких задач. Мы будем изучать роль алгоритмических идей в компьютерной науке вообще и постараемся связать эти идеи с диапазоном точно сформулированных задач, для решения кото-рых проектируются и анализируются алгоритмы. Иначе говоря, какие причины заставляют нас искать решение этих задач и как мы выбираем конкретные способы их формулировки? Как мы узнаем, какие принципы проектирования уместны в той или иной ситуации?

Исходя из сказанного, мы постарались показать, как выявлять «чистые» формулировки алгоритмических задач в сложных вычислитель-ных областях и как на базе этих формулировок проектировать эффективные алгоритмы для решения полученных задач. Чтобы разоб-раться в сложном алгоритме, часто бывает проще всего реконструировать последовательность идей (включая неудачные заходы и тупи-ки), которые привели от исходных упрощенных методов к выработанному со временем решению. Так сформировался стиль изложения, не приводящий читателя от постановки задачи сразу к алгоритму и, на наш взгляд, лучше отражающий то, как мы и наши коллеги под-ходим к решению подобных задач.

Общие сведения

Книга предназначена для студентов, прошедших двухсеместровый вводный курс вычислительных технологий (стандартный курс «CS1/CS2»), в ходе которого они писали программы для реализации базовых алгоритмов, и работы с такими структурами данных, как деревья и графы, а также с базовыми структурами данных (массивы, списки, очереди и стеки). Так как переход между этим курсом и первым курсом по алгоритмам еще не стал стандартным, книга открывается с изложения тем, которые знакомы студентам некоторых образовательных учреждений по курсу CS1/CS2, но в других учреждениях включаются в учебный план первого курса по алгоритмам. Соответственно, эта часть может рассматриваться либо как обзор, либо как новый материал; включая ее, мы надеемся, что книга может быть использована в более широком диапазоне учебных курсов и с большей гибкостью в отношении исходных знаний, обязательных для читателя.

В соответствии с описанным подходом мы разрабатываем базовые методы проектирования алгоритмов, изучая задачи из многих облас-тей компьютерной науки и сопутствующих областей. В частности, приводятся довольно подробные описания возможных применений из области систем и сетей (кэширование, коммутация, междоменная маршрутизация в Интернете), искусственного интеллекта (планирова-ние, игры, сети Хопфилда), распознавание образов (сегментация изображений), извлечение информации (обнаружение точки перехо-да, кластеризация), исследование операций (планирование воздушного движения) и вычислительная биология (выравнивание последо-вательностей, вторичная структура РНК).

Понятие вычислительной неразрешимости и NP-полноты в частности играет значительную роль в книге. Это соответствует нашему под-ходу к общему процессу проектирования алгоритма. Иногда интересная задача, возникающая в практической области, имеет эффек-тивное решение, а иногда она оказывается доказуемо NP-полной; для полноценного подхода к решению новой алгоритмической задачи вы должны уметь исследовать оба варианта с равной уверенностью. Поскольку очень многие естественные задачи в компьютерной нау-ке являются NP-полными, разработка механизмов работы с неразрешимыми задачами стала ключевым фактором изучения алгоритмов, и эта тема широко представлена в книге. Вывод о том, что задача является NP-полной, следует воспринимать не как конец исследова-ния, а как приглашение к поиску алгоритмов приближения, методов эвристического локального поиска или разрешимых особых слу-чаев. Каждый из этих трех подходов широко рассматривается в книге.

Чтобы упростить работу с такими задачами, в каждую главу включается раздел «Упражнения с решениями», в котором мы берем одну или несколько задач и подробно описываем процесс поиска решения. По этой причине обсуждение каждого упражнения с решением получается намного длиннее, чем простая запись полного, правильного решения (другими словами, намного длиннее, чем было необ-ходимо для полноценного решения, если бы эта задача была задана студенту для самостоятельного решения). Как и в остальном тексте книги, обсуждения в этих разделах должны дать читателю представление о более масштабных процессах, применяемых для решения задач такого типа и в конечном итоге приводящих к точному решению.

Стоит упомянуть еще два обстоятельства, связанных с использованием этих задач для самостоятельной работы в учебных курсах. Во-первых, задачи упорядочены приблизительно по возрастанию сложности, но это всего лишь приблизительный ориентир, и мы не сове-туем уделять ему слишком много внимания; так как основная часть задач была разработана для самостоятельной работы студентов, большие подмножества задач в каждой главе довольно тесно связаны в отношении сложности. Во-вторых, если не считать начальных глав, над решением этих задач придется потрудиться - как для того, чтобы связать описание задачи с алгоритмическими методами, описанными в главе, так и для непосредственного проектирования алгоритма. В своем учебном курсе мы назначали около трех таких задач на неделю.

Учебные аспекты и дополнения

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

Как упоминалось ранее, многие разделы в книге посвящены формулировке алгоритмической задачи (включая ее историю и мотивацию для поиска решения), проектированию и анализу алгоритма для ее решения. В соответствии с этим стилем такие разделы имеют еди-ную структуру, включающую последовательность подразделов: «Задача» с описанием задачи и ее точной формулировкой; «Проекти-рование алгоритма» с применением подходящих методов для разработки алгоритма; и «Анализ алгоритма» с доказательством свойств алгоритма и анализом его эффективности. В тех случаях, где рассматриваются расширения задачи или приводится дополнительный анализ алгоритма, включаются дополнительные подразделы. Целью такой структуры является введение относительно общего стиля изложения, который переходит от исходного обсуждения проблемы, возникающей в вычислительной области, к подробному анализу методов ее решения.

Глава 1 начинается с представления некоторых типичных алгоритмических задач. Мы начнем с задачи устойчивых паросочетаний, пото-му что она позволяет обозначить базовые аспекты разработки алгоритмов более конкретно и элегантно, чем любые абстрактные рас-суждения: поиск устойчивых паросочетаний обусловлен естественной, хотя и сложной практической областью, на базе которой можно абстрагировать интересную формулировку задачи и неожиданно эффективный алгоритм ее решения. В оставшейся части главы 1 рас-сматриваются пять «типичных задач», которые предопределяют темы из оставшейся части курса. Эти пять задач взаимосвязаны в том смысле, что все они могут рассматриваться как вариации и/или особые случаи задачи поиска независимого множества; но одна задача может быть решена при помощи «жадного» алгоритма, другая - методом динамического программирования, третья - методом нахож-дения потока в сети, четвертая (собственно задача независимого множества) является NP-полной, а пятая - PSPACE-полной. Тот факт, что тесно связанные задачи могут значительно отличаться по сложности, играет важную роль в книге, и эти пять задач служат ориен-тирами, к которым мы неоднократно возвращаемся по мере изложения материала.

Главы 2 и 3 помогают связать материал с учебным курсом CS1/CS2, о котором говорилось выше. В главе 2 вводятся ключевые мате-матические определения и понятия, используемые при анализе алгоритмов, а также мотивация для их применения. Глава начинается с неформального обзора того, что же следует понимать под вычислительной разрешимостью задачи, а также концепцией полиномиаль-ного времени как формального критерия эффективности. Затем вопросы скорости роста функций и асимптотического анализа рассмат-риваются более формально, приводится информация по функциям, часто встречающимся при анализе алгоритмов, а также по их стан-дартным применениям. В главе 3 рассматриваются базовые определения и алгоритмические примитивы, необходимые для работы с графами и занимающие центральное место во многих задачах книги. К концу учебного курса CS1/CS2 студенты реализуют многие ба-зовые алгоритмы теории графов, но этот материал полезно представить здесь в более широком контексте проектирования алгоритмов. В частности, мы рассмотрим базовые определения графов, методы обхода графов (обход в ширину и обход в глубину) и основные концепции направленных графов, включая сильную связность и топологическое упорядочение.

В главах 2 и 3 также представлены многие базовые структуры данных, используемые при реализации алгоритмов в книге; более слож-ные структуры данных описаны в последующих главах. Наш подход к структурам данных заключается в том, чтобы представлять их тогда, когда они потребуются для реализации алгоритмов, описанных в книге. Таким образом, хотя многие структуры данных уже бу-дут знакомы студентам по курсу CS1/CS2, мы будем рассматривать их в более широком контексте проектирования и анализа алгорит-мов.

В главах 4–7 рассматриваются четыре основных метода проектирования алгоритмов: жадные алгоритмы, принцип «разделяй и власт-вуй», динамическое программирование и нахождение потока в сети. С жадными алгоритмами важно понять, когда они работают, а когда нет; наше рассмотрение этой темы базируется на способе классификации алгоритмов, используемых для доказательства пра-вильности работы жадных алгоритмов. Глава завершается обзором основных применений жадных алгоритмов для поиска кратчайших путей, направленных и ненаправленных связующих деревьев, группировки и сжатия. Обсуждение метода «разделяй и властвуй» на-чинается с обзора стратегий рекуррентных соотношений как границ времени выполнения; затем мы покажем, как знание этих рекур-рентных соотношений может управлять проектированием алгоритмов, превосходящих прямолинейные решения многих базовых задач, включая сравнение оценок, нахождение ближайших пар точек на плоскости и быстрое преобразование Фурье. Знакомство с динами-ческим программированием начинается с интуитивно понятной рекурсии, на которой оно базируется, с последующей разработкой все более и более выразительных формул через приложения, в которых они естественным образом встречаются. Наконец, мы рассмотрим алгоритмы для задач нахождения потока в сети; большая часть этой главы будет посвящена разнообразным практическим примене-ниям этих потоков. В том объеме, в котором потоки в сети рассматриваются в алгоритмических учебных курсах, студенты часто недос-таточно хорошо представляют широкий спектр задач, к которым они могут применяться; мы постараемся воздать должное их гибкости и представим применение потоков для распределения загрузки, планирования, сегментации изображений, а также ряда других задач.

Главы 8 и 9 посвящены понятию вычислительной неразрешимости. Основное внимание в них уделяется NP-полноте; базовые NP-пол-ные задачи разбиваются на категории, чтобы помочь студентам в идентификации возможных сокращений при обнаружении новых задач. Мы дойдем до достаточно сложных доказательств NP-полноты, с рекомендациями относительно того, как следует подходить к построению сложных сокращений. Также будут рассмотрены типы вычислительной сложности, выходящие за рамки NP-полноты, осо-бенно в области PSPACE-полноты. Эта полезная концепция подчеркивает, что неразрешимость не кончается на NP-полноте; PSPACE-полнота также закладывает фундамент для центральных понятий из области искусственного интеллекта (планирования и ведения игр), которые без нее не нашли бы отражения в рассматриваемой алгоритмической области.

В главах с 10-й по 12-ю рассматриваются три основных метода работы с вычислительно неразрешимыми задачами: идентификация структурированных особых случаев, алгоритмы аппроксимации и эвристики локального поиска. Глава, посвященная разрешимым осо-бым случаям, показывает, что экземпляры NP-полных задач, встречающиеся на практике, могут быть не столь сложны в худших слу-чаях, потому что нередко они содержат структуру, которая может быть использована при проектировании эффективного алгоритма. Мы покажем, что NP-полные задачи часто удается эффективно решить, если ограничиться входными данными, имеющими структуру дере-ва. Тема завершается подробным обсуждением декомпозиций графов в дерево. Хотя эта тема больше подходит для выпускных учебных курсов, она имеет существенную практическую ценность, для которой трудно найти более доступный материал. В главе, посвященной алгоритмам аппроксимации, рассматривается процесс проектирования эффективных алгоритмов и задача анализа оптимального реше-ния для построения хороших оценок. Что касается методов проектирования алгоритмов аппроксимации, мы сосредото-чимся на жадных алгоритмах, линейном программировании и третьем методе, который будет называться «определение цены» (pricing), использующим идеи первых двух. Наконец, мы рассмотрим эвристики локального поиска, включая алгоритм Метрополиса и метод модельной «закал-ки». Эта тема часто не рассматривается в алгоритмических курсах среднего уровня, потому что о доказуемых гаран-тиях таких алго-ритмов известно очень мало; однако, учитывая их широкое практическое распространение, мы считаем, что студентам будет полезно знать о них. Также включаются описания случаев, для которых существуют доказуемые гарантии.

В главе 13 рассматривается применение рандомизации при проектировании алгоритмов. На эту тему написано несколько хороших книг. Здесь мы постараемся предоставить более компактное введение в некоторые способы применения методов рандомизации, осно-ванные на информации, которая обычно входит в учебные курсы дискретной математики среднего уровня.

Исследования Клейнберга посвящены алгоритмам, прежде всего связанным со структурой сетей и информации, и их практическим применениям в области компьютерных технологий, оптимизации, анализа данных и вычислительной биологии. Его работы по теме сетевого анализа помогли заложить основу современного поколения поисковых систем Интернета.

Ева Тардос (Eva Tardos) - профессор теории вычислительных систем в Корнелльском университете. Получила докторскую степень в Университе Этвёша в Будапеште (Венгрия) в 1984 году. Член Американской академии наук и искусств и Ассоциации по вычислитель-ной технике США.

Научные интересы Тардос связаны с проектированием и анализом алгоритмов для решения задач из теории графов и сетей. Наибольшую известность получили ее работы в области алгоритмов сетевого потока и аппроксимирующих алгоритмов для решения сетевых задач. Ее недавние работы были посвящены алгоритмической теории игр.

Более подробно с книгой можно ознакомиться на

Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов. Алгоритмы - это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных.
Вы познакомитесь с базовыми аспектами построения алгоритмов, основными понятиями и определениями, структурами данных, затем перейдете к основным методам построения алгоритмов, неразрешимости и методам решения неразрешимых задач, и, наконец, изучите рандомизацию при проектировании алгоритмов.
Самые сложные темы объясняются на четких и простых примерах, поэтому книга может использоваться как для самостоятельного изучения студентами, так и учеными-исследователями или профессионалами в области компьютерных технологий, которые хотят получить представление о применении тех или иных методов проектирования алгоритмов. Алгоритмический анализ состоит из двух фундаментальных компонентов: выделения математически чистого ядра задачи и выявления методов проектирования подходящего алгоритма на основании структуры задачи. И чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быстрее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира.

1. Введение: некоторые типичные задачи
2. Основы анализа алгоритмов
3. Графы
4. Жадные алгоритмы
5. Разделяй и властвуй
6. Динамическое программирование
7. Нахождение потока в сети
8. NP-полнота и вычислительная неразрешимость
9. PSPACE: класс задач за пределами NP
10. Расширение пределов разрешимости
11. Аппроксимирующие алгоритмы
12. Локальный поиск
13. Рандомизированные алгоритмы
Эпилог: алгоритмы, которые работают бесконечно

Основы анализа алгоритмов

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

Затем мы разработаем граничные оценки времени выполнения некоторых базовых алгоритмов, начиная с реализации алгоритма Гейла–Шепли из главы 1. Далее в обзор будут включены оценки времени выполнения и некоторые специфические характеристики алгоритмов, обеспечивающие это время выполнения. В некоторых случаях достижение хорошего времени выполнения зависит от использования более сложных структур данных, и в конце главы будет рассмотрен очень полезный пример такой структуры данных: приоритетные очереди и их реализация на базе кучи (heap).

Вычислительная разрешимость

Главной темой является поиск эффективных алгоритмов для вычислительных задач. На таком уровне общности к этой теме вроде бы можно отнести всю область компьютерных вычислений; чем же наш подход будет отличаться от других?

Сначала мы попробуем выявить общие темы и принципы проектирования при разработке алгоритмов. Нас будут интересовать парадигматические задачи и методы, которые с минимумом второстепенных подробностей будут демонстрировать базовые методы проектирования эффективных алгоритмов. Бессмысленно обсуждать эти принципы проектирования «в вакууме», поэтому рассматриваемые задачи и методы почерпнуты из фундаментальных в компьютерной науке тем, а общее изучение алгоритмов дает неплохое представление о вычислительных концепциях, встречающихся во многих областях.

Динамическое программирование

Наше изучение алгоритмических методов началось с жадных алгоритмов, которые в определенном смысле представляют наиболее естественный подход к разработке алгоритма. Как вы видели, столкнувшись с новой вычислительной задачей, иногда можно легко предложить для нее несколько возможных жадных алгоритмов; проблема в том, чтобы определить, дают ли какие-либо из этих алгоритмов верное решение задачи во всех случаях.

Все задачи из главы 4 объединял тот факт, что в конечном итоге действительно находился работающий жадный алгоритм. К сожалению, так бывает далеко не всегда; для большинства задач настоящие трудности возникают не с выбором правильной жадной стратегии из несколько вариантов, а с тем, что естественного жадного алгоритма для задачи вообще не существует. В таких случаях важно иметь наготове другие методы. Принцип «разделяй и властвуй» иногда выручает, однако реализации этого принципа, которые мы видели в предыдущей главе, часто недостаточно эффективны для сокращения экспоненциального поиска «грубой силой» до полиномиального времени. Как было замечено в главе 5, его применения чаще позволяют сократить излишне высокое, но уже полиномиальное время выполнения до более быстрого.

Мы обратимся к более мощному и нетривиальному методу разработки алгоритмов - динамическому программированию. Охарактеризовать динамическое программирование будет проще после того, как вы увидите его в действии, но основная идея базируется на интуитивных представлениях, лежащих в основе принципа «разделяй и властвуй», и по сути противоположна жадной стратегии: алгоритм неявно исследует пространство всех возможных решений, раскладывает задачу на серии подзадач, а затем строит правильные решения подзадач все большего размера. В некотором смысле динамическое программирование может рассматриваться как метод, работающий в опасной близости от границ перебора
«грубой силой»: хотя оно систематически прорабатывает большой набор возможных решений задачи, это делается без явной проверки всех вариантов. Именно из-за этой необходимости тщательного выдерживания баланса динамическое программирование бывает трудно освоить; как правило, вы начинаете чувствовать себя уверенно только после накопления немалого практического опыта.

Аппроксимирующие алгоритмы

После обсуждения NP-полноты и концепции вычислительной неразрешимости в целом мы начали искать ответ на фундаментальный вопрос: как разрабатывать алгоритмы для задач, у которых полиномиальное время, скорее всего, является недостижимым?

Мы займемся новой темой, связанной с этим вопросом: аппроксимирующие алгоритмы выполняются за полиномиальное время и находят решения, гарантированно близкие к оптимальным. В этом определении следует обратить внимание на ключевые слова: гарантированно и близкие. Мы не пытаемся искать оптимальное решение, и в результате появляется возможность достичь полиномиального времени выполнения. В то же время нужно будет доказывать, что алгоритмы находят решения, гарантированно близкие к оптимуму. Эта задача весьма непростая по своей природе: чтобы доказать гарантию аппроксимации, необходимо сравнить решение с оптимальным решением, которое очень трудно найти (и, возможно, привести обоснование). Данная проблема неоднократно встречается при анализе алгоритмов.

Здесь рассматриваются четыре общие методологии разработки аппроксимирующих алгоритмов. Мы начнем с жадных алгоритмов, аналогичных тем, что разрабатывались в главе 4. Эти алгоритмы быстры и просты, как и в главе 4, поэтому основная проблема связана с поиском жадного правила, приводящего к решению, доказуемо близкого к оптимальному. Второй общий метод - метод назначения цены - имеет экономическую подоплеку; мы рассматриваем цену, которую необходимо уплатить за соблюдение каждого ограничения в задаче. Метод назначения цены часто называется прямо-двойственным методом (primaldual) - термин происходит из области линейного программирования, которое тоже может использоваться в этой области. Описание метода назначения цены не требует знакомства с линейным программированием, которое будет представлено в третьей категории - линейном программировании с округлением, использующем отношения между вычислительной разрешимостью линейного программирования и выразительной мощью его «более сложного» родственника, целочисленного программирования. В завершение будет описан метод, приводящий к исключительно качественным аппроксимациям: применение динамического программирования к округленной версии входных данных.

Рандомизированные алгоритмы

Идея «случайности» процесса не нова; само понятие возникло давно в истории человеческой мысли. Оно отражено в азартных играх и страховом деле - и то и другое происходит из древних времен. Но хотя столь же интуитивно понятные дисциплины, такие как геометрия или логика, изучаются математическими методами уже несколько тысяч лет, область математического изучения вероятности на удивление молода; первые попытки ее серьезной формализации были предприняты в XVII веке. Конечно, компьютерная наука существует на много меньшем историческом отрезке, и случайности в ней уделяется внимание с первых дней.

Темы рандомизация и вероятностного анализа проникают во многие области компьютерной науки, включая разработку алгоритмов, и когда речь заходит о случайных процессах в контексте вычислений, обычно имеется в виду одна из двух точек зрения. Первая рассматривает случайное поведение реального мира: здесь часто изучаются традиционные алгоритмы, сталкивающиеся со случайно сгенерированными входными данными. Такие методы часто называются анализом среднего случая, потому что поведение алгоритма изучается на «средних» входных данных (подвергнутых воздействию некоторого случайного процесса) вместо худшего случая.

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

Чем может быть полезен алгоритм, принимающий случайные решения? Вопервых, рандомизация расширяет возможности используемой модели. Эффективные детерминированные алгоритмы, которые всегда дают правильный ответ, могут рассматриваться как особый случай эффективных рандомизированных алгоритмов, которые дают правильный ответ с очень высокой вероятностью; они также являются особым случаем рандомизированных алгоритмов, которые всегда работают правильно и при этом, как ожидается, выполняются эффективно. Даже при получении худших входных данных алгоритм, выполняющий свою «внутреннюю» рандомизацию, может компенсировать некоторые нежелательные аспекты худшего случая. Следовательно, задачи, которые не решаются эффективными детерминированными алгоритмами, могут не устоять перед рандомизированными алгоритмами.

Но это еще не все. Мы рассмотрим рандомизированные алгоритмы для некоторых задач, для которых существуют сравнительно эффективные детерминированные алгоритмы. Даже в таких ситуациях рандомизация часто проявляет немалую мощь: например, она может быть концептуально проще или она может обеспечить функционирование алгоритма при минимальных потребностях в хранении внутреннего состояния или информации о прошлых событиях. Преимущества рандомизации расширяются при рассмотрении крупных компьютерных систем и сетей с множеством гибких взаимодействий между процессами, другими словами, в распределенных системах. Здесь случайное поведение части отдельных
процессов может сократить объем необходимого обмена информации или синхронизации; рандомизация часто оказывается ценным инструментом для нарушения симметрии между процессами, снижающим вероятность конфликтов и появления «горячих точек». Многие из примеров будут взяты из ситуаций такого рода: управление доступом к общему ресурсу, распределение нагрузки по нескольким процессорам, маршрутизация пакетов в сети и т. д. Даже небольшой опыт работы с рандомизированными эвристиками может сильно пригодиться при анализе больших систем.

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

Эпилог: алгоритмы, которые работают бесконечно

У каждого десятилетия свои увлекательные головоломки; и если в начале 1980-х годов бесспорное первое место среди математических развлечений занимал кубик Рубика, то «Тетрис» вызывает похожее чувство ностальгии по концу 80-х и началу 90-х годов. У кубика Рубика и «Тетриса» есть кое-что общее: математический оттенок, базирующийся на стилизованных геометрических формах, - но пожалуй, различия между ними представляют еще больший интерес.

Кубик Рубика - игра, сложность которой определяется огромным пространством поиска; к заданной перемешанной конфигурации кубика требуется применить серию операций, чтобы достичь конечной цели. С другой стороны, «Тетрис» (в его «чистой» форме) имеет куда более размытое определение успеха; вместо конкретной конечной точки вы сталкиваетесь с бесконечным потоком событий, на которые необходимо непрерывно реагировать.

Эти отличительные признаки «Тетриса» напоминают аналогичные темы, проявившиеся в недавних работах по анализу алгоритмов. Все чаще встречаются ситуации, в которых традиционные представления об алгоритмах - в начале выполнения алгоритм получает входные данные, выполняется за конечное количество шагов и выдает результат - уже неприменимы. Попробуйте представить себе маршрутизаторы в Интернете, которые передают пакеты и пытаются избежать перегрузок; или децентрализованные механизмы обмена файлами, которые копируют и распространяют контент по требованию пользователей; или средства машинного обучения, формирующие прогностические модели концепций, изменяющихся со временем; во всех этих случаях мы имеем дело с алгоритмами, практически предназначенными для бесконечного выполнения. Признаком успешного выполнения является не окончательный результат, а способность алгоритма сохранить работоспособность в постоянно изменяющейся среде, постоянно подкидывающей новые задачи. В таких ситуациях мы переходим из мира кубика Рубика в мир «Тетриса».

Существует много разных примеров, на которых можно исследовать эту тему. В последнем разделе книги мы рассмотрим одну из самых интересных ситуаций: разработку алгоритмов для высокоскоростной коммутации пакетов в Интернете.