Роль алгоритмов в вычислениях

Роль алгоритмов в вычислениях

Что такое алгоритмы? Стоит ли тратить время на их изучение? Какова роль

алгоритмов и как они соотносятся с другими компьютерными технологиями? Эта

глава дает ответы на поставленные вопросы.

1.1 Алгоритмы

Говоря неформально, алгоритм (algorithm) — это любая корректно опреде-

определенная вычислительная процедура, на вход (input) которой подается некоторая

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

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

собой последовательность вычислительных шагов, преобразующих входные ве-

величины в выходные.

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

решения корректно поставленной вычислительной задачи (computational prob-

problem). В постановке задачи в общих чертах задаются отношения между входом

и выходом. В алгоритме описывается конкретная вычислительная процедура, с по-

помощью которой удается добиться выполнения указанных отношений.

Например, может понадобиться выполнить сортировку последовательности

чисел в неубывающем порядке. Эта задача часто возникает на практике и служит

благодатной почвой для ознакомления на ее примере со многими стандартными

методами разработки и анализа алгоритмов. Задача сортировки (sorting problem)

формально определяется следующим образом.
В информатике сортировка является основополагающей операцией (во многих

программах она используется в качестве промежуточного шага), в результате чего

появилось большое количество хороших алгоритмов сортировки. Выбор наиболее

подходящего алгоритма зависит от многих факторов, в том числе от количества

сортируемых элементов, от их порядка во входной последовательности, от воз-

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

того, какое устройство используется для хранения последовательности: основная

память, магнитные диски или накопители на магнитных лентах.

Говорят, что алгоритм корректен (correct), если для каждого ввода резуль-

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

алгоритм решает данную вычислительную задачу. Если алгоритм некорректный,

то для некоторых вводов он может вообще не завершить свою работу или вы-

выдать ответ, отличный от ожидаемого. Правда, некорректные алгоритмы иногда

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

возникновения ошибок. Такой пример рассматривается в главе 31, в которой изу-

изучаются алгоритмы определения простых чисел, намного превышающих единицу.

Тем не менее, обычно мы заинтересованы только в корректных алгоритмах.

Алгоритм может быть задан на естественном языке, в виде компьютерной про-

программы или даже воплощен в аппаратном обеспечении. Единственное требова-

требование — его спецификация должна предоставлять точное описание вычислительной

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

Вычислительные задачи, для которых разработаны алгоритмы, отнюдь не огра-

ограничиваются сортировкой. (Возможно, об их разнообразии можно судить по объему

данной книги.) Практическое применение алгоритмов чрезвычайно широко, о чем

свидетельствуют приведенные ниже примеры.

• Целью проекта по расшифровке генома человека является идентификация

всех 100000 генов, входящих в состав ДНК человека, определение последо-

вательностей, образуемых 3 миллиардами базовых пар, из которых состоит

ДНК, сортировка этой информации в базах данных и разработка инстру-

инструментов для ее анализа. Для реализации всех перечисленных этапов нужны

сложные алгоритмы. Решение разнообразных задач, являющихся составны-

составными частями данного проекта, выходит за рамки настоящей книги, однако

идеи, описанные во многих ее главах, используются для решения упомяну-

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

целей, эффективно используя вычислительные ресурсы. При этом эконо-

экономится время (как машинное, так и затрачиваемое сотрудниками) и деньги,

а также повышается эффективность использования лабораторного оборудо-

оборудования.

• Internet позволяет пользователям в любой точке мира быстро получать до-

доступ к информации и извлекать ее в больших объемах. Управление и манипу-

манипуляция этими данными осуществляется с помощью хитроумных алгоритмов.

В число задач, которые необходимо решить, входит определение оптималь-

оптимальных маршрутов, по которым перемещаются данные (методы для решения

этой задачи описываются в главе 24), и быстрый поиск страниц, на кото-

которых находится та или иная информация, с помощью специализированных

поисковых машин (соответствующие методы приводятся в главах 11 и 32).

• Электронная коммерция позволяет заключать сделки и предоставлять това-

товары и услуги с помощью электронных технических средств. Для того чтобы

она получила широкое распространение, важно иметь возможность защи-

защищать такую информацию, как номера кредитных карт, пароли и банковские

счета. В число базовых технологий в этой области входят криптография

с открытым ключом и цифровые подписи (они описываются в главе 31),

основанные на численных алгоритмах и теории чисел.

• В производстве и коммерции очень важно распорядиться ограниченными

ресурсами так, чтобы получить максимальную выгоду. Нефтяной компании

может понадобиться информация о том, где пробурить скважины, чтобы по-

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

может задаться вопросом, как потратить деньги, чтобы максимально повы-

повысить свои шансы победить на выборах. Авиакомпаниям важно знать, какую

минимальную цену можно назначить за билеты на тот или иной рейс, чтобы

уменьшить количество свободных мест и не нарушить при этом законы, ре-

регулирующие авиаперевозку пассажиров. Поставщик услуг Internet должен

уметь так размещать дополнительные ресурсы, чтобы повышался уровень

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

линейного программирования, к изучению которого мы приступим в главе 29.

Несмотря на то, что некоторые детали представленных примеров выходят за

рамки настоящей книги, в ней приводятся основные методы, применяющиеся для
Структуры данных

В книге представлен ряд структур данных. Структура данных (data struc-

structure) — это способ хранения и организации данных, облегчающий доступ к этим

данным и их модификацию. Ни одна структура данных не является универсаль-

универсальной и не может подходить для всех целей, поэтому важно знать преимущества

и ограничения, присущие некоторым из них.







анализ алгоритмов
3.1. Что такое время выполнения алгоритма?

Время выполнения алгоритма или операции над структурой данных

зависит, как правило, от целого ряда факторов, вследствие чеговозника-

ет вопрос — как следует проводить его измерение. При реализации алго-

алгоритма можно определить затраты времени, регистрируя действительное

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

запуска с различными исходнымиДаннЫми.Подобные изМерения долж-

должны проводиться с достаточной точностью с пЬмощью системных вызо-

вызовов, встроенных в язык или операционную систему, для которой написан

данный алгоритм (например, метод System.currentTimeMillis() или вызо-

вызовом исполняющей среды с возможностью профилирования). В общем,

требуется определить, каким образом время выполнения программы за-

зависит от количества исходных данных. Длйрешения этой задачи можно

провести ряд экспериментов, в которых будет использовано различное

количество исходных данных. Далее полученные результаты наглядно

представляются с помощью графика, где каждый случай выполнения алго-

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

исходных данных п, а координата у — времени выполнения алгоритма t

(см. рис. 3.1). Чтобы сделать определенные выводы на основе получен-

полученных экспериментов, необходимо использовать качественные образцы ис-

исходных данных и провести достаточно большое число экспериментов —

что позволит определить некоторые статистические характеристики в от-

отношении времени выполнения алгоритма.



Результаты экспериментального исследования времени выполнения ал-

алгоритма. Точка с координатами (n, t) обозначает, что при размере исход-

исходных данных п время выполнения алгоритма составило / миллисекунд

(мс). На рис. 3.1, а представлены результаты выполнения алгоритма на

компьютере с быстрым процессором, на рис. 3.1, b представлены резуль-

результаты выполнения алгоритма на компьютере с медленным процессором

В целом можно сказать, что время выполнения алгоритма или метода

структуры данных возрастает по мере увеличения размера исходных дан-

данных, хотя оно зависит и от типа данных, даже при равном размере. Кроме

того, время выполнения зависит от аппаратного обеспечения (процессо-

(процессора, тактовой частоты, размера памяти, места на диске и др.) и программ-

программного обеспечения (операционной среды,йзыка программирования, ком-

компилятора, интерпретатора и др.), с помощью которых осуществляется

реализация, компиляция и выполнение алгоритма. Например, при всех

прочих равных условиях время выполнения алгоритма определенного ко-

количества исходных данных будет меньше при использовании более мощ-

мощного компьютера или при записи алгоритма в виде программы на машин-

машинном коде по сравнению с его исполнением виртуальной машиной, прово-

проводящей интерпретацию в байт-коды.

3.1.1. Требования к методологии общего анализа

Экспериментальные исследования, безусловно, очень полезны, одна-

однако при их проведении существуют три основных ограничения:

• эксперименты могут проводиться лишь с использованием ограни-

ограниченного набора исходных данных; результаты, полученные с ис-

использованием другого набора, не учитываются;

• для срайнения эффективности двух алгоритмов необходимо, чтобы

эксперименты по определению времени их вьйюлнения проводи-

проводились на одинаковом аппаратном и программном обеспечении;

• для экспериментального изучения времени выполнения алгоритма

необходимо провести его реализацию и выполнение.

Далее в этой главе рассматривается общая методология анализа вре-

времени выполнения алгоритмов, которая:

• учитывает различные типы входных данных;

• позволяет производить оценку относительной эффективности лю-

любых двух алгоритмов независимо от аппаратного и программного

обеспечения;

• может проводиться по описанию алгоритма без его непосредствен-

непосредственной реализации или экспериментов.

Сущность такой методологии состоит в том, что каждому алгоритму

соответствует функцияДя), которая представляет время выполнения ал-

алгоритма как функцию размера исходных данных п. Наиболее распростра-

распространенными являются функции п и п2. Например, можно записать следую-

следующее утверждение: «Время выполнения алгоритма А пропорционально п».

В этом случае, в результате проредени^ экспериментов, окажется, что

время выполнения алгоритма А при любом размере входных данных п не

превышает значения cn, где с является константой, определяемой усло-

условиями используемого аппаратного и программного обеспечения. Если

имеются два алгоритма А и В, причем время выполнения алгоритма А

пропорционально п, а время выполнения В пропорционально п2, то пред-

предпочтительнее использовать алгоритм А, так как функция п возрастает

медленнее, чем функция п2. Выводы о скорости возрастания этих функ-

функций являются, безусловно, очевидными, однако предлагаемая методоло-

методология содержит точные определения данных понятий.

Перед тем как приступим к непосредственной разработке предлагае-

предлагаемой методологии анализа алгоритмов, рассмотрим высокоуровневые сис-

системы описания алгоритмов (раздел 3.2), вспомним базовые математиче-

математические положения (раздел 3.3), а также приемы формального доказательст-

доказательства (раздел 3.4).

3.2. Псевдокод

Зачастую программистам требуется создать описание алгоритма, пред-

предназначаемое только для человека. Подобные описания не являются про-

программами, но вместе с тем они более структурированы, чем обычный

текст. В частности, «высокоуровневые» описания сочетают естественный

язык и распространенные структуры языка программирования, что дела-

делает их доступными и вместе с тем информативными. Такие описания спо-

способствуют проведению высокоуровневого анализа структуры данных или

алгоритма. Подобные описания принято называть псевдокодом.

3.2.1. Пример псевдокода

Проблема «максимума в массиве» является простой задачей поиска

элемента с максимальным значением в массиве А, содержащем п целых

чисел. Для решения этой задачи можно использовать алгоритм аггауМах,

который осуществляет просмотр массива А с использованием цикла for.

Псевдокод алгоритма аггауМах представлен во фрагменте кода 3.1,

а полная реализация программы Java представлена во фрагменте кода 3.2.

Алгоритм arrayMax(A, n):

Input: массив А, содержащий п целых чисел (п > 1).

Output: элемент с максимальным значением в массиве Л.

currentMax <- А [0]

for / <- 1 to n - 1 do

if currentMax
currentMax <- А [/]

return currentMax

Фрагмент кода 3.1. Алгоритм аггауМах

/**

* Тестирует программу алгоритма поиска максимального элемента массива.

7

public class ArrayMaxProgram {

/** находит элемент с максимальным значением в массиве А,

* содержащем п целых чисел.

*/

static int arrayMax(int[ ] A, int n) {

int currentMax = A[0]; // выполняется один раз

for (int i=l' i < n' i++) // выполняется от 1 до п, п-1 раз

// соответственно.

if (currentMax < A[i]) // выполняется п-1 раз

currentMax = A[i]; // выполняется максимально л-1 раз
return currentMax; // выполняется один раз

}

/** Тестирующий метод, вызываемый после выполнения программы.

7

public static void main(String args[ ]) {

int[ ] num = { 10, 15, 3, 5, 56, 107, 22, 16, 85 };

int n = num.length;

System.out.print("Array:");

for (int j=0; i < n; i++) System.out.print("" + num[i]);

// выводит один элемент массива

System.out.print("" + num[i]);

System.out.println(".");

System.out.println("Themaximumelementis" + arrayMax(num,n) + ".");

Фрагмент кода 3.2. Алгоритм arrayMax внутри законченной Java-программы.

В комментариях указано, сколько раз выполняются определенные команды в ходе

выполнения программы

Как можно заметить, псевдокод выглядит компактнее Java-кода, и его

легче читать и понимать. При анализе псевдокода можно поспорить

о правильности алгоритма arrayMax c простым аргументом. Переменная

currentMax первоначально принимает значение первого элемента массива А.

Можно утверждать, что перед началом итерации по номеру / значение

currentMax равно максимаЛьному значению среди первых / элементов

массива А. Так как при повторении / зн&чение currentMax сравнивается

с A[i], то, если это утверждение верно перед данной итерацией, оно будет

верно и после нее для / + 1 (которое является следующим значением счетчика /).

Таким образом, после количества итераций п - 1 значение currentMax бу-

будет равно элементу массива А, содержащему максимальное значение.

3.2.2. Что такое псевдокод?

Псевдокод является сочетанием естественного языка и конструкций

языка программирования, которые используются для описания основ-

основных идей, заложенных в реализацию структуры данных или алгоритма.

Точного определения языка псевдокода не существует, так как в нем все

же преобладает естественный язык. В то же время для обеспечения четко-

четкости и ясности в псевдокоде наряду с естественным языком используются

стандартные конструкции языка программирования, такие как:

• Выражения. Для написания числовых и логических выражений ис-

используются стандартные математические символы. Знак стрелки

применяется в качестве оператора присваивания в командах при-

присваивания (равнозначен оператору «=» языка Java). Знак «=» ис-

используется для передачи отношения равенства в логических выра-

выражениях (что соответствует оператору «= =» языка Java).

• Объявление метода. Имя алгоритма (paraml, param2, ...) объявляет

«имя» нового метода и его параметры.

• Структуры принятиярешений. Условие if, then — действия, если ус-

условие верно [else — если условие не верно]. Отступы используются

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

• Цикл while, while — условие, do т? действия. Отступ обозначает

действия, выполняемые внутри цикла.

• Цикл repeat, repeat — действия, которые выполняются, пока вы-

выполняется условие until. Отступ обозначаетдействия, выполняемые

внутри цикла.

• Цикл for. for — описание переменной и инкремента, do — действия.

Отступ обозначает действия, выполняемые внутри цикла.

• Индексирование массива. A[/] обозначает z'-ую ячейку массива А.

Ячейки массива А с количеством ячеек п индексируются от A[0] до

A[n - 1] (как в Java).

• Обращения к методам, object.method (args) (часть object необязатель-

необязательна, если она очевидна).

• Возвращаемое методом значение. Значение return. Данный оператор воз-

возвращает значение, указанное в методе, вызывающим данный метод.

При записи псевдокода следубт помнить, что он записывается для

анализа человеком, а не компьютером, и необходимо выразить основные

глобальные идеи, а не базовые детали реализации структуры. В то же вре-

время не следует упускать из виду важные этапы. Таким образом, как при

любом типе человеческого общения, написание псевдокода состоит в по-

поиске баланса между общим и частным; такое умение вырабатывается

в ходе практической деятельности. В книге приведено несколько упраж-

упражнений, которые смогут поспособствовать развитию таких навыков.

Дополнительно, для лучшей передачи сущности алгоритма или струк-

структуры данных, описание алгоритма должно начинаться с краткого абст-

абстрактного объяснения характера входного и выходного потока данных,

а также основных действий vt используемых идей алгоритма.