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

В качестве примера давайте исследуем с этЬй точки зрения алгоритм Евклида. Предположим, нам нужно решить следующую задачу: "Пусть задано значение п, а m может быть любым целым положительным числом. Тогда чему равно среднее число Г„ выполнений шага Е1 алгоритма Е?". Прежде всего необходимо убедиться в том, что задача имеет смысл, поскольку нам предстоит найти среднее при бесконечно большом количестве значений т. Но совершенно очевидно, что после первого выполнения шага Е1 значение будет иметь только остаток от деления m на п. Поэтому все, что мы должны сделать для нахождения значения Г„, - это испытать алгоритм для m = 1, m = 2, ..., m = п, подсчитать суммарное число выполнений шага Е1 и разделить его на п.

А теперь рассмотрим еще один важный вопрос, касающийся поведения Т„ как функции от п: можно ли ее аппроксимировать, например, функцией п или На самом деле это чрезвычайно сложная и интересная математическая проблема, которая еще не решена окончательно; более подробно она будет рассмотрена в разделе 4.5.3. Можно доказать, что при больших значениях п Тп ведет себя, как функция (12(1п2)/7г) Inn, т. е. она пропорциональна натуральному логарифму п. Заметим, что коэффициент пропорциональности нельзя просто взять и угадать; чтобы определить его, нужно затратить определенные усилия. Более подробно об алгоритме Евклида, а также о других способах вычисления наибольшего общего делителя будет говориться в разделе 4.5.2.

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

До сих пор наше обсуждение алгоритмов носило достаточно общий характер, и, вероятно, "математически настроенный" читатель утвердился в мысли, что все предыдущие комментарии представляют собой очень шаткий фундамент для построения какой-либо теории алгоритмов. Поэтому давайте подведем итог данного раздела, кратко описав метод, с помощью которого понятие алгоритма можно строго обосновать в терминах математической теории множеств. Формально определим метод вычислений как четверку {Q,I,fl, f), где Q - это множество, содержащее подмножества / и П, а / - функция, переводящая множество Q в себя. Кроме того, / оставляет неподвижными точки множества Cl, т. е. f{q) равно q для всех элементов q из множества Cl. Эти четыре элемента, Q, I, fl, /, представляют соответственно состояния вычисления, ввод, вывод и правило вычислений. Каждое входное значение х из множества / определяет вычисляемую последовательность xo,xi,x2, .. следующим образом:

хо - X и Xk+i - fixk) для А; > 0. (1)

Говорят, что вычисляемая последовательность заканчивается через к шагов, если к - это наименьшее целое число, для которого, xjt принадлежит Cl, и что она дает

выходное значение Xk для заданного х. (Заметим, что если Xk принадлежит П, то и Хк+1 принадлежит Cl, так как в этом случае Xk+i = х/..) Некоторые вычисляемые последовательности могут никогда не заканчиваться, но алгоритм - это метод вычислений, который заканчивается через конечное число шагов для всех х из /.

Например, алгоритм Е в этих терминах можно формализовать следующим образом. Пусть элементами множества Q будут все величины (п), все упорядоченные пары (m,n) и все упорядоченные четверки (m,n,r, 1), {т,п,г,2) и (m,n,p, 3), где т, п и р - это целые положительные числа, а г - неотрицательное целое число. Пусть / - это подмножество всех пар {т,п), а О - подмножество всех величин (п). Определим функцию / следующим образом:

/((m,n)) =(m,n, 0,1); /((n)) = (n);

f[{m,n,r, 1)) = (m, n, остаток от деления m на n, 2);

/((m,n,r,2)) = (n), если г = 0, (m,n,r,3) в противном случае;

f{{ni,n,p,3)) = in,p,p,l).

Соответствие между данной записью и алгоритмом Е очевидно.

В этой формулировке понятия "алгоритм" не содержится ограничение, касающееся эффективности, о котором упоминалось ранее. Например, Q может быть множеством бесконечных последовательностей, которые нельзя вычислить с помощью карандаша и бумаги, а / может включать операции, которые простой смертный сможет выполнить не всегда. Если мы хотим ограничить понятие "алгоритм" таким образом, чтобы в нем могли содержаться только элементарные операции, то введем ограничения на элементы Q, I, U н /, например, следующим образом. Пусть А - это ограниченное множество букв, а А* -множество всех строк, определенных на множестве А (т. е. множество всех упорядоченных последовательностей xiX2 х„, где п > О н Xj принадлежит А для i < j < п). Идея заключается в следующем: закодировать состояния вычисления таким образом, чтобы они были представлены строками из множества А*. Теперь пусть N - целое неотрицательное число, а Q - множество всех пар {(T,j), где а принадлежит А*, а j - целое число, О < j < N. Пусть / - подмножество пар из Q, для которых j = О, а П - подмножество пар из Q, для которых j - N. Если Q и а - строки из А*, то мы будем говорить, что в входит в а, если а имеет вид адш, где а и w - некоторые строки. И в завершение определим функцию / с помощью строк д, и целых чисел Oj, bj, О < j < N следующим образом:

f{a,j) = {a,aj), если Oj не входит в а;

f{(T,j) = (афи, bj), если а является самой короткой строкой, для которой а = авш;

f{a,N) = {a,N). (S)

Метод вычислений, удовлетворяющий этому определению, безусловно, является эффективным. Кроме того, опыт показывает, что в таком виде можно представить любую задачу, которая решается с помощью карандаша и бумаги. Существует также много других по сути эквивалентных способов формяировки понятия эффективного метода вычислений (например, с помощью машины Тьюринга). Приведенная выше формулировка практически совпадает с той, которую дал А. А. Марков

(Markov) в своей книге Теория алгорифмов [Труды АН СССР, Ин-т математики.-1954.-42.-376 с], а впоследствии исправил и расширил Н. М. Нагорный (Nagorny) (М.: Наука, 1984).

УПРАЖНЕНИЯ

1. [10] В тексте показано, как взаимно заменить значения переменных типе помощью символа замены, а именно - полагая t *- т, т *- п, п *- t. Покажите, как в результате ряда замен можно преобразовать четверку переменных {a,b,c,d) в {b,c,d,a). Другими словами, новое значение переменной а должно стать равным первоначальному значению Ь и т. д. Постарайтесь выполнить преобразование с помощью минимального числа замен.

2. [15] Докажите, что в начале выполнения шага Е1 m всегда больше п, за исключением, возможно, только первого случая выполнения этого шага.

3. [20] Измените алгоритм Е (из соображений эффективности) таким образом, чтобы исключить из него все тривиальные операции замены типа "т п". Запишите этот новый алгоритм в стиле алгоритма Е и назовите его алгоритмом F.

4. [16] Чему равен наибольший общий делитель чисел 2 166 и 6 099?

► 5. [12] Покажите, что для процедуры чтения книг этой серии, приведенной в предисловии, не хватает трех из пяти условий для того, чтобы она стала настоящим алгоритмом! Укажите также некоторые различия в форме записи этой процедуры и алгоритма Е.

6. [20] Чему равно Tg (среднее число случаев выполнения шага Е1 при п = 5)?

► 7. [М21] Пусть m известно, а п - любое целое положительное число. Пусть f/m-среднее число случаев выполнения шага Е1 из алгоритма Е. Покажите, что Um четко определено. Существует ли какая-либо связь между Um ч Тт7

8. [Л/25] Придумайте эффективный формальный алгоритм вычисления наибольшего общего делителя целых положительных чисел тип, определив соответствующим образом Bj, фу, uj, bj (как в формулах (3)). Пусть входные данные представлены строкой а"Ь", т. е. за а, взятым m раз, следует Ь, взятое п раз. Постарайтесь найти самое простое решение, насколько это возможно. [Указание. Воспользуйтесь алгоритмом Е, но вместо деления на шаге Е1 присвойте г т - п, п *- min(m, п).]

► 9. [МЗО] Предположим, что Ci = {Qi,h,Ui, fi) и Cj = (Qa,/з, 2,/2)-методы вычислений. Например, Ci может обозначать алгоритм Е (см. формулу (2)) при условии, что т и п ограничены по величине, а С2 - компьютерную программу, реализующую алгоритм Е. (Тогда можно считать, что Qa-это набор всех состояний машины, т. е. всех возможных конфигураций ее памяти и регистров, /2 определяет элементарную машинную операцию, а h - начальное состояние, которое включает программу определения наибольшего общего делителя, а также значения тип.)

Сформулируйте теоретико-множественное определение понятия "Са является представлением Cl" или "С2 имитирует Ci". Интуитивно это означает, что любая вычисляемая последовательность Ci имитируется С2, за исключением того, что у Са может быть больше шагов, на которых выполняются вычисления, и можно получить больше информации из состояний. (Таким образом, мы получим точную интерпретацию утверждения "Программа X является реализацией алгоритма У.)