Краткое содержание

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

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

проектирования алгоритмов. В частности, мы рассмотрим базовые определения графов, методы обхода графов (обход в ширину и обход в глубину) и основные концепции направленных графов, включая сильную связность и топологическое упорядочение.

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

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

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

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

ласти искусственного интеллекта (планирования и ведения игр), которые без нее не нашли бы отражения в рассматриваемой алгоритмической области.

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Краткое содержание:

  1. СОДЕРЖАНИЕ И ЕГО КРАТКИЙ АНАЛИЗ
  2. Краткое содержание главы 1.
  3. Краткое изложение содержания книги
  4. Краткие юридические профессиограммы .
  5. 3. Будьте кратки.
  6. краткие выводы
  7. КРАТКИЙ ОЧЕРК ИСТОРИЧЕСКОГО РАЗВИТИЯ ЮРИДИЧЕСКОЙ ПСИХОЛОГИИ
  8. КРАТКОЕ ДОХОДЧИВОЕ ИЗЛОЖЕНИЕ*
  9. Борис Акимович Исаев. Социология. Краткий курс, 2010
  10. краткие выводы
  11. КРАТКАЯ СУТЬ.
  12. КРАТКОЕ РЕЗЮМЕ
  13. 1.1.2. Краткая информация