Файл: Понятие алгоритма, свойства алгоритма, способы представления алгоритма.pdf

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

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

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

Исполнителем алгоритма может быть как человек (кулинарные рецепты, различные инструкции, алгоритмы математических вычислений), так и техническое устройство.

Различные машины (компьютеры, промышленные роботы, современная бытовая техника) являются формальными исполнителями алгоритмов.

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

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

Для создания алгоритма (программы) необходимо знать:

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

Полученный алгоритм (программа) должен обладать следующим набором свойств:

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

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

Виды алгоритмов

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

Виды алгоритмов:

Линейный
Ветвящийся
Циклический

Рассмотрим каждый из этих видов алгоритмов.

Линейным алгоритмом - называется такой вычислительный процесс, при котором все этапы решения задачи выполняется в естественном порядке (друг за другом) следования записи этих этапов

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

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

Приведем пример Линейного алгоритмов, представленные в виде блок-схемы:

Рис1. Блок схема линейного алгоритма

Приведем пример алгоритмов ветвления, представленные в виде блок-схемы:

Рис 2. Блок схема алгоритма ветвления

Приведем пример циклического алгоритма, представленные в виде блок-схемы:

Рис 3. Блок-схема циклического алгоритма

Рекурсивный алгоритм

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

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

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

Рекурсивная функция – эта функция, которая вызывает саму себя. Это происходит в случае прямой рекурсии.

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

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

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

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

Словесная (записи на естественном языке)
Графический способ (в виде блок-схемы)
Текст на языке программирования (в виде программного кода)
Символьный (запись алгоритма с помощью условных знаков)

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

НЕДОСТАТКИ СЛОВЕСНОГО СПОСОБА:

отсутствие наглядности;
недостаточная точность.

ДОСТОИНСТВА: с его помощью можно описать любые алгоритмы, в том числе и вычислительные.

СПЕЦИАЛЬНЫЕ СОГЛАШЕНИЯ ДЛЯ СЛОВЕСНОЙ ЗАПИСИ АЛГОРИТМОВ:

1. Знак присваивания, слева от которого записывают ту переменную, которой присваивается значение, записанное справа от знака присваивания. Например, х: =х+1

2. Для задания значения исходных данных используют указания: ВВЕСТИ

3. Для запоминая промежуточных результата используют вспомогательные переменные.

4. Для указания начала и конца алгоритма используют указания: НАЧАЛО и КОНЕЦ.

5. Все шаги нумеруют.

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

Примеры блок схем были представлены ранее (см. рис 1-3)

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

Словесная и графическая форма записи алгоритма предназначены для человека. Алгоритм, предназначенный для исполнителя на компьютере, записывается на языке программирования (языке, понятном ЭВМ). Сейчас известно несколько сот языков программирования. Наиболее популярные: Бейсик, Си, Паскаль, Пролог, ПЛ, Ада и т.д.

Пример программы на языке программирования Pascal ABC:

PROGRAM RR;

VAR A,B,C, max: INTEGER;

BEGIN

WRITE(‘ ВВЕДИТЕ A, B, C');

READLN(A,B,C);

IF A>B THEN max:=A

ELSE max:=B;

IF C>max THEN max:=C;

WRITELN(max);

END.

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