Лекция №5. Алгоритм. Свойства алгоритма. Способы описания

Лекция №5.

Алгоритм. Свойства алгоритма. Способы описания.

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

Понятие алгоритма

Понятие алгоритма относится к фундаментальным концепциям информатики, хотя и возникло задолго до появления ЭВМ, и стало одним из основных понятий математики.

Слово "алгоритм" произошло от имени среднеазиатского математика Мухамеда из Хорезма (по-арабски - Аль Хорезми (IX в)) и использовалось в математике для обозначения правил выполнения четырех арифметических действий: сложения, умножения, вычитания и деления.

Мухаммед Аль Хорезми подробно объясняет правила действия с числами, записанными в десятично-позиционной системе счисления, и исследует квадратные уравнения. Слова "алгебра" и "алгоритм" впервые появились в переводе его трактатов. Первое из них означало операцию переноса членов из одной части уравнения в другую, а второе – искаженное имя автора – Аль Хорезми – Algorithmi. Оно применялось первоначально для обозначения правил вычисления в десятичной позиционной системе счисления.

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

Интуитивное понятие алгоритма, которым люди пользуются уже много лет, можно выразить следующим образом:

Алгоритм – это строгая последовательность действий, приводящая за конечное число шагов к достижению поставленной цели (к решению поставленной задачи).

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

Исполнитель алгоритма – это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнять действия, предписываемые алгоритмом.

Исполнителя характеризуют:

·  Среда;

·  Система команд;

·  Отказы.

Среда (обстановка) – это "место обитания" исполнителя. Например, среда ТР.

Система команд. Отдельные указания исполнителю, содержащиеся в каждом шаге алгоритма, называют командами. Исполнители отличаются друг от друга возможностями - наборами команд, которые они "понимают" и умеют выполнять. Совокупность команд, которые могут быть выполнены конкретным исполнителем, называется Системой Команд Исполнителя (СКИ).

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

Свойства алгоритма

1.  Результативность. Алгоритм имеет некоторое число входных величин – аргументов, задаваемых до начала работы. Цель выполнения алгоритма – получение результата (результатов), имеющего вполне определенное отношение к исходным данным. Можно сказать, что алгоритм указывает последовательность действий по преобразованию исходных данных в результаты.

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

3.  Понятность. Чтобы алгоритм можно было выполнить, он должен быть понятен исполнителю. Понятность алгоритма означает знание исполнителя алгоритма о том, что надо делать для его исполнения.

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

4.  Дискретность. Алгоритм представлен в виде конечной последовательности шагов. Говорят, что алгоритм имеет дискретную структуру. Следовательно, его исполнение расчленяется на выполнение отдельных шагов (выполнение каждого последующего шага начинается только после выполнения предыдущего).

5.  Конечность. Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут выполняться многократно.

В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Например, процедура вычисления числа π. Такая процедура описывает бесконечный процесс и никогда не завершится. Если же прервать ее искусственно, например, ввести условие завершения процесса вычислений вида: "Закончить вычисления после получения п десятичных знаков числа", то получится алгоритм вычисления п десятичных знаков числа π. На этом принципе основано получение многих вычислительных алгоритмов: строится бесконечный, сходящийся к искомому решению процесс. Он обрывается на некотором шаге, и полученное значение принимается за приближенное решение рассматриваемой задачи. При этом точность приближения зависит от числа шагов.

6.  Определенность. Каждый шаг алгоритма должен быть четко и недвусмысленно определен и не должен допускать произвольной трактовки исполнителем. При исполнении алгоритма исполнитель должен действовать строго в соответствии с его правилами и у него не должно возникать потребности предпринимать какие-либо действия, отличные от предписанных алгоритмом. Иными словами, алгоритм рассчитан на чисто механическое исполнение. Это означает, что если один и тот же алгоритм поручить для исполнения разным исполнителям, то они придут к одному и тому же результату, лишь бы исполнители понимали алгоритм.

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

7.  Эффективность. Алгоритм должен быть эффективен – значит, действия исполнителя на каждом шаге исполнения алгоритма должны быть достаточно простыми, чтобы их можно было выполнить точно и за конечное время. Кроме того, эффективность означает, что алгоритм может быть выполнен не просто за конечное, а за разумное конечное время (обычно важно, чтобы задача по разработанному алгоритму решалась как можно быстрее). Вот почему при разработке алгоритмов должны учитываться и возможности конкретных физических исполнителей алгоритма.

Самостоятельно нормальные алгоритмы Маркова

Способы описания алгоритмов

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

Рассмотрим основные способы описания алгоритмов.

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

Пример. Рассмотрим классический алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел:

1.  Если числа равны, то взять первое число в качестве ответа и закончить выполнение алгоритма, иначе перейти к п.2.

2.  Определить большее из двух чисел.

3.  Заменить большее число на разность большего и меньшего чисел.

4.  Перейти к п. 1.

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

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

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

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

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

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

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

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

алгоритм числогласных;

начало

записать в счетчик 0;

установить указатель на первый символ текста;

пока символ не есть $

повторять

начало

если символ есть гласная буква русского алфавита

то счетчик увеличить на 1

все;

перевести указатель на следующий символ текста

конец;

взять число, находящееся в счетчике, в качестве ответа

стоп

конец

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

Языки программирования. При записи алгоритмов в словесной форме, в виде схемы или на псевдокоде допускается определенный произвол при изображении команд. Вместе с тем такая запись настолько точна, что позволяет человеку понять суть задачи и исполнить алгоритм.

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

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

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

Однако создание языков программирования высокого уровня само по себе не обеспечивало полностью возможность решения задачи на ЭВМ. Для этого необходим перевод (трансляция) программы с языка высокого уровня на язык машины.

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

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

Транслятор выполняет следующие основные функции:

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

2.  производит генерацию машинной команды – непосредственную трансляцию исходной программы на машинный язык.

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

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

В связи с этим в операционной системе может быть несколько трансляторов для одного и того же языка программирования.

Структуры алгоритмов

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

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

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

При исполнении алгоритма обработка информации состоит в изменении значений некоторых величин, с которыми работает алгоритм. Величины могут быть постоянными и переменными. Значения постоянных величин остаются неизменными в процессе исполнения алгоритма, а значения переменных могут изменяться.

С величиной помимо значения связано также имя, используемое для обозначения. В качестве имени используется идентификатор, т. е. последовательность букв и цифр, начинающаяся с буквы, например, x, x1 Alfa,...

Значение переменной величины может быть изменено с помощью команды присваивания, имеющей общий вид

< идентификатор>:= <выражение>

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

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

присвоить это значение переменной, имя которой стоит в левой части команды. Например, команда x:=1 означает, что переменной х присваивается значение 1, а команда y:=y+1 - что переменной y присваивается значение, которое на 1 больше прежнего ее значения.

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

ввод (x, y)

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

вывод (x, y)

означает, что исполнитель должен выдать для отображения значения величин x, y.

Простая команда на языке блок-схем изображается в виде функционального блока, имеющего один вход и один выход:

Присваивание ввод-вывод

 

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

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

В общем виде команда следования может быть представлена так:

 

начало

<действие>;

<действие>; ………

...;

<действие> ………

конец

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

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

Пример.

начало

ввод (х);

у:=х2 + 5;

z:=

конец

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

На псевдокоде эта команда в общем виде записывается так:

если <условие>

то <действие 1>

иначе <действие 2>

все

Действия, указанные после служебных слов то и иначе, могут быть простыми или составными командами. При исполнении команды ветвления выполняется только одно из действий: если условие соблюдено, то выполняется действие1, в противном случае - действие2.

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

если <условие>

то <действие >

все

Пример.

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

.....

На псевдокоде команда ветвления для вычисления значения у будет иметь такой вид:

если x>=0

то y:=x + 1

иначе y:=x^2

все

В команде ветвления после служебных слов то и иначе может стоять составная команда.

Пример.

если x>=0

то

начало

y:=x + 1;

z:= y

конец

иначе y:=x^2

все

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

Команда повторения с предусловием записывается на псевдокоде следующим образом:

пока <условие >

повторять <действие>

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

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

 

Команда повторения с постусловием выполняется аналогично, только условие проверяется после выполнения команды, а повторение выполнения команды происходит в том случае, когда условие не соблюдено, т. е. повторение производится до соблюдения условия (поэтому этот тип цикла называют также циклом “до"). На псевдокоде цикл с постусловием записывается следующим образом:

повторять <действие>

до <условие >

Под действием, как и прежде, понимается простая или составная команда.

Пример.

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

Пусть векторы x и y заданы своими координатами x1,x2,...,xn и y1,y2,...,yn. Требуется найти и скалярное произведение:

n

сумма = xi×yi.

i=1

Запишем это вычисление на псевдокоде, используя команду цикла с предусловием:

сумма := 0;

i:=1;

пока i<= n

повторять

начало сумма:= сумма + xi×yi;

i:=i + 1;

конец;

Этот же фрагмент может быть записан с использованием команды цикла с постусловием:

сумма := 0;

i:=1;

повторять

начало сумма:= сумма + xi×yi;

i:=i + 1;

конец;

до i> n

Цикл с параметром (известным количеством повторений)

 

N1, N2 - выражения, определяющие соответственно начальное и конечное значения параметра цикла, N3 –шаг изменения параметра цикла.

Если N1< N2, то N3 >0.

Если N1> N2, то N3 <0.

3. Комбинации базовых команд. Из теории известно, что любой алгоритм может быть построен с использованием только базовых конструкций: следования, развилки и цикла. Это превращает построение алгоритма в "сборку" его конструкции из имеющегося набора базовых конструкций, подобно тому, как конструктор собирает механизм из конечного набора имеющихся в его распоряжении деталей.

"Сборка" алгоритма может происходить двумя путями.

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

2. Одна базовая конструкция может вкладываться в другую конструкцию, образуя "вложенные" конструкции. Это также возможно, т. к. внутри составных команд могут находиться другие составные команды.

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

Строгая дисциплина конструирования алгоритма позволяет получить алгоритм с ясно выраженной структурой, что облегчает понимание и доказательство его правильности. При записи алгоритма на псевдокоде получается текст, который можно читать без перерыва сверху вниз, как обычный текст. Кроме того, последовательная структура полученного при конструировании алгоритма означает, что при его исполнении команды будут выполняться в том порядке, в котором они появляются в тексте алгоритма. Это значительно облегчает переход от статического объекта - текста алгоритма - к динамическому процессу его исполнения.

Приведем примеры алгоритмов, построенных по этому принципу.

Пример.

Вычисление факториала числа. Известно, что n! = n-1)n. Поэтому процесс вычисления n! может быть описан с помощью команды цикла.

алгоритм факториал;

начало

ввод(n);

f := 1;

k:=0;

пока k n

повторять

начало

k := k+1

f := f*k

конец

конец

В алгоритме используется команда цикла с предусловием. Это имеет принципиальное значение, т. к. такой алгоритм будет работать верно и при n=0. Действительно, в этом случае действия, заданные командой цикла, не будут ни разу выполнены и в результате будет выдан верный ответ f=1 (по определению, 0!=1).

Алгоритм нахождения суммы 10 элементов массива

.....

4. Вспомогательные (подчиненные) алгоритмы. Часто при построении алгоритма оказывается возможным использовать уже разработанные ранее алгоритмы. Так при построении алгоритма по принципу "сверху вниз" обычно стараются всю задачу разбить на более простые подзадачи, и если для какой-то подзадачи уже построен алгоритм, то он может быть включен в состав вновь разрабатываемого алгоритма. Это позволяет не повторять уже проделанную работу, сэкономить время на разработку нового алгоритма, а также избежать при записи нового алгоритма повторения в ней текста в той его части, которая уже описана в готовом алгоритме.

Готовые алгоритмы, целиком включаемые в состав разрабатываемого алгоритма, называют вспомогательными алгоритмами в отличие от главного или основного алгоритма, в состав которого они вставляются.

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