4. Виды алгоритмов. Свойства и способы задания алгоритмов.

Выделяют следующие виды алгоритмов : линейный, разветвляющийся, циклический, комбинированный.

Алгоритм, который содержит сразу несколько структур называется КОМБИНИРОВАННЫМ.

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

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

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

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

Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.^{[источник не указан 518 дней]} С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.

Результативность — завершение алгоритма определёнными результатами.

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

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

Способы задания алгоритма.

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

— словесная (запись на естественном языке);

— графическая (изображения из графических символов);

— псевдокоды (полуформализованные описания алгоритмов на ус­ловном алгоритмическом языке, включающие в себя как элементы язы­ка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

— программная (тексты на языках программирования). Словесный способ записи алгоритмов представляет собой описание последователь­ных этапов обработки данных.

Словесный способ

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задаётся в про­извольном изложении на естественном языке.

Пример. Записать алгоритм нахождения наибольшего общего дели­теля (НОД) двух натуральных чисел (алгоритм Евклида).

Алгоритм может быть следующим:

1)     Задать два числа.

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

3)   Определить большее из чисел.

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

5)   Повторить алгоритм с шага 2.

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

Графический способ

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

 

Название	Блок-схема	Пояснение
Пуск-останов		Начало, конец алгоритма, вход и выход в подпрограмму
Процесс		Вычислительное действие или последовательность действий
Решение		Проверка условий
Модификация		Начало цикла
Предопределён­ный процесс		Вычисления по подпрограмме
Ввод-вывод		Ввод-вывод в общем виде

 

Блок «процесс» применяется для обозначения действия или последо­вательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько от­дельных блоков обработки можно объединять в один блок. Представле­ние отдельных операций достаточно свободно.

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

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

Блок «предопределённый процесс» используется для указания обращении к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным подпрограммам.

Псевдокод

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

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

Таблица 1.7. Служебные слова алгоритмического языка.

алг(алгоритм)	сим (символьный)	дано	да	нет
арг(аргумент)	лит (литерный)	надо	для	при
рез(результат)	лог(логический)	если	от	до
нач(начало)	таб (таблица)	то	знач	выбор
кон(конец)	нц(начало цикла)	иначе	и	или
цел (целый)	кц (конец цикла)	всё	ввод	вывод
вещ (вещественный)	длин(длина)	пока	утв	не

Общий вид алгоритма:

алг название алгоритма (аргументы и результаты)

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

надо цель выполнения алгоритма

нач описание промежуточных величин

последовательность команд (тело алгоритма)

кон.

Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключённая между словами нач и кон — телом алгоритма.

Программный способ записи алгоритмов

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