Основные свойства алгоритма.
Введение
Теория алгоритмов вместе с математической логикой составляют теоретическую основу для проектирования и применения вычислительных устройств к плохо формализуемым объектам. Именно, благодаря теории алгоритмов происходит внедрение математических методов в экономику, лингвистику, психологию, педагогику и другие гуманитарные науки.
Наиболее простые примеры алгоритмов известны нам из начальной школы. Это алгоритмы сложения, вычитания, умножения и деления целых чисел в десятичной системе счисления. Аналогичные алгоритмы известны и для произвольных систем счисления.
В качестве другого примера можно привести классический алгоритм Евклида (нахождения наибольшего общего делителя (НОД) двух натуральных чисел, отличных от нуля). Приведем описание этого алгоритма.
Задана пара натуральных чисел, т.е. 
, причем 
.
1) Делим a1 на a2.. Процесс деления записываем в общем виде:
a1 = a2 
b1 + r1.
Если r1=0, то НОД = 
.
Если r1 0, то переходим ко второму этапу.
2) Делим a2 на r1 . Процесс деления записываем в общем виде:
a2= r1b2 + r2 .
Если r2=0 , то НОД( 
r1 )=r1
Если r2 0, то переходим к следующему этапу и т.д.
В итоге имеем последовательности равенств:
a1 = a2 
b1 + r1.
a2= r1 b2 + r2
………………..
rn-2 = rn-1 bn + rn
rn-1 = rn bn+1 + rn+1
Таким образом, получили убывающую последовательность натуральных чисел
a2 > r1> r2 >...> rn > rn+1 0,
которая должна быть конечной, так как a2 N . Поэтому для некоторого n, rn+1=0, и в силу равенств НОД( a1,a2 )=НОД(a2,r1)=НОД(r1,r2)=...=НОД(rn1,rn)=
=НОД( rn,0) = rn .
Не трудно заметить, что в этом описании повторяется многократно одно и тоже действие (деление большего числа на меньшее), меняются лишь числа, компоненты действия, причем меняются они определенным образом, закономерно.
Возникает вопрос: нельзя ли построить такое предписание, чтобы действие деления содержалось в нем лишь один раз, но было бы точно определено, до каких пор надо повторить это действие и над какими числами оно выполняется в каждом повторении?
Данный вопрос решается положительно, но при этом придется исходным переменным a1 и a2 на каждом шагу присвоить новые значения. Тогда получаем следующее предписание:
1. Разделить a1 на a2. Перейти к пункту 2.
2. Если r = 0, то перейти к пункту 4, иначе – к пункту 3.
3. Присвоить a1 значение a2, a2– значение r. Перейти к пункту 1.
4. НОД( 
) = a2 . Перейти к пункту 5.
5. Процесс окончен.
Таким образом, мы получили более компактные описание алгоритма Евклида.
Основные свойства алгоритма.
1.Дискретность. Она проявляется в том, что процесс построения величин, задаваемый алгоритмом, протекает в дискретном времени следующим образом: в начальный момент задается исходная конечная система величин, а в каждый следующий момент система величин получается по определенному закону из системы величин, имевшихся в предыдущий момент времени.
2. Детерминированность (определенность) – система величин, получаемых в любой, отличный от начального, момент времени, однозначно определяется системой величин, полученных в предшествующие моменты времени.
3. Элементарность шагов – закон получения последующей системы величин из предшествующей должен быть простым.
4. Эффективность (результативность)– каждый шаг работы алгоритма должен заканчиваться результатом.
5. Массовость алгоритма – начальная система величин может выбираться из некоторого потенциально бесконечного счетного множества Х.
6. Конструктивность – объекты из Х, над которыми работает алгоритм, должны быть конструктивными (конструктивный объект –это такой объект, который может быть набран весь целиком и представлен нам для рассмотрения).
Примерами конструктивных объектов являются булевы функции, формулы алгебры логики, натуральные и рациональные числа, матрицы с натуральными или рациональными элементами, многочлены от n неизвестных с рациональными коэффициентами и т.п.
В качестве примера объекта, не являющимся конструктивным, можно привести любые действительные числа, представление которых в десятичной записи не может быть целиком представлено для рассмотрения. Например, число e и не являются конструктивными объектами.
Подводя некоторый итог сказанному, можно дать и следующее объяснение термину «алгоритм»: под алгоритмом понимается единый метод решения определенного класса однотипных задач, обладающий свойствами дискретности, определенности, массовости, результативности и оперирующий конструктивными объектами.
В силу свойства конструктивности алгоритма между объектами счетного множества X и множества натуральных чисел N можно установить взаимно однозначное соответствие и в дальнейшем вместо объекта xX рассматривать его номер или код объекта, являющийся натуральным числом.
Таким образом, можно рассматривать работу алгоритма не на множестве X, а на более удобном для изучения множестве натуральных чисел N. Поэтому в дальнейшем предметом наших рассмотрений будут служить преимущественно арифметические функции, т.е. функции, имеющие своими областями определения и множествами значений только множества натуральных чисел.
Необходимо также отметить, что, вообще говоря, не предполагается, что процесс применения алгоритма к исходным данным обязательно должен закончиться результатом через конечное число шагов. Процесс может оборваться безрезультатно или не закончиться вообще. В этом случае говорят, что алгоритм неприменим к рассматриваемым исходным данным.
В дальнейшем, при изложения данного курса мы будем иметь дело с арифметическими функциями, т.е. функциями, имеющими своими областями определения и множествами значений только множества натуральных чисел.