Привет, Хаброжители! У нас вышла новинка:
Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных.
Вы познакомитесь с базовыми аспектами построения алгоритмов, основными понятиями и определениями, структурами данных, затем перейдете к основным методам построения алгоритмов, неразрешимости и методам решения неразрешимых задач, и, наконец, изучите рандомизацию при проектировании алгоритмов. Самые сложные темы объясняются на четких и простых примерах, поэтому книга может использоваться как для самостоятельного изучения студентами, так и учеными-исследователями или профессионалами в области компьютерных технологий, которые хотят получить представление о применении тех или иных методов проектирования алгоритмов.
Алгоритмический анализ состоит из двух фундаментальных компонентов: выделения математи-чески чистого ядра задачи и выявления методов проектирования подходящего алгоритма на осно-вании структуры задачи. И чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быст-рее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира.
Алгоритмические задачи образуют ядро компьютерной науки, однако они редко появляются в виде аккуратно упакованных, математи-чески точных вопросов. Чаще они отягощаются множеством хлопотных подробностей, привязанных к конкретному случаю; одни из этих подробностей важны, другие избыточны. В результате алгоритмический анализ состоит из двух фундаментальных компонентов: выде-ления математически чистого ядра задачи и выявления методов проектирования подходящего алгоритма на основании структуры зада-чи. Эти два компонента взаимосвязаны: чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быст-рее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира. Таким образом, при ис-пользовании с максимальной эффективностью алгоритмические идеи не просто предоставляют решения четко поставленных задач — они формируют язык для четкого выражения вопросов, заложенных в их основу.
Цель этой книги — донести до читателя этот подход к алгоритмам в форме процесса проектирования, который начинается с задач, встречающихся по всему диапазону вычислительных приложений, использует хорошее понимание методов проектирования алгоритмов и конечным результатом которого является разработка эффективных решений таких задач. Мы будем изучать роль алгоритмических идей в компьютерной науке вообще и постараемся связать эти идеи с диапазоном точно сформулированных задач, для решения кото-рых проектируются и анализируются алгоритмы. Иначе говоря, какие причины заставляют нас искать решение этих задач и как мы выбираем конкретные способы их формулировки? Как мы узнаем, какие принципы проектирования уместны в той или иной ситуации?
Исходя из сказанного, мы постарались показать, как выявлять «чистые» формулировки алгоритмических задач в сложных вычислитель-ных областях и как на базе этих формулировок проектировать эффективные алгоритмы для решения полученных задач. Чтобы разоб-раться в сложном алгоритме, часто бывает проще всего реконструировать последовательность идей (включая неудачные заходы и тупи-ки), которые привели от исходных упрощенных методов к выработанному со временем решению. Так сформировался стиль изложения, не приводящий читателя от постановки задачи сразу к алгоритму и, на наш взгляд, лучше отражающий то, как мы и наши коллеги под-ходим к решению подобных задач.
Книга предназначена для студентов, прошедших двухсеместровый вводный курс вычислительных технологий (стандартный курс «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 рассматривается применение рандомизации при проектировании алгоритмов. На эту тему написано несколько хороших книг. Здесь мы постараемся предоставить более компактное введение в некоторые способы применения методов рандомизации, осно-ванные на информации, которая обычно входит в учебные курсы дискретной математики среднего уровня.
Джон Клейнберг (Jon Kleinberg) — профессор теории вычислительных систем в Корнелльском университете. Получил докторскую степень в Массачусетском технологическом институте в 1996 году.
Исследования Клейнберга посвящены алгоритмам, прежде всего связанным со структурой сетей и информации, и их практическим применениям в области компьютерных технологий, оптимизации, анализа данных и вычислительной биологии. Его работы по теме сетевого анализа помогли заложить основу современного поколения поисковых систем Интернета.
Ева Тардос (Eva Tardos) — профессор теории вычислительных систем в Корнелльском университете. Получила докторскую степень в Университе Этвёша в Будапеште (Венгрия) в 1984 году. Член Американской академии наук и искусств и Ассоциации по вычислитель-ной технике США.
Научные интересы Тардос связаны с проектированием и анализом алгоритмов для решения задач из теории графов и сетей. Наибольшую известность получили ее работы в области алгоритмов сетевого потока и аппроксимирующих алгоритмов для решения сетевых задач. Ее недавние работы были посвящены алгоритмической теории игр.
Более подробно с книгой можно ознакомиться на сайте издательства
Оглавление
Отрывок
Для Хаброжителей скидка 25% по купону — Алгоритмы
Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных.Вы познакомитесь с базовыми аспектами построения алгоритмов, основными понятиями и определениями, структурами данных, затем перейдете к основным методам построения алгоритмов, неразрешимости и методам решения неразрешимых задач, и, наконец, изучите рандомизацию при проектировании алгоритмов. Самые сложные темы объясняются на четких и простых примерах, поэтому книга может использоваться как для самостоятельного изучения студентами, так и учеными-исследователями или профессионалами в области компьютерных технологий, которые хотят получить представление о применении тех или иных методов проектирования алгоритмов.
Алгоритмический анализ состоит из двух фундаментальных компонентов: выделения математи-чески чистого ядра задачи и выявления методов проектирования подходящего алгоритма на осно-вании структуры задачи. И чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быст-рее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира.
Алгоритмические задачи образуют ядро компьютерной науки, однако они редко появляются в виде аккуратно упакованных, математи-чески точных вопросов. Чаще они отягощаются множеством хлопотных подробностей, привязанных к конкретному случаю; одни из этих подробностей важны, другие избыточны. В результате алгоритмический анализ состоит из двух фундаментальных компонентов: выде-ления математически чистого ядра задачи и выявления методов проектирования подходящего алгоритма на основании структуры зада-чи. Эти два компонента взаимосвязаны: чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быст-рее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира. Таким образом, при ис-пользовании с максимальной эффективностью алгоритмические идеи не просто предоставляют решения четко поставленных задач — они формируют язык для четкого выражения вопросов, заложенных в их основу.
Цель этой книги — донести до читателя этот подход к алгоритмам в форме процесса проектирования, который начинается с задач, встречающихся по всему диапазону вычислительных приложений, использует хорошее понимание методов проектирования алгоритмов и конечным результатом которого является разработка эффективных решений таких задач. Мы будем изучать роль алгоритмических идей в компьютерной науке вообще и постараемся связать эти идеи с диапазоном точно сформулированных задач, для решения кото-рых проектируются и анализируются алгоритмы. Иначе говоря, какие причины заставляют нас искать решение этих задач и как мы выбираем конкретные способы их формулировки? Как мы узнаем, какие принципы проектирования уместны в той или иной ситуации?
Исходя из сказанного, мы постарались показать, как выявлять «чистые» формулировки алгоритмических задач в сложных вычислитель-ных областях и как на базе этих формулировок проектировать эффективные алгоритмы для решения полученных задач. Чтобы разоб-раться в сложном алгоритме, часто бывает проще всего реконструировать последовательность идей (включая неудачные заходы и тупи-ки), которые привели от исходных упрощенных методов к выработанному со временем решению. Так сформировался стиль изложения, не приводящий читателя от постановки задачи сразу к алгоритму и, на наш взгляд, лучше отражающий то, как мы и наши коллеги под-ходим к решению подобных задач.
Общие сведения
Книга предназначена для студентов, прошедших двухсеместровый вводный курс вычислительных технологий (стандартный курс «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 рассматривается применение рандомизации при проектировании алгоритмов. На эту тему написано несколько хороших книг. Здесь мы постараемся предоставить более компактное введение в некоторые способы применения методов рандомизации, осно-ванные на информации, которая обычно входит в учебные курсы дискретной математики среднего уровня.
Об авторах
Джон Клейнберг (Jon Kleinberg) — профессор теории вычислительных систем в Корнелльском университете. Получил докторскую степень в Массачусетском технологическом институте в 1996 году.
Исследования Клейнберга посвящены алгоритмам, прежде всего связанным со структурой сетей и информации, и их практическим применениям в области компьютерных технологий, оптимизации, анализа данных и вычислительной биологии. Его работы по теме сетевого анализа помогли заложить основу современного поколения поисковых систем Интернета.
Ева Тардос (Eva Tardos) — профессор теории вычислительных систем в Корнелльском университете. Получила докторскую степень в Университе Этвёша в Будапеште (Венгрия) в 1984 году. Член Американской академии наук и искусств и Ассоциации по вычислитель-ной технике США.
Научные интересы Тардос связаны с проектированием и анализом алгоритмов для решения задач из теории графов и сетей. Наибольшую известность получили ее работы в области алгоритмов сетевого потока и аппроксимирующих алгоритмов для решения сетевых задач. Ее недавние работы были посвящены алгоритмической теории игр.
Более подробно с книгой можно ознакомиться на сайте издательства
Оглавление
Отрывок
Для Хаброжителей скидка 25% по купону — Алгоритмы
