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

В алгоритме описывается конкретная вычислительная процедура, с помощью которой удается добиться выполнения указанных отношений. Например, может понадобиться выполнить сортировку последовательности чисел в неубывающем порядке. Эта задача часто возникает на практике и служит благодатной почвой для ознакомления на ее примере со многими стандартными методами разработки и анализа алгоритмов. Задача сортировки (аоп1ля ргоЫеш) формально определяется следующим образом. Глава 1.

Роль алгоритмов в вычислениях 47 Вход: последовательность из и чисел (а1,аэ,...,а„). Выход: перестановка (измененне порядка) (а1,а~э,...,а'„) входной последовательности таким образом„ что для ее членов выполняется соотношение а1 < а ( ° ( а„, / Р / Например, если на вход подается последовательность (31,41,59,26,41,58), то вывод алгоритма сортировки должен быть таким: (26, 31, 41, 41, 58, 59). Подобная входная последовательность называется экземяляром (1пз1апсе) задачи сортировки. Вообще говоря, экземяляр задачи состоит из ввода (удовлетворяющего всем ограничениям, наложенным прн постановке задачи), необходимого для решения задачи.

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

Мы говорим, что корректный алгоритм ре1ааеяг данную вычислительную задачу. Если алгоритм некорректный, то для некоторых вводов он может вообще не завершить свою работу илн выдать ответ, отличный от ожидаемого. Правда, некорректные алгоритмы иногда могут оказаться полезными, если в них есть возможность контролировать частоту возникновения ошибок. Такой пример рассматривается в главе 31, в которой изучаются алгоритмы определения простых чисел, намного превышающих единицу. Тем не менее, обычно мы заинтересованы только в корректных алгоритмах.

Алгоритм может быть задан на естественном языке, в виде компьютерной программы или даже воплощен в аппаратном обеспечении. Единственное требование — его спецификация должна предоставлять точное описание вычислительной процедуры, которую требуется выполнить. Какие задачи решаются с помощью алгоритмов? Вычислительные задачи„для которых разработаны алгоритмы, отнюдь не ограничиваются сортировкой. (Возможно, об их разнообразии можно судить по объему данной книги.) Практическое применение алгоритмов чрезвычайно широко, о чем свидетельствуют приведенные ниже примеры.

° Целью проекта по расшифровке генома человека является идентификация всех 100 000 генов, входящих в состав ДНК человека, определение последо- 48 Часть!. Основы вательностей, образуемых 3 миллиардами базовых пар, из которых состоит ДНК, сортировка этой информации в базах данных и разработка инструментов для ее анализа. Для реализации всех перечисленных этапов нужны сложные алгоритмы. Решение разнообразных задач, являющихся составными частями данного проекта, выходит за рамки настоящей книги, однако идеи, описанные во многих ее главах, используются для решения упомянутых биологических проблем.

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

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

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

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

Задача будет заключаться в определении кратчайшего пути от одной вершины графа к другой. Эффективное решение этой задачи представлено в главе 24. ° Пусть дана последовательность (Аы Аз,..., А„), образованная п матрицами, и нам нужно найти произведение этих матриц. Поскольку матричное произведение обладает свойством ассоциативности, существует несколько корректных порядков умножения. Например, если п = 4, перемножение матриц можно выполнять любым из следующих способов (определяемых скобками): (А~ (Аз (АзА4))), (А~ ((АзАз) А4)), ((А~Аз) (АзА4)), ((А~ (АзАз)) А4) или (((А~Аз) Аз) А4). Если все этн матрицы квадратные (т.е. одинакового размера), порядок перемножения не влияет на продолжительность процедуры.

Если же матрицы различаются по размеру (но при этом их размеры соответствуют правилам матричного умножения), то порядок их перемножения может очень сильно влиять на время выполнения процедуры. Количество всевозможных вариантов, различающихся порядком перемножения матриц, растет с увеличением юличества матриц по экспоненциальному закону, поэтому для перебора всех этих вариантов может потребоваться довольно длительное время. Из главы 15 мы узнаем, как эта задача намного эффективнее решается с помощью общего метода, известного как динамическое программирование. ° Пусть имеется уравнение ах = Ь (пюдп), ~де а, Ь и п — целые числа, и нужно найти все целые х по модулю и, удовлетворяющие этому уравнению. Оно может не иметь решения, может иметь одно илн несколью решений.

Можно попытаться применить метод, заключающийся в последовательной подстановке в уравнение чисел х = О, 1,..., и — 1, но в главе 31 представлен более эффективный метод. ° Пусть имеется п принадлежащих плоскости точек, и нужно найти выпуклую оболочку этих точек.

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