Лекция 7 Алгоритм

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

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

Алгоритм — это точная инструкция, а инструк­ции встречаются практически во всех областях че­ловеческой деятельности. Возможны алгоритмы проведения физического эксперимента, сборки шкафа или телевизора, обработки детали. Однако не всякая инструкция есть алгоритм. Инструкция становится алгоритмом только тогда, когда она удовлетворяет определенным требованиям. Эти требования частично сформулированы в начале статьи, хотя упомянутые в определении понятия од­нозначности и элементарности сами нуждаются в уточнении. Алгоритм однозначен, если при приме­нении к одним и тем же данным он дает один и тот же результат. Но как по описанию алгоритма опре­делить, однозначен он или нет? В каком случае ша­ги считаются элементарными?

Может возникнуть встречный вопрос: а так ли уж необходимо иметь точное определение алгорит­ма? В конце концов, в течение более двух тысяче­летий люди создавали различные алгоритмы, не задумываясь над тем, что такое алгоритм вообще. Ответ на этот вопрос связан с двумя аспектами: те­оретическим и практическим. С точки зрения самой математики желательно иметь дело только с точно определенными понятиями. Это нужно, например, для того, чтобы утверждать о некотором процессе, что он является алгоритмом или не является тако­вым. Точное определение важно и тогда, когда воз­никает желание доказать что-либо, относящееся к свойствам алгоритмов или к их возможностям. Этот аспект проблемы отражен в статье "Теория алго­ритмов".

Здесь же речь пойдет о практическом аспекте, связанном с понятием алгоритма и с широким ис­пользованием этого понятия в программировании и вычислительной технике. Ведь всякий алгоритм есть некоторая программа действия, а машинные программы с этой точки зрения и есть точные инс­трукции на выполнение некоторых процедур. Это наводит на мысль, что программы — это записи не­которых алгоритмов, а программирование есть про­цесс перевода записей алгоритмов на язык, понятный машине.

От программ мы ожидаем практической ре­зультативности. Вряд ли могут представлять инте­рес программы, которые никогда не приводят к результату. Поэтому и в практическом аспекте важно уточнить понятие алгоритма.

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

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

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

2. Данные для своего размещения требуют па­мяти. В ЭВМ память состоит из одинаковых ячеек, каждая из которых может содержать один или не­сколько символов алфавита данных. Таким обра­зом, единицы объема данных и памяти согласованы, и в прикладных алгоритмических моделях объем данных можно измерять числом ячеек, в которых данные размещены.

3. Элементарные шаги алгоритма состоят из базовых действий, число которых конечно. В при­кладных алгоритмических моделях под действиями можно подразумевать машинные команды, входя­щие в состав системы команд ЭВМ. При записи ал­горитмов на языках программирования более высокого уровня, чем машинный язык, в качестве базовых действий могут выступать операторы, входящие в состав синтаксиса данного языка програм­мирования.

4. Последовательность шагов алгоритма должна быть однозначной. Не допускается произвола при выборе очередного шага алгоритма. Обязатель­но должны быть зафиксированы начальный и за­ключительный шаги алгоритма.

Все шаги, которые встречаются в алгоритме, можно разделить на условные и безусловные. После безусловного действия либо выполняется действие, расположенное вслед за ним в описании, либо од­нозначно указывается, какой шаг надо выполнять. Условное действие связано с проверкой условия и указывает два действия, которые могут последовать за ним: одно выполняется, если условие соблюдено;

другое — если не соблюдено. Примером такого дей­ствия является команда условного перехода.

5. Точность записи алгоритма связана с ис­пользованием жесткого синтаксиса. Любая синтак­сическая вольность (скажем, замена запятой на точку с запятой), любая ошибка в синтаксисе будут обнаружены и потребуют исправления.

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

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

Дано: последовательность чисел.

Требуется: найти в этой последовательности максимальное число.

Метод решения:

1. В некоторой памяти М запоминаем первое число.

2. Следующее число последовательности срав­ниваем с числом, лежащим в М. Записываем в М большее из этих чисел (т. е. либо сохраняем в М прежнее число — если оно больше, — либо запи­сываем вместо него следующее).

3. Повторяем шаг 2 до конца данной последо­вательности.

Сразу же возникают вопросы, которые можно разделить на две группы (хотя они и связаны).

Вопросы к постановке задачи:

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

б) Что значит "найти максимальное число" — просто дать его значение или, кроме того, указать еще и его место в последовательности? Предлагае­мый метод решения дает только значение. Если нужно указывать место числа, то числа последова­тельности нужно как-то нумеровать или именовать, а метод решения изменить. Кроме того, как быть, если найдено несколько одинаковых максимальных чисел — указывать все их места или, например, первое по порядку?

Ответы на эти вопросы неоднозначны. Дать их может только тот, кто ставит задачу. Предположим, что в нашем случае ответы таковы: числа — целые и кроме значения результата нужно указать еще и номер первого по порядку максимального числа, по­этому числа последовательности должны быть как-то пронумерованы.

Вопросы к методу решения:

а) Как искать следующее число? В длинной по­следовательности это требует аккуратности даже при ручной работе. Можно, например, зачеркивать или как-то удалять уже просмотренные числа, и тогда следующее число — это первое незачеркну­тое, а можно иметь некоторый указатель, работать с числом, на которое он указывает, а потом пере­двинуть его на следующее число. Поскольку уже решено, что числа последовательности будут про­нумерованы, то таким указателем может служить специальная переменная — счетчик номеров, зна­чение которой после каждого сравнения увеличи­вается на единицу.

б) Как определить конец последовательности? Есть два стандартных способа: либо при ее вводе указать количество ее элементов (чисел), либо вве­сти дополнительный элемент — признак конца. Ос­тановимся на первом варианте.

Теперь описанный выше процесс можно описать более точно. Для записи чисел в память будем пользоваться обычным для языков программирова­ния оператором присвоения. Например, М: = х оз­начает, что переменной М присвоено значение переменной х; в терминах машинной памяти это значит, что в ячейку памяти М записано содержи­мое ячейки х.

1. Ввести данные: исходную последователь­ность расположить в ячейках р(1), ..., р(п).

1. е: = п (в ячейке е лежит число элементов последовательности).

3. i:= 1 (счетчик номеров устанавливаем в на­чальное положение).

4. М: =р(1) (в М — первое число).

5 .N:=1 (в N — его номер).

6. i: =i + 1 (счетчик увеличивается на 1).

7. Если ,то перейти к п.10; иначе перейти к следующему шагу (п. 8).

8. М: =p(i) (в М — новое число ).

9. N:=i (в N — его номер).

10. Если i < е, то перейти к п. 6; иначе — к сле­дующему шагу.

11. Конец алгоритма.

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

вставить после шага 10 шаг, связанный с выводом результата (на печать или экран), и записать алгоритм на выбран­ном языке, строго соблюдая его синтаксис.

Алгоритм является фундаментальным поняти­ем информатики. Можно выделить три крупных класса алгоритмов: вычислительные, информаци­онные и управляющие. Вычислительные алгорит­мы, как правило, работают со сравнительно простыми видами данных (числа, матрицы), но сам процесс вычисления может быть долгим и сложным. Информационные алгоритмы представляют собой набор сравнительно простых процедур (например, поиск числа или слова, удовлетворяющего опреде­ленным признакам), но работающих с большими объемами информации. Таковы алгоритмы в раз­личных базах данных. Для того чтобы они работали эффективно, важно иметь хорошую организацию данных. Например, чтобы в картотеке можно было быстро найти нужные сведения, эти сведения нужно постоянно поддерживать в определенном порядке (по разделам, внутри разделов по алфавиту и т. д.). Управляющие алгоритмы характеризуются тем, что данные к ним поступают от внешних процессов, ко­торыми они управляют. Результаты работы этих алгоритмов представляют собой различные управляющие воздействия. Поэтому значения данных в ходе работы управляющих алгоритмов меняются (иногда очень быстро), и алгоритм должен вовремя правильно отреагировать, т. е. выдать нужный управляющий сигнал в нужный момент.

Блок-схема алгоритма

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

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

Безусловные шаги принято изображать прямо­угольниками, условные шаги — ромбами. Из ромба всегда выходят две стрелки: одна имеет пометку "да" (условие выполнено), другая — пометку "нет" (условие не выполнено). Граф, изображенный на рис. 1, соответствует процессу отыскания макси­мального числа в последовательности, который опи­сан в статье "Алгоритм".

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

Рис.1.

Рис.2.

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

Поэтому возможны два варианта прохождения цикла 6, 7, 8, 9, 10, 6 и 6, 7, 10, 6. Цикл обязательно содержит условную вершину, в которой можно выйти из цикла. В дан­ном примере такой вершиной является шаг 10. Вы­ход из цикла происходит, когда все числа последовательности просмотрены. Если условия вы­хода из цикла сформулированы неправильно, то мо­жет оказаться, что они никогда не выполняются, и процесс исполнения алгоритма становится беско­нечным (он, как говорят, зацикливается, что явля­ется типичной программистской ошибкой).

Для компактного описания циклов в языках программирования имеются специальные операто­ры циклов. Основную часть нашего примера (шаги 2 — 10) с помощью такого оператора можно запи­сать гораздо короче. Правда, оператор цикла нельзя считать элементарным шагом, в частности, потому, что время его выполнения зависит от исходных дан­ных и может быть сколь угодно большим.

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

Крупный шаг — это фактически алгоритм, яв­ляющийся частью (подалгоритмом) более сложного алгоритма. Такие подалгоритмы называются блоками. Блок обычно не элементарен (его размеры неограниченны и выбираются произвольно). Одна­ко правильно сформулированный блок обладает всеми другими признаками алгоритмического ша­га. В частности, он имеет точно выделенное начало (точку входа) и может быть условным или безус­ловным. У безусловного блока — всегда одна точка выхода. Условный блок имеет несколько точек вы­хода (их может быть больше двух, если блок содер­жит несколько условий). Другие блоки алгоритма связаны с данным блоком только через точки входа и выхода. Поэтому если блок правильно решает свою задачу, т. е. всегда дает нужный результат, то его внутренняя структура несущественна для остальной части алгоритма. Из этого следуют два важных вывода. Во-первых, описание алгоритма можно представлять в укрупненном блочном виде. Отсутствие детального описания внутренней структуры блоков не мешает пониманию того, как работает алгоритм в целом; важно лишь, чтобы было четко определено, какие блоки запускают данный блок в работу, где лежит его исходная ин­формация, где будет записан результат и куда пе­реходить после окончания его работы. Такое блочное представление особенно удобно на первых этапах разработки алгоритмов (детализация бло­ков происходит позднее). Во-вторых, детализацией разных блоков (т. е. программированием — дове­дением их до настоящих алгоритмов и программ) могут заниматься разные люди независимо друг от друга. Это важно при организации работ по созда­нию сложных программ.

Блок-схемы являются частным случаем на­глядных форм представления алгоритмов. Сущест­вуют и другие способы представления: операторные алгоритмы, диаграммы смены состояний и т. п. Раз­вивается и теория таких представлений. С ней мож­но познакомиться в статье «Схема алгоритма».

Схема алгоритма

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

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

Рис. 1

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

Кроме блок-схем используются и другие спосо­бы отображения структуры алгоритмов и программ. Но они получили гораздо меньшее распростране­ние, чем блок-схемы. Правда, для теоретических исследований в начале развития теории программирования использовались специальные операторные схемы алгоритмов, предложенные советским иссле­дователем А. А. Ляпуновым. На рис. 2 тот же алгоритм поиска наибольшего общего делителя двух натуральных чисел представлен в виде записи через операторы Ляпунова. Буквами А_i обозначены вычислительные операторы, Р_i — логические операторы, Ф_i — операторы ввода, О_i — операторы вывода, S — оператор прекращения алгоритма, — операторы безусловного перехода. Выполнение операторов происходит слева направо в порядке их написания. Если очередной оператор есть Р„ то при отрицательном результате проверки начинает выполняться соседний правый в записи оператор. При положительном результате проверки условия происходит переход по стрелке. При выходе на оператор всегда происходит переход по стрелке. При сложных алгоритмах стрелки, характеризующие переходы, целиком не рисуются, чтобы не загромождать схему, рисуется лишь начало и конец стрелки, помечаемые одинаковыми номерами, а са­ми стрелки пишутся в той же строке, что и операторы. Такая запись показана на рис. 2, но ниже первой.