Пример

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

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

Сведение любого алгоритма к численному алгоритму.

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

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

Включим все условия задачи, доступные для перера­ботки данным алгоритмом А, в занумерованную неот­рицательными целыми числами последовательность А₀, А₁, А₂, …, А_n, …

Совершенно аналогично записи возможных решений также включим в занумерованную последовательность B₀, B₁, B₂, …, B_n, …

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

m=φ(n),

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

Очевидно также, что если есть алгоритм, решающий исходную задачу, то есть и алгоритм вычисления зна­чений соответствующей функции. Действительно, чтобы найти значение φ(n) при п = п*, можно по п* восста­новить запись условий задачи, затем с помощью имею­щегося алгоритма найти запись решения и по записи решения определить номер m*. Следовательно,

φ(n*)=m*

Обратно, если есть алгоритм вычисления функции φ(n), то, стало быть, имеется и алгоритм решения ис­ходной задачи. Действительно, по записи условий за­дачи можно найти соответствующий ей номер n*, затем вычислить m*=φ(n*), и по m* oопределить запись ре­шения.

Функция f называется вычислимой, если существует алгоритм, перерабатывающий всякий объект х, для которого определена функция f, в объект f (x) и не применимый ни к какому x, для которого f не определена. Вычислимая функция, одно из основных понятий теории алгоритмов

Примеры:1) х — натуральное число, f (x) = х ²; x — пара рациональных чисел x ₁ и x ₂, f (x) = x ₁: x ₂ (эта функция определена лишь для тех x, у которых x _2≠0);

2) X — пара матриц X ₁ и X ₂ с целочисленными элементами, f (X) = X ₁ X ₂ (эта функция определена лишь для тех X, у которых число стоблцов в X ₁ совпадает с числом строк в X ₂).

Дата добавления: 2014-01-20