Реферат: Интуитивное понятие алгоритма и его свойств

действия над данными (например, сравни, вычти, положи);

действия, изменяющие “естественный” порядок вычислений (например, если - то - иначе; перейди к шагу #).

Если присмотреться внимательней, то мы увидим, что действия вида “сравни”, “вычти” и действия вида “положи ” - это разные действия. Разница между ними в том, что действия первого вида указывают что делать с его операндами, но не указывают где “сохранить” полученный результат. Действия второго вида, наоборот “умалчивают” каким образом получено значение, которое надо “сохранить” в качестве нового значения переменной.

Теперь пристальнее рассмотрим правило окончания алгоритма и выбора результата. В алгоритме могут быть использованы десятки переменных, но результат будет храниться лишь в нескольких. Эти “результирующие” переменные должны быть явно указаны в алгоритме, т.к. в противном случае нет никакой возможности их выявить. Момент, когда в этих переменных сформированы нужные значения, определяет правило окончания алгоритма. Правило окончания всегда формулируется как некоторое условие на множестве текущих значений переменных. Достижение этого условия и означает, что в определенных переменных получен результат. В нашем примере таким условием является равенство текущего значения переменной а текущему значению переменной b.

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

Данные в алгоритме могут быть представлены переменными (в нашем примере именуемые a и b), либо явно, в виде постоянной величины - константы (в нашем примере n и m), которая не меняет своего значения в конце выполнения алгоритма.

Переменная - это имя, с которым связано конкрентное множество значений. В каждый конкретный момент времени исполнения алгоритма каждая переменная принимает одно конкретное значение, из связанного с ней множества.

Определение 1.1

Типом переменной называется множество возможных ее значений.

Пусть у нас есть множество переменных {v_i |i=1,k}. (Примеры!)

Определение 1.2

Состоянием на множестве переменных {v_i |i=1,k} называется набор значений этих переменных.

Пусть А - алгоритм, {v_i |i=1,k} - набор всех переменных, используемых в этом алгоритме. Добавим к этому набору еще одну переменную p, тип которой есть множество индексов действий в алгоритме. Каждый шаг исполнения алгоритма можно однозначно охарактеризовать сосотоянием на множестве переменных ({v_i |i=1,k},p).

Определение 1.3

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

Определение 1.4

Состоянием вычислительного процесса, порожденного алгоритмом А, называется состояние на множестве переменных ({v_i |i=1,k},p), где{v_i |i=1,k} - набор всех переменных, используемых в алгоритме А.

Нетрудно видеть, что вычислительный процесс можно описать в виде последовательности его состояний.

Определение 1.5

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

Определение 1.6

Результат - это определенная совокупность значений из терминального состояния вычислительного процесса алгоритма.

Определение 1.7

Действие - переход из одного состояния в другое.

Действительно, если действие связано с преобразованием каких-либо данных, то правильность этого утверждения очевидна. Если же действие связано с изменением “естественного” порядка выполнения действий в алгоритме, то состояние вычислительного процесса меняется все равно, т.к. изменяется значение специальной переменной p - индекс действия.

Рассмотрим еще один пример. Пусть нам надо построить алгоритм для решения следующего класса задач:

вычислить значение выражения , в точке x=b, где

a_i ÎR, bÎR, где R - множество вещественных чисел.

Множество исходных данных: , где a_i ÎR, bÎR.