скачать doc
РАЗРАБОТКА, ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ
И АНАЛИЗ АЛГОРИТМА
Фактическая нумерация со стр.4
РАЗРАБОТКА, ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ
И АНАЛИЗ АЛГОРИТМА
Начнём с примера, демонстрирующего основные этапы работы над алгоритмом. Рассмотрим задачу нахождения наибольшего общего делителя двух натуральных чисел. Далее для обозначения наибольшего общего делителя будем использовать русскую аббревиатуру НОД или английскую gcd или GCD от словосочетания Greatest Common Divisor.
Основные определения
Даны два натуральных числа a и b (a, b > 0). Требуется найти натуральное число c = НОД(a, b). Понятие НОД известно из школьного курса арифметики (алгебры). Можно было бы вычислять НОД на основе разложения чисел a и b на простые множители
учитывая, что
(1.2)Однако получение разложения произвольного числа на простые множители само по себе является непростой задачей.
Для того чтобы найти другие способы вычисления НОД, дадим формальное (точное) определение НОД(a, b). Запись p q для натуральных p и q далее означает, что q является делителем (делит нацело) p.
Определение НОД. Натуральное число c = НОД(a, b), если
1) c делитель a, т. е. a c;
2) c делитель b, т. е. b c;
3) c наибольшее из натуральных чисел, удовлетворяющих 1) и 2).
Уточняя используемые в 1) 3) понятия, дополним это определение:
4) для натуральных p и q запись p q означает, что существует такое натуральное s, что p = s q;
5) наибольшим из множества S натуральных чисел является такое p S, что не существует другого числа q S, такого, что q > p.
Основываясь непосредственно на данном определении, можно вычислять НОД следующим образом: последовательно перебирая числа c = 1, 2, 3, …, min(a, b), находим максимальное среди тех из них, для которых справедливо a c и b c. Эту простую схему можно улучшить, если числа перебирать в порядке убывания от min(a, b) до 1, тогда первое встретившееся c, такое, что a c и b c, и будет НОД(a, b). Оказывается, существует более эффективный (по количеству операций) алгоритм.
Во многих случаях полезно строить вычисления не непосредственно на определении вычисляемой величины, а на её свойствах. Рассмотрим некоторые из них. Очевидно, что gcd(a, b) = gcd(b, a) и gcd(a, a) = a. Расширим область значений входных чисел a и b, допуская, что одно из них может быть равно 0. Тогда gcd(a, 0) = a.
Для того чтобы сформулировать важное для дальнейшего свойство НОД, напомним определения операций деления нацело div и нахождения остатка от деления mod. Пусть a, b и a > b > 0, тогда существуют, и притом единственные q и r 0 , такие, что имеет место представление
a = q b + r, 0 r < b.
Обычно используют обозначения q = a div b, r = a mod b, и тогда
a = (a div b) b + (a mod b).
Свойство НОД. Пусть a, b и a > b > 0, тогда gcd(a, b) = gcd(b, r).
В других обозначениях gcd(a, b) = gcd(b, a mod b), gcd(a, b) = gcd(b, a q b).
Доказательство. 1) Пусть d общий делитель a и b (d = ОД(a, b)), т. е. a d и b d. Тогда (a q b) d, т. е. r d и d = ОД(b, r); 2) пусть d = ОД(b, r), тогда (q b + r) d, т. е. a d и d = ОД(a, b). Отсюда следует, что множества общих делителей пар чисел (a, b) и (b, r) совпадают, а следовательно, совпадают и их наибольшие общие делители.
Можно сформулировать и доказать аналогичное свойство НОД, включающее операцию вычитания: (a > b > 0) gcd(a, b) = gcd(a b, b).
Разработка алгоритма
Рассмотрим алгоритм, в основе которого лежат два свойства НОД, а именно:
(a > b > 0) gcd(a, b) = gcd(b, a mod b);
gcd(a, 0) = a.
Общая идея алгоритма состоит в том, чтобы последовательно от пары чисел (a, b) переходить к новой паре чисел (b, a mod b). При этом max(b, a mod b) < max(a, b), т. е. каждый такой шаг «уменьшает» текущую пару. Шаги продолжаются, пока не будет получена пара (a, 0) , и тогда gcd(a, 0) = a.
Такой алгоритм известен как алгоритм Евклида и далее в 1.4 он будет записан в стандартной форме. Сейчас запишем этот алгоритм в виде вычислительной схемы, т. е. как последовательность шагов, пронумерованных от 1 до n, с описанием действий каждого шага. На i-м шаге очередную полученную пару чисел обозначим с помощью индексов как (ci, ci + 1). Вначале установим c0 = a, c1 = b (a > b > 0). Очевидно, gcd(a, b) = gcd(c0, c1). Дальнейшие действия представим в виде табл. 1.1.
Таблица 1.1
| Шаг | До шага | Действия шага | После шага |
| 1: | {c0, c1} | c0 = q1 c1 + c2 | {c1, c2} {gcd(c1, c2) = gcd(c0, c1)} |
| 2: | {c1, c2} | c1 = q2 c2 + c3 | {c2, c3} {gcd(c2, c3) = gcd(c1, c2)} |
| | | … | |
| i: | {ci 1, ci} | ci 1 = qi ci + ci + 1 | {ci, ci + 1} {gcd(ci, ci + 1) = gcd(ci 1, ci)} |
| | | … | |
| n: | {cn 1, cn} | cn 1 = qn cn + cn + 1 | {cn, cn + 1} {gcd(cn, cn + 1) = gcd(cn 1, cn)} |
Действия каждого шага представлены здесь как переход от пары чисел (ci 1, ci) к паре чисел (ci, ci + 1) согласно соотношению ci 1 = qi ci + ci + 1. Фактически вычисление qi = ci 1 div ci производить не нужно, достаточно вычислить ci + 1 = ci 1 mod ci.
Здесь предполагалось, что n-й шаг вычислений последний, т. е. cn + 1 = 0 и gcd(cn, 0) = cn. Учитывая цепочку равенств в правом столбце табл.1.1 и начальное равенство gcd(a, b) = gcd(c0, c1), получим cn = gcd(a, b), что и обосновывает правильность алгоритма.
Тот факт, что вычисления вообще закончатся, следует из неравенств (свойств остатков) ci > ci + 1 0, т. е. c0 > c1 > c2 > c3 > … >cn 1 > cn > cn + 1 = 0. Действительно, не может существовать бесконечной строго убывающей последовательности целых неотрицательных чисел.
Неудовлетворенность в предыдущих рассуждениях, обосновывающих правильность вычислений, может быть вызвана наличием знака многоточия «…» в некоторых местах записи вычислений или при рассуждениях (оборот речи «и т. д.»). Поскольку в дальнейшем возникнет необходимость строить рассуждения о свойствах алгоритмов, можно добиться строгости рассуждений, используя обычное для математики в таких случаях средство доказательство методом математической индукции.
1.3. Метод математической индукции
Пусть сформулировано утверждение P(n) для всех натуральных n или для части натуральных чисел (например, для подмножества (n0) ={x | x n0}, где n0). Для того чтобы доказать справедливость P(n) для всех n или n(n0), применяют следующий способ, называемый принципом или методом математической индукции (ММИ).
Способ доказательства:
(а) Доказать, что P(n0) справедливо.
(б) Доказать, что из справедливости утверждений P(n0), P(n0 + 1),…, P(n) следует справедливость утверждения P(n + 1). Это доказательство должно годиться для любого n n0.
Доказательство (а) называют базой или основанием, а доказательство (б) – индукцией или индуктивным переходом.
Используя квантор всеобщности , можно представить описанный способ доказательства в виде правила вывода (обозначения см. в 2.1 и 4.1):
| P(n0), (n(n0): (k: n0 k n: P(k)) P(n + 1)) | . |
| (n(n0): P(n)) |
Иногда используют упрощённый вариант метода математической индукции, представляя шаг (б) в следующем виде:
(б) Доказать, что из справедливости утверждения P(n) следует справедливость утверждения P(n + 1) для любого n n0.
В форме правила вывода упрощённый вариант выглядит как
| P(n0), (n(n0): P(n) P(n + 1)) | . |
| (n(n0): P(n)) |
В отличие от упрощённого варианта исходную формулировку называют полным методом математической индукции.
Рассмотрим примеры доказательств с помощью ММИ.
Пример 1. Докажем, что
S (n) = 1 + 2 + 3 + … + (n – 1) + n =
= 
.Действительно,
(а) S (1) = 1(1+1)/2 = 1,
(б) S (n + 1) =
= S (n) + (n + 1) =
+ (n + 1) = (n + 1) 
= 
.Пример 2. Докажем, что в полном графе из n вершин имеется ровно
рёбер. Полные графы для n = 1, 2, 3, 4, 5 действительно имеют 0, 1, 3, 6, 10 рёбер соответственно. Для базы индукции достаточно взять n = 1, остальные значения приведены для иллюстрации (рис. 1.1). 
Индуктивный переход: рассмотрим полный граф из n + 1 вершин; выделим одну из них и все рёбра, инцидентные этой вершине (соединённые одним концом с этой вершиной); таких рёбер имеется ровно n штук (второй конец каждого такого ребра соединён с одной из остальных вершин); прочие вершины и рёбра образуют полный граф, в котором по индуктивному предположению имеется ровно
рёбер; эти рёбра вместе с ранее выделенными дают в совокупности + n = , что и доказывает утверждение P(n + 1).Заметим, что в этих примерах использовался упрощённый вариант ММИ.
Пример 3. Числами Фибоначчи называются элементы числовой последовательности, определяемые рекуррентным (возвратным) уравнением Fn + 2 = Fn + 1 + Fn при n = 0, 1, 2, … и начальными элементами F0 = 0 и F1 = 1. Вот несколько первых чисел Фибоначчи: F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, F9 = 34, F10 = 55, F11 = 89, F12 = 144, F13 = 233, F14 = 377, F15 = 610.
Докажем, что для чисел Фибоначчи справедливо соотношение
(1.3)где
и 
есть корни квадратного уравнения 
и 
. Число 1.61803… называют «золотым сечением» [1].Действительно, (а) при n = 0 имеем
, а при n = 1 
. Далее (б)
что и доказывает (1.3).
Пример 4. Каждое n можно представить в виде произведения одного и более простых сомножителей.
Действительно, если n = 1, то оно простое и утверждение справедливо. Предположим, что наше утверждение справедливо для чисел 1, 2, 3, …, n. Покажем, что n + 1 также можно представить в виде произведения одного и более простых сомножителей. Действительно, если n + 1 простое число, то n + 1 = (n + 1)1. Если n + 1 не простое, то существует некоторое положительное число a, такое, что 1 < a < (n + 1) и оно делит n + 1 без остатка. Это означает, что n + 1 = q a, где q частное от деления и 1 < q < (n + 1). Поскольку каждое из чисел a и q меньше n + 1, то по предположению их можно представить в виде произведения одного и более простых сомножителей, а следовательно, это верно и для n + 1 = q a.
Отметим, что в этом доказательстве использован полный метод математической индукции, так как заранее неизвестно, каковы будут a и q, и требуется индуктивное предположение для всех чисел 1, 2, 3, …, n.
Приведём пример некорректного использования метода математической индукции. Докажем, что в любой куче камешков все камешки одного цвета. Действительно, при n = 1 утверждение справедливо. Предположим, что оно справедливо для n, и покажем его справедливость для n + 1. Выберем один камешек из кучи, содержащей n + 1 камешек. Оставшиеся в куче камешки по предположению имеют одинаковый цвет. Поменяем выбранный камешек с одним из оставшихся в куче. В куче по-прежнему n камешков и все они по предположению одного цвета, причём того же, что и были ранее, так как мы заменили лишь один из камешков. Отсюда следует, что выбранный вначале камешек имеет тот же цвет, что и остальные, и все n + 1 камешков имеют один цвет.
Ошибку в представленном доказательстве легко обнаружить, если попытаться выполнить алгоритм ММИ, представленный на рис. 1.2.
Алгоритм ММИ
(выдает для заданных n0 и n(n0) доказательство того,
ч
то P(n0), P(n0 + 1), …, P(n) верны)
Рис. 1.2. Алгоритмическая процедура метода математической индукции
Действительно, метод математической индукции можно считать алгоритмической процедурой доказательства утверждения P(n) для любого заданного n(n0) в предположении, что доказательства (а) и (б) уже известны.
1.4. Запись алгоритма и доказательство корректности
После обсуждения метода математической индукции вернёмся к проблеме обоснования правильности алгоритма нахождения НОД из 1.2. Во всех тех случаях, где ранее использовалась запись «…» («и т. д.»), доказательство можно провести методом математической индукции. При этом индуктивный переход будет опираться на уже доказанное свойство НОД: (a > b > 0) gcd(a, b) = gcd(b, a mod b).
Запишем алгоритм Евклида на языке Паскаль. Для описания действий понадобятся, кроме исходных a и b, ещё две переменные u и v, которые будут использованы вместо ci, ci + 1. Поскольку для вычисления каждой новой пары достаточно знать лишь предыдущую пару, то можно обойтись двумя переменными u и v. Итак, в алгоритме будут участвовать переменные a, b, u, v типа Integer и, кроме того, ещё одна вспомогательная переменная r для представления остатка от деления.
u := a; v := b;
while v 0 do