Методические указания к выполнению контрольных работ по дисциплине "Основы программирования" (стр. 8 из 40)

Фраза, которая в приведенном выше доказательстве выделена курсивом, является иллюстрацией того общепринятого условного языка, который так часто используется в доказательствах методом индукции. Например, выполняя п. (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 и на само себя. Используя данное определение и метод математической индукции, докажите, что любое целое число, большее единицы, можно записать как произведение одного или нескольких простых чисел. (Для удобства будем считать, что простое число – это «произведение» одного простого числа, т.е. его самого.)