Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013), страница 5

Часть 1 Освавы Интернет позволяет пользователям в любой точке мира быстро получать доступ к информации и извлекать ее в больших объемах. Благодаря помощи хитроумных алгоритмов сайты в Интернете способны работать с этими огромными объемами данных. Примерами задач, для которых жизненно необходимо применение эффективных алгоритмов, могут служить определение оптимальных маршрутов, по которым перемешаются данные (методы для решения этой задачи описываются в главе 24), и быстрый поиск страниц, на которых находится та или иная информация, с помощью специализированных поисковых машин (соответствуюшне методы приводятся в главах 11 и 32). Электронная коммерция позволяет заключать сделки и предоставлять товары и услуги с помощью различных электронных технических средств.

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

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

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

Пусть имеется карта дорог, на которой обозначены расстояния между каждой парой соседних перекрестков. Наша цель — определить кратчайший путь от одного перекрестка к другому. Количество возможных маршрутов может быть огромным, даже если исключить те из них, которые содержат самопересечения. Как найти наиболее короткий из всех возможных маршрутов? При решении этой задачи карта дорог (которая сама по себе является моделью настояших дорог) моделируется в виде графа (мы подробнее познакомимся с графами в части Ч1 и приложении Б). Задача будет заключаться в определении кратчайшего пути от одной вершины графа к другой.

Эффективное решение этой задачи представлено в главе 24. Глава !. Роль олгаривииов в вычиеленилл У нас имеются две упорядоченные последовательности символов, Х = (хы хз,..., я ) и г = (ры уз,..., у„), и нам надо найти длиннейшую общую подпоследовательность Х и У. Подпоследовательностью Х является сама последовательность Х с некоторыми (возможно, всеми нли никакими) удаленными элементами. Например, одной из подпоследовательностей (А, В, С, 13, Е, Е, С) является (В, С, Е, С).

Наидлиннейшая общая подпоследовательность Х и )' дает меру схожести двух последовательностей. Например, если этими двумя последовательностями являются базовые пары в цепочках ДНК, то мы можем считать их сходными, если они имеют длинную общую подпоследовательность. Если Х имеет т символов, а )' — п, символов, то Х и У имеют 2 и 2" возможньгх подпоследовательностей соответственно. Выбирая все возможные подпоследовательности Х и )г и сопоставляя их, можно решить поставленную задачу только за очень длительное время (конечно, если только т и п не оказываются очень малыми величинами). В главе 15 мы познакомимся с общим методом гораздо более эффективного решения этой задачи, известным как динамическое программирование. У нас имеется проект, который представлен в виде библиотеки составных частей, причем каждая часть может включать экземпляры из других частей.

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

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

33.6 на с. 1076). В качестве набора вершин может выступать любое из 2" подмножеств множества точек. Однако недостаточно знать, какие точки являются вершинами выпуклой оболочки, нужно еше указать порядок их обхода. Таким образом, чтобы найти выпуклую оболочку, придется перебрать множество вариантов. В главе 33 описаны два хороших метода поиска выпуклой оболочки. Приведенные выше случаи применения алгоритмов отнюдь не являются исчерпываюшими, однако на их примере выявляются две обшие характеристики, присушие многим интересным алгоритмам. Часть 2 Основы 1. Они имеют множество вариантов-кандидатов, подавляющее большинство которых решениями не являются.

Поиск среди них работаюшего (или "наилучшего") кандидата является довольно сложным делом. 2. Они имеют практическое применение. Простейший пример среди перечисленных задач — определение кратчайшего пути, соединяющего два перекрестка. Любая компания, занимающаяся автомобильными или железнодорожными перевозками, финансово заинтересована в том, чтобы определить кратчайший маршрут. Это способствовало бы снижению затрат труда и расходов горючего. Маршрутизатору в Интернете также нужно иметь возможность находить кратчайшие пути в сети, чтобы как можно быстрее доставлять сообщения. Водитель, едущий из одного города в другой, может захотеть найти маршрут иа веб-сайте или использовать в поездке ОРБ.

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

Помимо того что дискретное Фурье- преобразование представляет собой основу всей обработки сигналов, оно имеет приложения в сжатии данных и умножении больших полиномов и целых чисел. В главе 30 приведены как эффективный алгоритм быстрого Фурье-преобразования (обычно именуемого БПФ (ЕРТ)) для решения этой задачи, так и наброски проекта микросхемы для вычисления БПФ. Структуры данных В книге также представлен ряд структур данных. Структура даиных (оаГа зпцсппе) — это способ хранения и организации данных, облегчающий доступ к этим данным и их модификацию. Ни одна структура данных не является универсальной и не может подходить для всех целей, поэтому важно знать преимушества и ограничения, присущие некоторым из них.

Методические указания Данную книгу можно рассматривать как "сборник рецептов" для алгоритмов. Правда, однажды вам встретится задача, для которой вы не сможете найти опубликованный алгоритм (например, таковы многие из приведенных в книге упражнений и задач). Данная книга научит вас методам разработки алгоритмов и их анализа. Это позволит вам разрабатывать корректные алгоритмы и оценивать их эффективность самостоятельно. В разных главах рассматриваются различные аспекты решения алгоритмических задач. Одни главы посвяшены конкретным задачам, таким как поиск медиан и порядковых статистик в главе 9, вычисление минимальных остовных деревьев в главе 23 и определение максимального потока в сети в главе 26. Другие главы ориентированы на методы, такие как "разделяй Глава Ь Раль алгаритиав в вылиалеиилл и властвуй" в главе 4, динамическое программирование в главе 15 и амортизаци- онный анализ в главе 17.

Сложные задачи Ббльшая часть этой книги посвящена эффективным алгоритмам. Обычной мерой эффективности алгоритма является скорость — время, в течение которого алгоритм выдает результат. Однако существуют задачи, для которых неизвестны эффективные методы решения. В главе 34 рассматривается интересный вопрос, имеющий отношение к подобным задачам, известным как ХР-полные. Почему ХР-полные задачи представляют такой интерес? Во-первых, несмотря на то что до сих пор не найден эффективный алгоритм их решения, также не доказано, что такого алгоритма не существует. Другими словами, никто не знает, существует ли эффективный алгоритм для ХР-полных задач.