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

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

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

Алгоритм

3.

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

4.

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

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

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

6.

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

7.

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

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

Рассмотрим основные способы
описания алгоритмов:
*Словесная запись алгоритма
*Графическая запись алгоритма
*Псевдокоды
*Языки программирования

9. Словесная запись алгоритма

Словесная форма обычно используется для алгоритмов, ориентированных на
исполнителя – человека. Команды алгоритма нумеруют, чтобы иметь возможность
на них ссылаться.
Пример. Рассмотрим классический алгоритм Евклида для нахождения
наибольшего общего делителя двух натуральных чисел:
1. Если числа равны, то взять первое число в качестве ответа и закончить
выполнение алгоритма, иначе перейти к п.2.
2. Определить большее из двух чисел.
3. Заменить большее число на разность большего и меньшего чисел.
4. Перейти к п. 1.
Команды этого алгоритма выполняется в естественной последовательности, если
не оговорено противного. Так, после второй команды будет выполняться третья,
после третьей – четвертая, а после выполнения четвертой команды необходимо
вернуться к снова к выполнению первой команды, т. к. это явно оговорено в
четвертой команде. Команды такого типа (команды перехода) нарушают
естественный порядок выполнения команд алгоритма.
Форма записи команд не формализуется. В командах помимо слов могут
использоваться символы и формулы. Важно лишь то, чтобы каждая команда была
понятна исполнителю, точно определяла все его действия и могла быть им
выполнена.

10. Графическая запись алгоритма

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

11. Графическая запись алгоритма

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

12. Правила создания блок – схем:

1.Линии, соединяющие блоки и указывающие
последовательность связей между ними, должны проводится
параллельно линиям рамки.
2.Из блока (кроме логического) может выходить только одна
линия.
3.Логический блок может иметь в качестве продолжения один
из двух блоков, и из него выходят две линии.
4.Если на схеме имеет место слияние линий, то место
пересечения выделяется точкой.
5.Схему алгоритма следует выполнять как единое целое,
однако в случае необходимости допускается обрывать линии,
соединяющие блоки.

13. Псевдокоды

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