Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.

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

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

Примеры:

1. «Проезд запрещен», «Не курить» - не алгоритмы;

2. «Придерживайтесь правой стороны», «Место для курения», «Вход» - не алгоритмы;

3. Сложение (умножение, вычитание, деление) двух чисел (т.е. N²N) столбиком – алгоритм.

Пример:

Упорядочить в порядке возрастания конечное множество М положительных чисел. Описание решения этой задачи в интуитивном смысле может быть:

Шаг 1:В М ищется наименьшее число

Шаг 2: Найденное число приписывается справа к возрастающей последовательности чиселR(в начальный моментRпусто) и вычеркивается из М;

Шаг 3: Если в М не осталось чисел, то перейти к шагу 4, в противном случае перейти к шагу 1;

Шаг 4: Конец. Результатом считать последовательностьR, построенную к данному моменту.

Это описание, которое кажется вполне ясным, далеко от алгоритма. Действительно, если М=⁹5,⁶2, (1/3)^/2, то в предложенном варианте решения поставленной задачи не указано, как искать наименьшее число.

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

Пояснения:

1. Приведенное наивное (интуитивное) определение алгоритма не является точным математическим определением, а лишь объясняет смысл слова «алгоритм», в котором это слово используется в математике.

2. Характеристиками алгоритма являются:

• детерминированность(определенность) – однозначность результата процесса при заданных исходных данных;

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

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

Основные требования к алгоритмам.

1. Очевидно, что каждый алгоритм имеет дело с данными: входными, выходными и промежуточными. В этом плане уточнение понятия алгоритм требует и уточнения понятия данных, т.е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать. Ясно, что эти объекты должны быть четко определены и отличимы как друг от друга, так и от «необъектов». В теории алгоритмов четкая определенность объектов обусловлена заданием их в формальном языке L=<A,S>, в котором символы конечного алфавита А рассматриваются как элементарные объекты для построения более сложных объектов конечными средствамиS(этот язык часто называется языком операндов в отличие от языка описания самого алгоритма – алгоритмического языка).

2. В дальнейшем будем различать:

• описание алгоритма (т.е. инструкции или программы);

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

• память данных алгоритма;

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

Пояснения:

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

2. Предполагается также, что память данных алгоритма однородна и дискретна, то есть состоит из одинаковых ячеек, каждая из которых может содержать только один символ алфавита данных. Вопрос о том, нужна ли одна память или несколько (в частности для входных, выходных и промежуточных данных алгоритма) может решаться по-разному.

3. Понятие задачи «в общем виде» уточняется при помощи понятия «массовая алгоритмическая проблема». Последняя задается серией отдельных единичных проблем и состоит в требовании найти единый алгоритм их решения (когда такого алгоритма не существует говорят, что рассматриваемая массовая алгоритмическая проблема неразрешима). Так, проблема численного решения уравнений данного типа и проблема автоматического перевода есть массовые алгоритмические проблемы: образующими их единичными проблемами являются в 1-м случае проблемы численного решения отдельных уравнений данного типа, а во 2-м случае - проблемы перевода отдельных фраз.

4. Алгоритмический процесс – есть процесс последовательного преобразование конструктивных объектов, происходящий дискретными шагами; каждый шаг состоит в смене одного конструктивного объекта другим. Так, при применении алгоритма вычисления (f:D²D) столбиком к паре <507, 38> последовательно возникают следующие конструктивные объекты:

_507 _507 _507 _507

38 38 38 38

469

Здесь возможными исходными данными служат пары чисел, возможными результатами – числа (все в десятичной системе счисления), а возможные промежуточные результаты суть трехэтажные записи вида , гдеq-

запись числа в десятичной системе, z- такая же запись или пустое слово, аp- запись числа в десятичной системе с допущением точек над некоторыми цифрами (точка означает заимствование из старшего разряда).