Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

за конечное число шагов найти выходное слово, соответствующее любому наперед заданному входному слову из области определе­

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

Два алфавитных оператора считаются равными, если они имеют

щие им алфавитные операторы и совпадает система правил, зада­ ющих действие этих алгоритмов на выходные слова.

Два алгоритма считаются эквивалентными, если у них совпа­ дают алфавитные операторы, но не совпадают способы их зада­ ния (система правил). Обычно в теории алгоритмов рассматривают­ ся лишь такие алгоритмы, которым соответствуют однозначные ал­ фавитные операторы.

Всякий алгоритм такого рода любому входному слову относит только одно выходное слово. Такие алгоритмы и соответствующие

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

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

Теперь эквивалентность алгоритмов может быть определена следующим образом: два алгоритма эквивалентны, если совпадают их области применимости и результаты переработки любого слова из этой области.

В общем случае различают еще случайные и самоизменяющие­ ся алгоритмы. Алгоритм называется случайным, если в системе

15

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

Алгоритм называется самоизменяющимся, если он не только перерабатывает входные слова, но и сам изменяется в процессе такой переработки. Результат действия самоизменяющегося алго­ ритма на то или иное входное слово зависит не только от этого слова, но и от истории предыдущей работы алгоритма.

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

Основные формализмы прикладной теории алгоритмов можно разделить на два направления, условно называемые «алгебраиче­ ским» и «геометрическим».

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

ввиде разметки вершин или ребер графа.

Кпервому направлению относятся рекурсивные функции, ма­ шины Тьюринга, операторные системы Ван-Хао, А. А. Ляпунова, логические схемы алгоритмов Ю. И. Янова и др.

Ко второму направлению относятся представления нормальных алгоритмов А. А. Маркова в виде граф-схем, предложенных Л. А. Калужниным, блок-схемный метод алгоритмизации и др.

Упражнения:

1. Составить словесные алгоритмы вычитания из некоторого числа А последовательности п чисел Ьл, Ь%,..., Ьп.

а) алгоритм вычисления по фбрмуле

б) алгоритм вычисления по формуле

2. Составить алгоритм поэлементного вычисления из последова­ тельности п чисел аи а г , . . . , ап, последовательности п чисел Ьи Ьг,.. Ьп, т. е. алгоритм вычисления по формуле

1б

3. Составить алгоритм вычисления по формуле

1=1

4. Составить алгоритм вычисления по формуле

С, = а , Х М 1 < * < т ) .

5.Составить алгоритм вычисления по формуле

С= П а 4 ( 1 < К 4

6.Составить алгоритм вычисления по формуле

10.Составить алгоритм определения количества одинаковых элементов в матрице В размерностью п X т.

11.Составить алгоритм умножения матрицы на вектор,

12.Составить алгоритм умножения матрицы на матрицу.

13.Составить алгоритм транспортирования матрицы.

14.Составить алгоритм, реализующий операцию объединения

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

16.Составить алгоритм, реализующий операцию разности двух произвольных множеств.

1.2. Рекурсивные функции

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

Численные функции, значение которых можно установить по­

процедура для выполнения определенных вычислений, если эти вычисления выполняются по механическим правилам, т. е. по опре­ деленному алгоритму.

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

класс всех числовых функций, определимых в некоторой формаль­

Понятие вычислимой функции точно не определяется, поэтому те­

недоказуема, как и гипотеза Черча. Однако математические иссле­ дования последних 30 лет выявили полную целесообразность считать понятие частично рекурсивной функции научным эквива­ лентом интуитивного понятия вычислимой частичной функции.

В дальнейшем под тезисом Черча будем понимать гипотезу Черча в том расширенном виде, который был придан ей Клини.

Тезис Черча оказался достаточным, чтобы придать необходи-

18

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

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

После нумерации входных и выходных слов в произвольном ал­ фавитном операторе этот оператор превращается в функцию у = = f(x), в которой аргумент х и функция у принимают неотрицатель­ ные целочисленные значения. Функция f(x) может быть определе­ на не для всех значений х, а лишь для тех, которые составляют об­

ми, среди них выделим наиболее простые и будем их называть эле­

2) тождественные функции, повторяющие значения своих аргу­

3) функции непосредственного следования:

S1(x) = x + 1

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

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

Операция суперпозиции функций заключается в подстановке одних арифметических функций вместо аргументов других арифме­ тических функций.

Пусть заданы п функций fi, . . . , fn от m переменных каждая и