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

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

Алгоритм

Алгоритм – заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов.

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

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

· Среда;

· Элементарные действия;

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

· Отказы.

Среда (или обстановка) – это «место обитания» исполнителя.

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

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

1. Понятность для исполнителя – исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для этого алгоритма.

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

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

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

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

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

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

· Гибкие алгоритмы:
- вероятностные (стохастические) алгоритмы дают программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата;
- эвристические алгоритмы – это алгоритмы, в которых достижение конечного результата программы действий однозначно не определено, так же как не обозначена вся последовательность действий исполнителя.

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

· Линейные алгоритмы – наборы команд (указаний), выполняемых последовательно во времени друг за другом;

· Разветвляющиеся алгоритмы – алгоритмы, содержащие хотя бы одно условие, в результате проверки которого компьютер обеспечивает переход на один из двух возможных шагов;

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

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

Дата добавления: 2014-01-07