Предисловие

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

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

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

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

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

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

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

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

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

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

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

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

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

Наконец, мы будем благодарны читателям за обратную связь. Как и в любой книге такого объема, в ней наверняка встречаются ошибки, которые остались и в печатном варианте. Комментарии и сообщения об ошибках можно присылать по электронной почте [email protected]; пожалуйста, включите в строку темы слово “feedback”.

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

Глава 1 начинается с представления некоторых типичных алгоритмических задач. Мы начнем с задачи устойчивых паросочетаний, потому что она позволяет обозначить базовые аспекты разработки алгоритмов более конкретно и элегантно, чем любые абстрактные рассуждения: поиск устойчивых паросочетаний обусловлен естественной, хотя и сложной практической областью, на базе которой можно абстрагировать интересную формулировку задачи и неожиданно эффективный алгоритм ее решения. В оставшейся части главы 1 рассматриваются пять “типичных задач”, которые предопределяют темы из оставшейся части курса. Эти пять задач взаимосвязаны в том смысле, что все они могут рассматриваться как вариации и/или особые случаи задачи поиска независимого множества; но одна задача может быть решена при помощи “жадного” алгоритма, другая — методом динамического программирования, третья — методом нахождения потока в сети, четвертая (собственно задача независимого множества) является NР-полной, а пятая — 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-ю рассматриваются три основных метода работы с вычислительно неразрешимыми задачами: идентификация структурированных особых случаев, алгоритмы аппроксимации и эвристики локального поиска. Глава, посвященная разрешимым особым случаям, показывает, что экземпляры NР-полных задач, встречающиеся на практике, могут быть не столь сложны в худших случаях, потому что нередко они содержат структуру, которая может быть использована при проектировании эффективного алгоритма. Мы покажем, что ЖР-полные задачи часто удается эффективно решить, если ограничиться входными данными, имеющими структуру дерева. Тема завершается подробным обсуждением декомпозиций графов в дерево. Хотя эта тема больше подходит для выпускных учебных курсов, она имеет существенную практическую ценность, для которой трудно найти более доступный материал. В главе, посвященной алгоритмам аппроксимации, рассматривается процесс проектирования эффективных алгоритмов и задача анализа оптимального решения для построения хороших оценок. Что касается методов проектирования алгоритмов аппроксимации, мы сосредоточимся на жадных алгоритмах, линейном программировании и третьем методе, который будет называться “определение цены” (pricing), использующим идеи первых двух. Наконец, мы рассмотрим эвристики локального поиска, включая алгоритм Метрополиса и метод модельной “закалки”. Эта тема часто не рассматривается в алгоритмических курсах среднего уровня, потому что о доказуемых гарантиях таких алгоритмов известно очень мало; однако, учитывая их широкое практическое распространение, мы считаем, что студентам будет полезно знать о них. Также включаются описания случаев, для которых существуют доказуемые гарантии.

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

Как пользоваться книгой

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

Используя книгу на вводном уровне, мы проводим примерно одну лекцию для каждого нумерованного раздела; если объем материала превышает продолжительность одной лекции (например, если в разделе присутствуют дополнительные примеры), дополнительный материал рассматривается как приложение, с которым студенты могут ознакомиться самостоятельно. Разделы со звездочками пропускаются; хотя в них рассматриваются важные темы, они не столь принципиальны. Также мы обычно пропускаем один-два раздела каждой главы из первой половины книги (например, часто пропускаются разделы 4.3, 4.7-4.8, 5.5-5.6, 6.5, 7.6 и 7.11). В главах 11-13 рассматривается примерно половина разделов.

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

Главы 2 и 3 рассматриваются в основном как обзор материала более ранних курсов; но, как упоминалось выше, использование этих двух глав серьезно зависит от связи каждого конкретного курса с предшествующими курсами.

Итоговый учебный план выглядит примерно так: глава 1; главы 4-8 (исключая разделы 4.3, 4.7-4.9, 5.5-5.6, 6.5, 6.10, 7.4, 7.6, 7.11 и 7.13); глава 9 (кратко); глава 10, разделы 10.1 и 10.2; глава 11, разделы 11.1, 11.2, 11.6 и 11.8; глава 12, разделы 12.112.3; глава 13, разделы 13.1-13.5.

Книга также может использоваться в ознакомительной части основных учебных курсов. В нашем представлении такой курс должен познакомить студентов, которым предстоит заниматься исследованиями во многих разных областях, с важными современными вопросами проектирования алгоритмов. В таком случае повышенное внимание формулировке задач тоже приносит пользу, потому что студенты скоро начнут определять собственные исследовательские задачи в различных подобластях. На учебных курсах такого типа мы рассматриваем материал глав 4 и 6 (разделы 4.5-4.9 и 6.5-6.10), весь материал главы 7 (начальные разделы излагаются в более высоком темпе), быстро излагаем тему NР-полноты из главы 8 (потому что многие студенты-старшекурсники уже знакомы с этой темой), а все оставшееся время тратится на знакомство с материалом глав 10-13.

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

Благодарности

Эта книга была написана на основе серии алгоритмических учебных курсов, которые мы вели в Корнелльском университете. За прошедшие годы эти курсы развивались, как развивалась и сама область, и в них отражено влияние преподавателей Корнелла, которые помогали сформировать их в нынешнем виде; это Юрис Хартманис (Juris Hartmanis), Моника Хензингер (MonikaHenzinger), Джон Хопкрофт (John Hopcroft), Декстер Козен (Dexter Kozen), Ронитт Рубинфельд (Ronitt Rubinfeld) и Сэм Туэг (Sam Toueg). Кроме того, мы бы хотели поблагодарить всех своих коллег по Корнеллу за бесчисленные обсуждения представленного материала и более широкого круга вопросов, связанных со спецификой области.

Учебный персонал, участвовавший в преподавании курса, оказал огромную помощь в разработке материала. Мы благодарны нашим ассистентам, в числе которых были: Сиддхарт Александр (Siddharth Alexander), Ри Андо (Rie Ando), Эллиот Аншелевич (Elliot Anshelevich), Ларс Бекстром (Lars Backstrom), Стив Бейкер (Steve Baker), Ральф Бензингер (Ralph Benzinger), Джон Бикет (John Bicket), Дуг Бурдик (Doug Burdick), Майк Коннор (Mike Connor), Владимир Дижур (Vladimir Dizhoor), Шаддин Догми (Shaddin Doghmi), Александр Друян (Alexander Druyan), Бовэй Ду (BoweiDu), Саша Евфимиевски (Sasha Evfimievski), Арифул Гани (Ariful Gani), Вадим Гриншпан (Vadim Grinshpun), Ара Хайрапетян (Ara Hayrapetyan), Крис Джуэл (Chris Jeuell), Игорь Кац (Igor Kats), Омар Хан (Omar Khan), Михаил Кобяков (Mikhail Kobyakov), Алексей Копылов (Alexei Kopylov), Брайан Кулис (Brian Kulis), Амит Кумар (Amit Kumar), Ёнви Ли (Yeongwee Lee), Генри Лин (HenryLin), Ашвин Мачанаваджала (Ashwin Machanavajjhala), Аян Мандал (Ayan Mandal), Бил Макклоски (Bill McCloskey), Леонид Мейергуз (Leonid Meyerguz), Эван Моран (Evan Moran), Ниранджан Нагараджан (Niranjan Nagarajan), Тина Нолт (Tina Nolte), Трэвис Ортогеро (Travis Ortogero), Мартин Пал (Martin Pal), Джон Пересс (Jon Peress), Мэтт Пиотровски (Matt Piotrowski), Джо Поластре (Joe Polastre), Майк Прискотт (Mike Priscott), Син Ци (Xin Qi), Вену Рамасубрамьян (Venu Ramasubramanian), Адитья Рао (Aditya Rao), Дэвид Ричардсон (David Richardson), Брайан Сабино (BrianSabino), Рачит Сиамвалла (Rachit Siamwalla), Себастьян Силгардо (Sebastian Silgardo), Алекс Сливкинс (Alex Slivkins), Чайтанья Свами (Chaitanya Swamy), Перри Там (Perry Tam), Надя Травинин (Nadya Travinin), Сергей Васильвицкий (Sergei Vassilvitskii), Мэтью Уокс (Matthew Wachs), Том Векслер (Tom Wexler), Шан-Люн Мэверик Ву (Shan-Leung Maverick Woo), Джастин Ян (Justin Yang) и Миша Зацман (Misha Zatsman). Многие из них предоставили полезную информацию, поделились замечаниями и предложениями по тексту. Мы также благодарим всех студентов, поделившихся своим мнением по поводу ранних вариантов книги.

За несколько последних лет нам сильно помогали наши коллеги, использовавшие черновые версии материалов для обучения. Анна Карлин (Anna Karlin) бесстрашно взяла предварительную версию за основу своего курса в Вашингтонском университете, когда книга еще находилась на ранней стадии работы; за ней последовали многие люди, использовавшие книгу как учебник или ресурс для обучения: Пол Бим (Paul Beame), Аллан Бородин (Allan Borodin), Девдатт Дубхаши (Devdatt Dubhashi), Дэвид Кемпе (David Kempe), Джин Клейнберг (Gene Kleinberg), Декстер Козен (Dexter Kozen), Амит Кумар (Amit Kumar), Майк Моллой (Mike Molloy), Ювал Рабани (Yuval Rabani), Тим Рафгарден (Tim Roughgarden), Алекса Шарп (Alexa Sharp), Шанхуа Тен (Shanghua Teng), Аравинд Шринивасан (Aravind Srinivasan), Дитер ван Мелькебек (Dieter van Melkebeek), Кевин Уэйн (Kevin Wayne), Том Векслер (Tom Wexler) и Сью Уайтсайдз (Sue Whitesides). Мы глубоко благодарны им за их мнения и советы, которые помогли нам улучшить книгу. Хотим дополнительно поблагодарить Кевина Уэйна за предоставленные материалы, с которыми книга становится еще более полезной для преподавателя.

В ряде случаев в нашем подходе к некоторым темам в книге отразилось влияние конкретных коллег. Наверняка многие из этих предложений прошли мимо нас, но некоторых людей мы хотим поблагодарить особо: это Юрий Бойков (Yuri Boykov), Рон Элбер (Ron Elber), Дэн Хаттенлокер (Dan Huttenlocher), Бобби Клейнберг (Bobby Kleinberg), Эви Клейнберг (Evie Kleinberg), Лиллиан Ли (Lillian Lee), Дэвид Макаллестер (David McAllester), Марк Ньюман (Mark Newman), Прабхакар Рагхаван (Prabhakar Raghavan), Барт Селман (Bart Selman), Дэвид Шмойс (David Shmoys), Стив Строгац (Steve Strogatz), Ольга Векслер (Olga Veksler), Данкан Уоттс (Duncan Watts) и Рамин Забих (Ramin Zabih).

Нам было приятно работать с Addison Wesley за прошедший год. Прежде всего, спасибо Мэтту Голдстейну (Matt Goldstein) за все его советы и рекомендации и за помощь в преобразовании огромного объема обзорного материала в конкретный план, который улучшил книгу. Наши ранние беседы о книге с Сьюзен Хартман (Susan Hartman) тоже принесли огромную пользу. Мы благодарим Мэтта и Сьюзен, а также Мишель Браун (Michelle Brown), Мэрилин Ллойд (Marilyn Lloyd), Патти Махтани (Patty Mahtani) и Мейта Суарес-Ривас (Maite Suarez-Rivas) из издательства Addison Wesley и Пола Анагностопулоса (Anagnostopoulos) и Жаки Скарлотт (Jacqui Scarlott) из Windfall Software за работу по редактированию, подготовке к выпуску и управлению проектом. Хотим особо поблагодарить Пола и Жаки за мастерскую верстку книги. Спасибо Джойсу Уэллсу (Joyce Wells) за дизайн обложки, Нэнси Мерфи (Nancy Murphy) из Dartmouth Publishing — за работу над иллюстрациями; Теду Локсу (Ted Laux) за составление алфавитного указателя, Каролу Лейбу (Carol Leyba) и Дженнифер Маккейн (Jennifer McClain) за стилевое редактирование и корректуру.

Ансельм Блумер (Anselm Blumer) из Университета Тафта, Ричард Чанг (Richard Chang) из Мэрилендского университета, Кевин Комптон (Kevin Compton) из университета Мичигана, Диана Кук (Diane Cook) из Техасского университета в Арлингтоне, Сариэл Хар-Пелед (Sariel Har-Peled) из Университета Иллинойса в Урбана-Шампейн, Санджив Ханна (Sanjeev Khanna) из Университета Пенсильвании, Филип Клейн (Philip Klein) из Университета Брауна, Дэвид Маттиас (David Matthias) из Университета штата Огайо, Адам Мейерсон (Adam Meyerson) из Калифорнийского университета в Лос-Анджелесе, Майкл Митценмахер (Michael Mitzenmacher) из Гарвардского университета, Стивен Олариу (Stephan Olariu) из Университета Олд-Доминион, Мохан Патури (MohanPaturi) из Калифорнийского университета в Сан-Диего, Эдгар Рамос (Edgar Ramos) из Университета Иллинойса в Урбана-Шампейн, Санджай Ранка (Sanjay Ranka) из Университета Флориды в Гейнсвилле, Леон Резник (Leon Reznik) из Рочестерского технологического института, Субхаш Сури (Subhash Suri) из Калифорнийского университета в Санта-Барбаре, Дитер ван Мелькебек (Dieter van Melkebeek) из Университета Висконсина в Мэдисоне, Булент Йенер (Bulent Yener) из Ренсслерского политехнического университета не пожалели своего времени и предоставили подробные и содержательные рецензии на рукопись; их комментарии привели к многочисленным усовершенствованиям (как большим, так и малым) в окончательной версии текста.

Наконец, мы хотим поблагодарить наши семьи — Лиллиан, Алису, Дэвида, Ребекку и Эми. Мы ценим их поддержку, терпение и все остальное сильнее, чем можно выразить в тексте.

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

Джон Клейнберг

Ева Тардос

Итака, 2005