учебники, программирование, основы, введение в,

 

Построение цикла с помощью инварианта

Правильное использование конструкции цикла всегда представляет некоторую трудность. Применение элементарной теории помогает избежать ошибок и облегчает написание сложных программ.
Основная идея состоит в следующем. В процессе выполнения цикла изменяются значения набора переменных. Надо найти соотношение между меняющимися переменными, которое остается постоянным. Это соотношение называется инвариантом цикла. Сознательное построение цикла "пока" всегда связано с явной формулировкой и использованием инварианта цикла.
Явная формулировка инварианта помогает выписать инициализацию переменных, выполняемую до начала цикла, и тело цикла. Инициализация должна обеспечить выполнение инварианта до начала работы цикла. Тело цикла должно быть сконструировано таким образом, чтобы обеспечить сохранение инварианта. (Более точно, из того, что инвариант выполняется до начала исполнения тела цикла, должно следовать выполнение инварианта после окончания тела цикла. В процессе исполнения тела цикла инвариант может нарушаться.)
Завершение цикла, как правило, связано с ограниченной величиной, которая монотонно возрастает или монотонно убывает при каждом выполнении тела цикла. Цикл "пока" завершается, когда условие после слова "пока" в заголовке цикла становится ложным. Следовательно, это условие должно прямо или косвенно зависеть от величины, монотонно убывающей или возрастающей в процессе выполнения цикла. По достижению ее определенного значения условие должно становиться ложным. Условием завершения цикла называют отрицание условия, стоящего после слова "пока" в заголовке цикла.
Выполнение инварианта цикла и одновременно условия завершения должно обеспечивать решение требуемой задачи.
Общая схема
Обозначим через X множество всевозможных наборов значений всех переменных, меняющихся в ходе выполнения цикла. Множество X иногда называют фазовым, или конфигурационным, пространством задачи. Инвариант - это некоторое условие I(x), зависящее от точки x из множества X и принимающее значение "истина" или "ложь". (Математики называют такие условия предикатами.) В процессе инициализации точке x присваивается такое значение x0, что условие I(x0) истинно.
Обозначим условие завершения цикла через Q(x). Условия I(x) и Q(x) должны быть подобраны таким образом, чтобы одновременная истинность I(x) и Q(x) обеспечивала решение требуемой задачи: нахождение точки x с требуемыми свойствами.
Тело цикла можно трактовать как отображение точки x в новую точку T(x) из того же множества X:
T:X http://localhost:3232/img/symbols/srarr.gif X   
Условие I(x) является инвариантом для отображения T: если I(x), то I(T(x)) также истинно.
Общая схема построения цикла с помощью инварианта выглядит следующим образом:
x := x0;    // x0 выбирается так, чтобы условие
//              I(x0) было истинным
утверждение: I(x);

  цикл пока не Q(x)
| инвариант: I(x);
| x := T(x);  // точка x преобразуется в T(x)
конец цикла

  утверждение: Q(x) и I(x);
ответ := x;
Конечно, эта схема не имеет никакой ценности без умения применять ее на практике. Рассмотрим несколько важных примеров ее использования.

http://localhost:3232/img/empty.gifАлгоритм Евклида вычисления наибольшего общего делителя

Пусть даны два целых числа m и n, хотя бы одно из которых не равно нулю. Требуется найти их наибольший общий делитель. Напомним, что наибольшим общим делителем двух чисел m и n называется такой их общий делитель d, который делится на любые другие общие делители d'. Такое определение НОД подходит не только для чисел, но и для многочленов, поскольку в нем не используется сравнение по величине. Наибольший общий делитель определен с точностью до обратимого множителя; в частности, поскольку в кольце чисел обратимы только элементы ±1, НОД целых чисел определен с точностью до знака.
В качестве пространства X рассматривается множество пар целых чисел

X = {(a,b) | a, b http://localhost:3232/img/symbols/isin.gif Z, a http://localhost:3232/img/symbols/ne.gif 0   или b http://localhost:3232/img/symbols/ne.gif 0} 

Надо вычислить НОД для заданной пары чисел (m,n). В качестве инварианта используем утверждение, что НОД текущей пары чисел равен НОД исходной пары:

I(a,b): НОД(a,b) = НОД(m,n). 

Следовательно, цикл надо строить таким образом, чтобы при изменении переменных a, b наибольший общий делитель пары (a,b) оставался неизменным. В качестве начальной точки x0 используется пара (m,n).
Обозначим через r остаток от деления a на b:

a = gb+r, где |r| < |b|.   

Тогда нетрудно доказать, что НОД(b,r) = НОД(a,b). Достаточно показать, что множества общих делителей пары (b,r) и пары (a,b) совпадают. Пусть d делит b и r. Тогда из равенства a = gb+r вытекает, что d делит a. Обратно, пусть d делит a и b. Из определения остатка имеем:

r = a-gb.

Так как правая часть равенства делится на d, то r тоже делится на d.
Итак, при замене пары (a,b) на пару (b,r) НОД не меняется. Обозначим через T отображение

T:(a,b) http://localhost:3232/img/symbols/srarr.gif (b,r)   

Условие I(a,b) является инвариантным для отображения T.
Осталось только определить условие завершения цикла Q(a,b). Выполнение этого условия должно обеспечивать решение задачи, т.е. нахождение HOД чисел a, b. Для какой пары чисел их НОД можно сразу вычислить? Проще всего, когда одно из чисел равно нулю. В этом случае

НОД(a,0) = a 

Итак, в качестве условия завершения цикла используем условие, что вторая компонента пары (a, b) нулевая:

Q(a,b): b = 0 

Теперь можно выписать алгоритм нахождения наибольшего общего делителя:

цел алгоритм НОД(вх: цел m, цел n)
| дано: целые числа m, n, хотя бы одно отлично от нуля
| надо: вычислить наибольший общий делитель пары (m, n)
начало алгоритма
| цел a, b, r;
| // инициализация
| a := m; b := n;
| утверждение: НОД(a, b) == НОД(m, n);
|
| цикл пока b != 0
| | инвариант: НОД(a, b) == НОД(m, n)
| | r := a % b;     // находим остаток от деления a на b
| | a := b; b := r; // заменяем пару (a, b) на (b, r)
| конец цикла
|
| утверждение: b == 0 и НОД(a, b) == НОД(m, n);
| ответ := a;
конец алгоритма

Алгоритм Евклида - один из самых замечательных алгоритмов теории чисел и программирования. Работает он исключительно быстро, за время, линейно зависящее от длины записи входных чисел. (Действительно, легко показать, что за два выполнения тела цикла число b уменьшается не менее, чем в четыре раза. Следовательно, число выполнений тела цикла в худшем случае равно длине двоичной записи максимального из чисел a, b.) Это позволяет применять алгоритм Евклида к очень большим целым числам - например, к двухсотзначным десятичным. Алгоритм Евклида (более точно, расширенный алгоритм Евклида, который будет рассмотрен ниже) применяется для таких больших чисел в схеме кодирования с открытым ключом RSA, которая в настоящее время широко используется на практике для защиты информации.
Быстрое возведение в степень
Второй важнейший алгоритм элементарной теории чисел - это алгоритм быстрого возведения в степень. Наряду с алгоритмом Евклида, он встречается буквально на каждом шагу, когда речь идет о применении теории чисел в программировании, - например, в теории кодирования.
Пусть требуется возвести элемент a в целую неотрицательную степень n. В качестве a может фигурировать целое или вещественное число, квадратная матрица, элемент кольца вычетов по модулю m и т.п. - требуется только, чтобы элемент a принадлежал алгебраической структуре, в которой определена ассоциативная операция умножения (т.е. в общем случае, a - элемент полугруппы).
Идея алгоритма состоит в том, чтобы возвести a в произвольную степень, применяя элементарные операции возведения в квадрат и умножения.
В качестве фазового пространства X этой задачи рассмотрим множество троек
X = {(b,k,p)}.
Здесь b выступает в роли текущего основания степени, k - в роли текущего показателя степени, p - это уже вычисленная часть степени. Ключевым моментом всегда является формулировка инварианта цикла:
I(b,k,p): bk*p = an = const,
т.е. величина bk*p постоянна и равна an. Легко подобрать начальные значения так, чтобы инвариант выполнялся:
b0 = a;  k0 = n;  p0 = 1.
I(b0,k0,p0) = I(a,n,1): an*1 = an 
Условие завершения совместно с выполнением инварианта должно обеспечить легкое решение требуемой задачи, т.е. вычисление an. Действительно, если k = 0, то из инварианта следует, что
b0*p = p = an, 
т.е. искомая величина содержится в переменной p. Итак, условие завершения состоит в равенстве нулю числа k:
Q(b,k,p): k = 0
Осталось написать преобразование T точки x = (b,k,p), которое сохраняет инвариант и одновременно уменьшает k. Определим преобразование T следующим образом:
T(b,k,p) = (b*b, k/2, p),     если k четное
T(b,k,p) = (b, k-1, p*b),   если k нечетное
Легко видеть, что инвариант сохраняется и k монотонно убывает. Итак, выпишем алгоритм быстрого возведения в степень для случая вещественного основания:
вещ алг. быстрое возведение в степень(вх: вещ a, цел n)
| дано: основание a и показатель степени n >= 0
| надо: вычислить a в степени n
начало алгоритма
| вещ b, p; цел k;
|
| // инициализация
| b := a; p := 1.0; k := n;
| утверждение: b^k * p == a^n;
|
| цикл пока k > 0
| | инвариант: b^k * p == a^n;
| | если k четное
| | | то
| | |   k := k / 2;
| | |   b := b * b;
| | | иначе
| | |   k := k - 1;
| | |   p := p * b;
| | конец если
| конец цикла
|
| утверждение: k == 0 и b^k * p == a^n;
| ответ := p;
конец алгоритма

http://localhost:3232/img/empty.gifВычисление логарифма без использования разложения в ряд

Схема построения цикла с помощью инварианта позволяет легко написать алгоритм вычисления логарифма заданного числа без использования разложения в ряд.
Пусть задано вещественное число x. Требуется вычислить логарифм числа x по основанию a c точностью ε, где ε - некоторое положительное очень маленькое число. Для определенности, пусть a>1 (для a<1 можно воспользоваться тождеством log1/ax = -logax).
Из определения логарифма следует, что надо найти число y такое, что
ay = x.
Нам достаточно, чтобы это равенство выполнялось приближенно. В качестве инварианта используем условие
ayzt = x = const.
Таким образом, в цикле будут меняться три переменные
(y,z,t),
и инвариант записывается в виде
I(y,z,t): ayzt = x  
Начальные значения переменных y, z, t выбираются так, чтобы выполнялся инвариант:
y0 = 0,  z0 = x,  t0 = 1.
Определим условие завершения цикла Q(y,z,t). Необходимо, чтобы искомая величина по окончанию цикла содержалась в переменной y. Следовательно, величина zt должна быть близка к единице: тогда приблизительно выполняется равенство
ay http://localhost:3232/img/symbols/cong.gif ayzt = x
т.е. y приближенно равен искомому логарифму. Для того, чтобы величина zt была близка к единице, нужно, чтобы показатель степени t был близок к нулю, а основание z было не очень велико и не очень мало. Для этого достаточно выполнения трех неравенств
|t| < ε,  1/a < z < a  
Можно доказать строго, что при выполнении этих неравенств, а также условия ayzt = x, величина y отличается от logax не больше чем на ε.
Выполнение этих трех неравенств и являются условием завершения цикла:
Q(y,z,t):  |t| < ε и 1/a < z и z < a   
Наконец, тело цикла должно преобразовывать переменные (y,z,t) так, чтобы абсолютная величина t монотонно убывала, а переменная z рано или поздно попадала бы в интервал (1/a,a), и при этом сохранялся инвариант. Такое преобразование T легко выписывается по инварианту цикла:
T(y,z,t) = (y+t, z/a, t), если z http://localhost:3232/img/symbols/ge.gif a
T(y,z,t) = (y-t, z*a, t), если z http://localhost:3232/img/symbols/le.gif 1/a
T(y,z,t) = (y, z*z, t/2), если 1/a < z < a    
Заметим, что при применении преобразования T некоторая величина как бы перетекает из одних переменных в другие, при этом равенство ayzt = x остается неизменным.
Теперь можно выписать алгоритм вычисления логарифма:
вещ алгоритм логарифм(вх: вещ x, вещ a, вещ eps)
| дано: x > 0, a > 1, eps > 0
| надо: вычислить log_a x с точностью eps
начало алгоритма
| вещ y, z, t;
|
| // инициализация
| y := 0.0; z := x; t := 1.0;
| утверждение: a^y * z^t == x;
|
| цикл пока |t| >= eps или z <= 1.0/a или z >= a
| | инвариант: a^y * z^t == x;
| | если z >= a
| | | то
| | |   z := z/a; y := y + t;
| | иначе если z <= 1.0/a
| | | то
| | |   z := z*a; y := y - t;
| | иначе
| | |   z := z*z; t := t/2.0;
| | конец если
| конец цикла
|
| утверждение: |t| < eps  и
|              z > 1.0/a  и  z < a  и
|              a^y * z^t == x;
| ответ := y;
конец алгоритма

http://localhost:3232/img/empty.gifРасширенный алгоритм Евклида

Один из важнейших результатов элементарной теории чисел утверждает, что наибольший общий делитель двух целых чисел выражается в виде их линейной комбинации с целыми коэффициентами. Пусть m и n - два целых числа, хотя бы одно из которых не равно нулю. Тогда их наибольший общий делитель d = НОД(m,n) выражается в виде
d = um+vn,
где u и v - некоторые целые числа. Результат этот очень важен для практики, т.к. позволяет вычислить обратный элемент к n в кольце вычетов по модулю m. Действительно, пусть числа m и n взаимно просты, т.е. НОД(m,n) = 1. Тогда
1 = um+vn,
откуда следует
vn = 1-um  http://localhost:3232/img/symbols/rArr.gif     
vn http://localhost:3232/img/symbols/equiv.gif 1(mod m)
Нахождение обратного элемента в кольце вычетов Zm применяется во многих дискретных алгоритмах, например, в схеме кодирования с открытым ключом.
Для вычисления наибольшего общего делителя d и одновременно чисел u и v используется так называемый расширенный алгоритм Евклида. В обычном алгоритме Евклида пара чисел (a,b) в цикле заменяется на пару (b,r), где r - остаток от деления a на b, при этом наибольший общий делитель у обеих пар одинаковый. Начальные значения переменных a и b равны m и n соответственно. Алгоритм заканчивается, когда b становится равным нулю, при этом a будет содержать наибольший общий делитель.
Идея расширенного алгоритма Евклида заключается в том, что на любом шаге алгоритма хранятся коэффициенты, выражающие текущие числа a и b через исходные числа m и n. При замене пары (a,b) на пару (b,r) эти коэффициенты перевычисляются.
Итак, в алгоритме участвуют переменные a, b, u1, v1, u2, v2, для которых выполняется следующий инвариант цикла:
I(a, b, u1, v1, u2, v2):  НОД(a,b) = НОД(m,n) 
a = u1m+v1n
b = u2m+v2n
Начальные значения этих переменных обеспечивают выполнение инварианта:
a = m, b = n,
u1 = 1, v1 = 0,
u2 = 0, v2 = 1.
Условием завершения цикла, как и в обычном алгоритме Евклида, является равенство нулю переменной b:
Q(a, b, u1, v1, u2, v2):  b = 0.
Осталось написать тело цикла, сохраняющее инвариант и уменьшающее абсолютную величину переменной b. Это нетрудно сделать, исходя из инварианта цикла. В обычном алгоритме Евклида пара (a,b) заменяется на (b,r), где r - остаток от деления a на b.
a = gb+r,  |r| < |b|.   
Здесь g равняется целой части частного от деления a на b. Заметим, что в программировании, в отличие от школьной математики, операция взятия целой части перестановочна с операцией изменения знака:
целая часть(-x) = - целая часть(x)
Например, целая часть(-3.7) = -3. Это позволяет работать с отрицательными числами так же, как и с положительными, т.е. вообще не следить за знаком! Отметим также, что в большинстве языков программирования считается, что результат любой операции с целыми числами является целым числом, например, 8/3 = 2.
Переменная g вычисляется как целая часть частного от деления a на b:
g = целая часть (a/b)
Выразим остаток r в виде линейной комбинации a и b:
r = a-gb
Используя инвариант цикла, можно выразить r через исходные числа m и n:
r = a-gb = (u1m+v1n)-g(u2m+v2) =
= (u1-gu2)m+(v1-gv2)n.
Через u'1, v'1, u'2, v'2 обозначаются новые значения переменных u1, v1, u2, v2. При замене (a,b) http://localhost:3232/img/symbols/srarr.gif(b,r) они вычисляются следующим образом:
u'1 = u2,  v'1 = v2
u'2 = u1-gu2, v'2 = v1-gv2  
По завершению цикла ответ будет находиться в переменных a (НОД исходных чисел m и n), u1, v1 (коэффициенты выражения НОД через m и n).
Выпишем алгоритм:
алгоритм Расширенный алгоритм Евклида(
вх: цел m, цел n,
вых: цел d, цел u, цел v
)
| дано: целые числа m, n, хотя бы одно отлично от нуля;
| надо: вычислить d = НОД(m, n) и найти u, v такие, что
|                 d = u * m + v * n;
начало алгоритма
| цел a, b, q, r, u1, v1, u2, v2;
| цел t;        // вспомогательная переменная
| // инициализация
| a := m; b := n;
| u1 := 1; v1 := 0;
| u2 := 0; v2 := 1;
| утверждение: НОД(a, b) == НОД(m, n)  и
|              a == u1 * m + v1 * n    и
|              b == u2 * m + v2 * n;
|
| цикл пока b != 0
| | инвариант: НОД(a, b) == НОД(m, n)  и
| |            a == u1 * m + v1 * n    и
| |            b == u2 * m + v2 * n;
| | q := a / b; // целая часть частного от деления a на b
| | r := a % b; // остаток от деления a на b
| | a := b; b := r;    // заменяем пару (a, b) на (b, r)
| |
| | // Вычисляем новые значения переменных u1, u2
| | t := u2;           // запоминаем старое значение u2
| | u2 := u1 - q * u2; // вычисляем новое значение u2
| | u1 := t;           // новое значение u1 := старое
| |                    //                 значение u2
| | // Аналогично находим новые значения переменных v1, v2
| | t := v2;
| | v2 := v1 - q * v2;
| | v1 := t;
| конец цикла
|
| утверждение: b == 0                 и
|              НОД(a, b) == НОД(m, n) и
|              a == u1 * m + v1 * n;
| // Выдаем ответ
| d := a;
| u := u1; v := v1;
конец алгоритма

http://localhost:3232/img/empty.gifНахождение корня функции методом деления отрезка пополам

Рассмотрим еще один пример использования схемы построения цикла с помощью инварианта, часто встречающийся в реальных программах. Пусть y = f(x) - непрерывная функция от вещественного аргумента, принимающая вещественные значения. Пусть известно, что на заданном отрезке [a,b] она принимает значения разных знаков. Из непрерывности функции f следует, что она имеет по крайней мере один корень на этом отрезке. Требуется вычислить корень функции f с заданной точностью ε.
Идея алгоритма состоит в том, чтобы поделить отрезок пополам и выбрать ту половину отрезка, на которой функция принимает значения разных знаков. Эта операция повторяется до тех пор, пока длина отрезка не станет меньше, чем ε.
Пусть концы текущего отрезка хранятся в переменных x0, x1. Инвариантом цикла является утверждение о том, что функция принимает значения разных знаков в точках x0, x1:

I(x0, x1): f(x0)*f(x1) http://localhost:3232/img/symbols/le.gif 0 

Начальные значения:

x0 = a,  x1 = b 

Условием завершения цикла является утверждение о том, что длина отрезка меньше ε:

Q(x0, x1): |x1-x0| < ε       

(знак модуля используется потому, что в условии задачи не требуется выполнения неравенства a < b).
Выпишем алгоритм вычисления корня функции с заданной точностью:

вещ корень функции на отрезке(вх: вещ a, вещ b, вещ eps)
| дано: f(a) * f(b) <= 0,
|       eps > 0 - очень маленькое число;
| надо: вычислить корень функции f на отрезке [a, b] с
|       точностью eps;
начало алгоритма
| вещ x0, x1, c;
|
| // инициализация
| x0 := a; x1 := b;
| утверждение: f(x0) * f (x1) <= 0;
|
| цикл пока |x1 - x0| >= eps
| | инвариант: f(x0) * f (x1) <= 0;
| | c := (x0 + x1) / 2; // Середина отрезка [x0, x1]
| | если f(x0) * f(c) <= 0
| | | то
| | |   x1 := c
| | | иначе
| | |   утверждение: f(c) * f(x1) <= 0
| | |   x0 := c
| | конец если
| конец цикла
|
| утверждение: |x1 - x0| < eps  и
|              f(x0) * f (x1) <= 0;
| ответ := (x0 + x1) / 2;
конец алгоритма
 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика