1.5 Обзор тем

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

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

Основные принципы (Часть I) в контексте данной книги представляют собой основные принципы и методологию, используемые для реализации, анализа и сравнения алгоритмов. Материал, приведенный в главе 1, служит обоснованием изучения разработки и анализа алгоритмов; в главе 2 рассмотрены основные методы получения информации о количественных показателях производительности алгоритмов.

Структуры данных (Часть 2) тесно связаны с алгоритмами: необходимо получить ясное представление о методах представления данных, которые используются во всех остальных частях книги. Изложение материала начинается с введения в базовые структуры данных в главе 3, включая анализ, связанные списки и строки; затем в главе 5 рассмотрены рекурсивные программы и структуры данных, в частности, деревья и алгоритмы для манипулирования ими. В главе 4 рассмотрены основные абстрактные типы данных (abstract data types - ADT), такие как стеки и очереди, а также реализации с использованием элементарных структур данных.

Алгоритмы сортировки (Часть 3), предназначенные для упорядочения файлов имеют особую важность. Мы достаточно глубоко рассмотрим ряд базовых алгоритмов, в том числе быструю сортировку, сортировку слиянием и поразрядную сортировку. В ходе рассмотрения мы встретимся с несколькими связанными задачами, в том числе с очередями приоритетов, выбором и слиянием. Многие из этих алгоритмов послужат основанием для других алгоритмов, рассматриваемых в последующих частях книги.

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

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

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

Геометрические алгоритмы (Часть 6) - это методы решения задач с использованием точек и линий (и других простых геометрических объектов), которые стали использоваться лишь недавно. Мы рассмотрим алгоритмы для отыскания образующей поверхности, определенной набором точек, определения пересечений геометрических объектов, решения задач отыскания ближайших точек и для выполнения многомерного поиска. Многие из этих методов прекрасно дополняют более элементарные методы сортировки и поиска.

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

Дополнительные темы (Часть 8) устанавливают соответствие между изложенным в книге материалом и несколькими связанными областями. Изложение материала начинается с рассмотрения базовых подходов к разработке и анализу алгоритмов, в том числе алгоритмов типа разделяй и властвуй , динамического программирования, рандомизации и амортизации. Мы рассмотрим линейное профаммирование, быстрое преобразование Фурье, NP-полноту и другие дополнительные темы для получения общего представления о ряде областей, интерес к которым порождается элементарными проблемами, рассмотренными в этой книге.

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

Принципы

анализа

алгоритмов

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

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

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