Основные свойства алгоритма.

Введение

Теория алгоритмов вместе с математической логикой составляют теоретическую основу для проектирования и применения вычислительных устройств к плохо формализуемым объектам. Именно, благодаря теории алгоритмов происходит внедрение математических методов в экономику, лингвистику, психологию, педагогику и другие гуманитарные науки.

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

В качестве другого примера можно привести классический алгоритм Евклида (нахождения наибольшего общего делителя (НОД) двух натуральных чисел, отличных от нуля). Приведем описание этого алгоритма.

Задана пара натуральных чисел, т.е. , причем .

1) Делим a₁ на a₂.. Процесс деления записываем в общем виде:

a₁ = a₂ b₁ + r₁.

Если r₁=0, то НОД = .

Если r₁≠ 0, то переходим ко второму этапу.

2) Делим a₂ на r₁ . Процесс деления записываем в общем виде:

a₂= r₁⋅b₂ + r₂ .

Если r₂=0 , то НОД( r₁ )=r₁

Если r₂≠ 0, то переходим к следующему этапу и т.д.

В итоге имеем последовательности равенств:

a₁ = a₂ b₁ + r₁.

a₂= r₁⋅ b₂ + r₂

………………..

r_n-2 = r_n-1 ⋅ b_n + r_n

r_n-1 = r_n ⋅ b_n+1 + r_n+1

Таким образом, получили убывающую последовательность натуральных чисел

a₂ > r₁> r₂ >...> r_n > r_n+1 ≥ 0,

которая должна быть конечной, так как a₂∈ N . Поэтому для некоторого n, r_n+1=0, и в силу равенств НОД( a₁,a₂ )=НОД(a₂,r₁)=НОД(r₁,r₂)=...=НОД(r_n−1,r_n)=

=НОД( r_n,0) = r_n .

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

Возникает вопрос: нельзя ли построить такое предписание, чтобы действие деления содержалось в нем лишь один раз, но было бы точно определено, до каких пор надо повторить это действие и над какими числами оно выполняется в каждом повторении?

Данный вопрос решается положительно, но при этом придется исходным переменным a₁ и a₂ на каждом шагу присвоить новые значения. Тогда получаем следующее предписание:

1. Разделить a₁ на a₂. Перейти к пункту 2.

2. Если r = 0, то перейти к пункту 4, иначе – к пункту 3.

3. Присвоить a₁ значение a₂, a2– значение r. Перейти к пункту 1.

4. НОД( ) = a₂ . Перейти к пункту 5.

5. Процесс окончен.

Таким образом, мы получили более компактные описание алгоритма Евклида.

Основные свойства алгоритма.

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

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

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

4. Эффективность (результативность)– каждый шаг работы алгоритма должен заканчиваться результатом.

5. Массовость алгоритма – начальная система величин может выбираться из некоторого потенциально бесконечного счетного множества Х.

6. Конструктивность – объекты из Х, над которыми работает алгоритм, должны быть конструктивными (конструктивный объект –это такой объект, который может быть набран весь целиком и представлен нам для рассмотрения).

Примерами конструктивных объектов являются булевы функции, формулы алгебры логики, натуральные и рациональные числа, матрицы с натуральными или рациональными элементами, многочлены от n неизвестных с рациональными коэффициентами и т.п.

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

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

В силу свойства конструктивности алгоритма между объектами счетного множества X и множества натуральных чисел N можно установить взаимно однозначное соответствие и в дальнейшем вместо объекта x∈X рассматривать его номер или код объекта, являющийся натуральным числом.

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

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

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