Обобщенный алгоритм Евклида

 

Пример 1-4. Математическую индукцию можно использовать также для доказательства фактов, касающихся алгоритмов. Давайте рассмотрим следующее обобщение алгоритма Евклида.

Алгоритм Е (обобщенный алгоритм Евклида). Даны два целых положительных числа m и b. Требуется найти их наибольший общий делитель d и два целых числа а и b,таких, что am + bn = d .

Действие E l. Инициализация.

Присвоить а' b 1, аb' 0, с т, d n.

Действие Е 2. Деление.

Пусть q и r – это частное и остаток от деления с на d соответственно. Тогда

с = qd + r,где 0 £ r < d.

Действие Е З. Остаток – это нуль?

Если r = 0, то выполнение алгоритма прекращается; в этом случае имеем

am + bn = d,

как и требовалось.

Действие Е 4. Повторение цикла.

Присвоить

с d, d r, t а', а' а, а (t – qa), t b ', b ' b, b (t – qb)

 

и вернуться к шагу Е2.

Если изъять из алгоритма переменные а, b, а' и b ' и использовать m и n в качестве вспомогательных переменных с и d, то получим старый алгоритм Е (см. параграф 1.1). В новой версии алгоритма выполняется немного больше вычислений, так как необходимо определить коэффициенты a и b. Предположим, что m = 1769 и n = 551. Тогда последовательно (после шага Е 2) имеем:

 

а'	a	b'	b	c	d	q	r
1	0	0	1	1769	551	3	116
0	1	1	– 3	551	116	4	87
1	– 4	– 3	13	116	87	1	29
– 4	5	13	– 16	87	29	3	0

 

Проверяя полученные результаты, убеждаемся в том, что все правильно, так как 5 ´ 1769 - 16 ´ 551 = 8845 - 8816 = 29, т.е. мы получили наибольший общий делитель чисел 1769 и 551.

Теперь нужно доказать, что рассматриваемый алгоритм работает правильно при любых т и п. Для этого попробуем применить метод математической индукции к следующему утверждению Р(п): «Алгоритм Е дает правильное решение для заданного n и всех целых m». Но провести подобное доказательство не так-то просто, поэтому нужно доказать сначала несколько дополнительных фактов. После некоторого изучения проблемы выясняется, что нужно доказать какой-то факт, связанный с коэффициентами а, b , а'и b'. Этот факт заключается в том, что равенства

              а'т + b 'п = с,   am + bn = d                              (1.9)

 

верны в каждом случае выполнения шага Е2. Данные равенства можно доказать непосредственно, заметив, что они безусловно справедливы после первого выполнения шага Е2, и что шаг Е4 не меняет это положение вещей (см. упражнение 1.17).

Теперь мы готовы индукцией по п доказать, что алгоритм Е работает правильно. Если т кратно п,то очевидно, что алгоритм работает правильно, поскольку его работа заканчивается на шаге ЕЗ в первом же цикле и мы получаем верный результат. Это происходит всегда, когда n = 1. Поэтому остается провести доказательство для случая, когда п > 1 и т не является кратным п. В такой ситуации в первом цикле осуществляется переход к шагу Е4 и выполняются операции присвоения с п, d r. И так как r < п, по индукции можно предположить, что окончательное значение d – наибольший общий делитель чисел п и r. Из доказательства, приведенного в параграфе 1.2. следует, что пары {т,п}и {п,r}имеют одинаковые наибольшие общие делители и, в частности, один и тот же наибольший общий делитель. Значит, d – это наибольший общий делитель чисел m и n и согласно (1.9) am + bn = d .

 

Фраза, которая в приведенном выше доказательстве выделена курсивом, является иллюстрацией того общепринятого условного языка, который так часто используется в доказательствах методом индукции. Например, выполняя п. (b), вместо того чтобы сказать «Теперь предположим, что утверждения Р(1), Р(2), ..., Р(п)справедливы, и на этом основании докажем справедливость утверждения Р(п + 1)», мы будем говорить просто «Теперь докажем утверждение Р(п); по индукции мы можем предположить, что P(k)верно для любого 1 £ k < n» .

Если хорошо вдуматься и посмотреть на все вышесказанное с несколько иной точки зрения, то перед нами предстанет общий метод доказательства корректности любого алгоритма. Идея состоит в том, чтобы взять блок-схему некоторого алгоритма и к каждой стрелке добавить примечание о текущем состоянии дел в тот момент, который соответствует стрелке. На рис. 1.4 эти примечания (мы их будем называть также утверждениями) обозначены через Al, A2,..., А6. В утверждении А1даются первоначальные предположения о входных данных алгоритма, а в А4формулируется положение о том, что мы хотим доказать по поводу выходных значений а, b и d .

Общий метод заключается в том, чтобы для каждого блока на блок-схеме доказать следующее:

 

Согласно описанному методу для нашего примера мы должны доказать, что если до выполнения шага Е2 верно А2 либо А6,то после выполнения этого шага верно A3. (В данном случае утверждение А2является более сильным, чем А6,т.е. из А2 следует А6. Поэтому нам достаточно доказать, что выполнение А6дошага Е2 влечет за собой выполнение A3после этого шага. Заметим, что условие d > 0 необходимо в А6для того, чтобы операция Е2 имела смысл.) Нужно показать также, что из A3(при условии, что ) следует А4,из A3(при условии, что ) следует А5и т.д. Все это доказывается очень просто.

Если доказать утверждение (1.10) для каждого блока, то все примечания к стрелкам будут верны в любом случае выполнения алгоритма. Теперь мы можем применить индукцию по числу шагов, т. е. по числу стрелок в блок-схеме. При прохождении первой стрелки (той, которая выходит из блока «Начало») утверждение А1 верно, поскольку мы всегда исходим из предположения, что входные значения удовлетворяют заданным условиям. Таким образом, утверждение, которое соответствует первой стрелке, верно. Если утверждение, которое соответствует n-й стрелке, верно, то согласно (1.10) утверждение, которое соответствует (n + 1)-й стрелке, тоже верно.

Исходя из этого общего метода доказательство правильности заданного алгоритма, очевидно, сводится к нахождению правильных утверждений, соответствующих стрелкам блок-схемы. Как только данное начальное препятствие будет преодолено, останется лишь рутинная работа, связанная с доказательством того, что каждое утверждение на входе в блок влечет за собой утверждение на выходе из блока. В действительности после того как вы придумаете самые трудные из этих утверждений, найти все остальные уже не составит труда. Скажем, если даны утверждения А1, А4и А6,уже понятно, какими должны быть утверждения А2, АЗ и А5. В нашем примере самых больших творческих усилий потребует доказательство утверждения А6; все остальное, в принципе, должно получиться автоматически.

Этот подход к доказательству корректности алгоритма имеет и другой, еще более важный аспект: он отражает способ нашего понимания алгоритма. Нужно проверять работу алгоритма на примере одного-двух наборов входных данных. И это не случайно, так как пробная «прогонка» алгоритма поможет вам мысленно сформулировать утверждения, соответствующие стрелкам на блок-схеме. Уверенность в корректности алгоритма приходит только тогда, когда мысленно сформулированы все утверждения, приведенные на рис. 1.4. Отсюда следуют важные психологические выводы, касающиеся передачи алгоритма от одного лица к другому. Речь идет о том, что, объясняя алгоритм кому-либо другому, всегда следует явно формулировать основные утверждения, которые трудно получить автоматически. Например, в случае алгоритма Е нужно обязательно упомянуть утверждение А6.

Но бдительный читатель, конечно, заметил явный недостаток в нашем последнем доказательстве алгоритма Е. Из доказательства нигде не следует, что алгоритм обладает свойством конечности, т.е. рано или поздно его выполнение завершится. Мы доказали только, что если алгоритм конечен, то он дает правильный результат!

(Например, заметим, что алгоритм Е по-прежнему имеет смысл, если его переменные m, n, с, d и r принимают значения типа

,

 

где параметры и и v – целые числа^*.

    Переменные q, а, b, а', b'должны по-прежнему принимать целые значения. Если, например, на вход подать значения  и , то на выходе будет получен «наибольший общий делитель»  и коэффициенты a = +2, b = –1. Даже при таком расширении исходных предположений доказательства утверждений от А1до А6остаются в силе. Следовательно, на любом этапе выполнения этой процедуры все утверждения верны. Но если начать со значений m = 1 и , то вычисления никогда не закончатся (см. упражнение 1.15). Следовательно, из доказательства утверждений А1¸А6еще не следует, что алгоритм конечен.)

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

Итак, мы уже дважды доказали правильность алгоритма Е. Чтобы быть последовательными до конца, нам следовало бы попытаться доказать, что первый алгоритм в этом разделе, а именно – алгоритм I, также корректен. Ведь, в сущности, мы использовали алгоритм I, чтобы показать корректность любого доказательства по индукции. Но если мы попытаемся доказать, что алгоритм I работает правильно, то попадем в затруднительное положение: мы не сможем сделать это, не воспользовавшись снова индукцией! Итак, получается замкнутый круг.

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

Упражнение 1.8. Объясните, как можно модифицировать идею доказательства методом математической индукции в случае, если некоторое утверждение Р(п)нужно доказать для всех неотрицательных целых чисел, т.е. для n = 0, 1, 2, ... , а не для n = 1, 2, 3, ... .

Упражнение 1.9. Найдите ошибку в следующем доказательстве.

«Теорема. Пусть a – любое положительное число. Для всех целых положительных чисел п имеем .

Доказательство. Если п = 1, то . По индукции, предполагая, что теорема верна для 1, 2, ..., п,имеем

 ;

следовательно, теорема верна также для n + 1.»

Упражнение 1.9. Следующее доказательство по индукции выглядит корректным, но по непонятной причине для п = 6 левая часть уравнения дает , а правая дает . В чем же ошибка? «Теорема.

.

Доказательство. Используем индукцию по п. Для п = 1 доказательство очевидно: 3/2 – 1/п = 1/(1 ´ 2). Предполагая, что теорема верна для п, имеем:

.

Упражнение 1.10. Докажите, что числа Фибоначчи удовлетворяют не только соотношению (1.6), но и неравенству .

Упражнение 1.11. Простое число – это целое число, большее единицы, которое делится только на 1 и на само себя. Используя данное определение и метод математической индукции, докажите, что любое целое число, большее единицы, можно записать как произведение одного или нескольких простых чисел. (Для удобства будем считать, что простое число – это «произведение» одного простого числа, т.е. его самого.)

Упражнение 1.12. Докажите по индукции, что если 0 < a < 1, то .

Упражнение 1.13. Докажите по индукции, что если п > 10, то .

Упражнение 1.14. Найдите и докажите простую формулу для следующей суммы:

.

Упражнение 1.15. Покажите, как можно обобщить алгоритм Е, чтобы, как было указано в тексте, для него допускались входные значения вида , где и и v – это целые числа, и вычисления по-прежнему выполнялись элементарным образом (т.е. не выражая иррациональное число бесконечной десятичной дробью). Докажите, что при т = 1 и  выполнение алгоритма никогда не закончится.

Упражнение 1.16. Обобщите алгоритм Е, введя новую переменную Т и добавив в начале каждого шага операцию Т Т+1. (Таким образом, переменная Т – это счетчик выполненных шагов.)

Предположим, что первоначальное значение Т равно нулю, поэтому утверждение А1на рис. 1.4 примет вид m > 0, n > 0, Т = 0. Аналогично к А2следует добавить дополнительное условие Т = 1. Покажите, как добавить к утверждениям дополнительные условия таким образом, чтобы из любого утверждения А1, А2,..., А6следовало, что Т < 3n, и чтобы можно было провести доказательство по индукции. (Следовательно, вычисления должны закончиться максимум через 3n шагов.)

Упражнение 1.17. Докажите, что если соотношения (1.9) справедливы непосредственно перед выполнением шага Е4, то они верны и после его выполнения.