Преподаватель который помогает студентам и школьникам в учёбе.

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

Содержание:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис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.

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

Рис 4. Блок-схема примера рекурсивного алгоритма

Понятие блок-схема. Смысловые блоки блок-схемы.

Приведем точное определение блок-схемы

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

На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт — ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем» .

Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.

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

Рис 1. Виды смысловых блоков для блок-схем и их описание

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

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

Литература

Ефимова О., Морозов В., Угринович Н. Курс компьютерной технологии с основами информатики. Учебное пособие для старших классов. - М.: ООО "Издательство АСТ"; АВF, 2000 г.
Задачник-практикум по информатике. В 2-х томах/Под ред. И.Семакина, Е.Хеннера. - М.: Лаборатория Базовых Знаний, 2001 г.
Угринович Н. Информатика и информационные технологии. 10-11 класс- М.: Лаборатория Базовых Знаний, АО "Московские учебники", 2001 г.
[Электронный ресурс]. URL: http://www.fvn2009.narod.ru/Examinations/Tickets/Tickets2.htm
ГОСТ 19.701–90 (ИСО 5807–85) «Единая система программной документации».
Алгоритм. Свойства алгоритма [Электронный ресурс]. URL: https://pro-prof.com/archives/578
Алгоритмы сортировки слиянием и быстрой сортировки [Электронный ресурс]. URL: https://pro-prof.com/archives/813
yEd Graph Editor [Электронный ресурс]. URL: https://www.yworks.com/products/yed
Книги: алгоритмы [Электронный ресурс]. URL: https://pro-prof.com/books-algorithms