Понятие алгоритм. Свойства алгоритмов. Способы представления алгоритмов. Блоки, используемые для построения блок-схем и их функции
Слово "алгоритм" появилось в IX веке и произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса Ал-Хорезми (Alhorithmi). В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила выполнения четырех арифметических действий над многозначными числами.
В настоящее время понятие алгоритма является одним из фундаментальных понятий науки информатики.
Алгоритм – точное предписание, состоящее из последовательности действий для некоторого исполнителя, ведущих к решению задачи за конечное число шагов.
Алгоритм моделирует решение задачи в виде точно определенной последовательности действий для некоторого исполнителя по преобразованию исходных данных в результирующие. Процесс составления алгоритмов называют алгоритмизацией.
Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.
Исполнителя характеризуют: среда, элементарные действия, система команд, отказы.
Среда (или обстановка) — это "место обитания" исполнителя.
Система команд исполнителя – строго заданный список команд, который может выполнять каждый исполнитель. Для каждой команды должны быть заданы условия применимости (состояние среды, в которой выполняется команда) и описаны результаты выполнения команды.
После вызова команды исполнитель совершает соответствующее элементарное действие.
Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.
Обычно исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды, не задавая вопросов "почему" и "зачем".
Основным исполнителем несложных алгоритмов является человек. При решении сложных задач в роли исполнителя часто выступает ЭВМ.
Основные свойства алгоритмов:
– дискретность (прерывность). Алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов, при этом для выполнения каждого шага требуется конечный отрезок времени;
– определенность. Каждое правило алгоритма должно быть четким и однозначным. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче;
– результативность (или конечность) состоит в том, что за конечное число шагов алгоритм должен приводить к решению задачи или после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов;
– массовость означает, что алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Самый простой способ представления алгоритма – словесный, который содержит описание алгоритма на естественном языке (например, на русском). Выполнение предписаний алгоритма предполагается в естественной последовательности (в порядке записи), изменение порядка выполнения операций необходимо указать в явном виде, например, «перейти к шагу 3», в этом случае шаги алгоритма должны быть пронумерованы.
В формульно-словесном способе к словесному описанию добавляются формулы для определения значений переменных, при этом каждая переменная должна иметь уникальное имя – идентификатор.
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Алгоритмы на псевдокоде могут записываться и читаться как обычный текст
Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.
Псевдокод удобен для пошаговой разработки алгоритма.
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Примером псевдокода является школьный алгоритмический язык в русской нотации – «Школьный АЯ».
Операторный метод описания алгоритмов был разработан советским ученым Алексеем Андреевичем Ляпуновым в 1954 году. Операторная схема – аналитическая форма представления алгоритма с помощью операторов, отражающих содержание этапов. Арифметический оператор (вычисление) обозначается в русской транскрипции буквой А, логический – буквой Л, ввод данных – буквой В, печать – буквой П, начало – буквой Н, конец – буквой К.
Порядковый номер оператора, независимо от его типа, обозначается индексом. Операторы записываются в строку, для пояснения схемы переходов после логических операторов ставятся сверху или снизу горизонтальные стрелки, указывающие место перехода. Если операторы выполняются в естественном порядке, между ними не ставится разделитель, если после i-го оператора (i+1)-й не выполняется, между ними ставится разделитель – точка с запятой. Для логических операторов возможно указание условия, по которому программа разветвляется на ветви.
Операторный метод дает наглядное логическое представление алгоритма, однако он был вытеснен графическим способом, который оказался более компактным и наглядным.
При графическом способе представления алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий