| Каталог | Индекс раздела |
| Назад | Оглавление | Вперед |
Теорема 8 упоминает последовательные состояния, соединенные рекуррентными соотношениями. Смысл этой теоремы двойной: она может применяться для доказательства утверждений о данной конкретной программе, но также - и это, я думаю, более важно - она подсказывает нам, когда мы встречаемся с задачей создания программ, использование фразы while для проблемы, математическая формулировка которой представляется рекуррентным соотношением. Мы собираемся проиллюстрировать это несколькими примерами.
Рассмотрим последовательность пар ai, ci, заданную, как
Упражнение. Докажите последнюю формулу. (Тут нечего делать по программированию, это алгебра средней школы. Ключ к доказательству может быть найден в соотношении
Требуется использовать это рекуррентное соотношение для приближенного вычисления значения 1/b; очевидно, что мы не можем вычислить бесконечно много элементов последовательности a0, a1, a2, ..., но мы можем принять ak как достаточно близкую (насколько близкую?) аппроксимацию 1/b, когда ck меньше (по абсолютной величине) заданной, маленькой положительной погрешности, названной "eps". (Этот пример имеет исторический интерес; он был взят из библиотеки подпрограмм для EDSAC 1, первой в мире хранимой программы для автоматического компьютера. Коды команд этого компьютера не содержали инструкции деления, и одним из методов, используемых на этом компьютере для получения частного был основан на данном рекуррентном соотношении.)
Теорема 8 говорит о "части, s, пространства состояний", и цикл
while B(s) do s:= S(s)
предполагает, что при начальном состоянии s0 состояние si после i-го выполнения повторяющегося оператора будет удовлетворять
si = S(si-1) (3)
Наши рекуррентные соотношения (2) находятся точно в форме (3), если мы идентифицируем состояние si парой значений ai, ci. То есть, чтобы охватить часть s пространства состояний, мы должны ввести две переменные, назовем их в данном обсуждении A и C, и мы будем обозначать их значения после i-го выполнения повторяющегося оператора Ai и Ci соответственно. Мы связываем состояние si (задаваемое значениями Ai и Ci) с парой значений ai, ci соотношением
Ai = ai (4) Ci = ci
(Помните, с левой стороны индекс "i" означает "значение переменной после i-го выполнения повторяющегося оператора", с правой стороны индекс i ссылается на рекуррентную последовательность, заданную (1) и (2). Было бы полезно назвать две переменные "a" и "c" вместо "A" и "C", т.е., не делать различия между величинами, определенными в математической формулировке, с одной стороны, и ассоциированными с ними переменными в программе, с другой стороны. Но поскольку эта ассоциация является объектом нашего обсуждения, неразличение их будет для него фатальным.)
В рамках объявления "real A, C" будет очень простой задачей написать часть программы:
A:= 1; C:= 1 - b; while abs(C)eps do begin A:= (1 + C) * A; C:= C * C; end
Первая строка создает правильное состояние s0 и делает это в соответствии с (4) и (1), повторяющийся оператор имеет форму, символически обозначенную как "s:= S(s)" - см. примечание ниже - в соответствии с (4)и (2), а условие гарантирует, что после завершения
(Ak)=) A = ak
будет сохранено с правильным значением k.
Упражнение. Докажите, что цикл завершается.
Примечание. Символическое присваивание "s:= S(s)" имеет форму двух операторов присваивания
A:= (1 + C) * A; C:= C * C
При начальных условиях A = ai-1, C = ci-1 первое присваивание будет эквивалентно
A:= (1 + ci-1) * ai-1
А после первого, но перед вторым присваиванием мы имеем - с учетом (2) -
A = ai, C = ci-1 .
Мы имеем законченную пару A = ai-1, C = ci только после второго присваивания. Благодаря явному появлению индексов, порядок двух отношений, составляющих (2) несущественен, в отличие от двух операторов присваивания, составляющих повторяющийся оператор, чей порядок жизненно важен.
Упражнение. В той же библиотеке подпрограмм EDSAC 1 была использована следующая схема. Рассмотрим последовательность пар ai, ci, заданную как
Докажите последнюю формулу и сделайте программу, используя ее для приближенного вычисления квадратного корня. Ключ к доказательству может быть найден в отношении
(1 - ci-1)-.5 = (1 + .5 * ci-1) * (1 - i)-.5 .
Докажите также завершение цикла в сделанной программе.
Упражнение. В той же библиотеке подпрограмм EDSAC 1 была использована следующая схема. Рассмотрим последовательность троек inci, si, xi, заданную как
Докажите это соотношение и сделайте программу, использующую его для приближенного вычисления логарифма значения аргумента в заданном интервале. (В этой программе "log 2" может рассматриваться как известная константа, которая, фактически, определяет основу логарифма.) Ключ может быть найден в инвариантности соотношения
log(arg) = si + inci * log(xi) / log 2 .
Наш следующий пример очень прост; он настолько традиционен, что может быть назван стандартным. (Ни один уважающий себя курс программирования не обходит его, часто он является самым первым примером цикла; Петер Наур использует его в своей статье "Proof of algorithm by general snapshots", 1966, BIT, 6, pp 310-316.)
Дана последовательность значений
a[1], a[2], a[3], ... , a[N] (при N
и переменная, названная "max". Сделать часть программы, присваивающую переменной с именем "max" максимальное значение, встречающееся в последовательности. (Поскольку N , последовательность не пустая и, следовательно, задача имеет смысл; не требуется, чтобы любые два значения в последовательности отличались друг от друга, максимальное значение может встречаться более одного раза.) Если мы приветствуем накопление опыта, приглашаем читателя попробовать самостоятельно сделать эту часть программы прежде, чем читать дальше.
1
Как мы определим максимальное значение, встречающееся в последовательности длиной N для общего случая N >= 1? Если мы назовем "maximumk" максимальное значение, встретившееся среди первых k элементов a[1], a[2], ... , a[k], то
maximumN
maximumk задается
при k = 1 |
как базовое: maximum1 = a[1]используя знание того, что максимальным элементом в последовательности длиной 1 должен быть единственный элемент, имеющийся в этой последовательности |
(5) |
при k > 1 |
как рекуррентное соотношение:
предполагая, что мы знаем функциюmaximumk = MAX(maximumk-1,a[k]) MAX двух аргументов |
(6) |
Рекуррентное соотношение (6) представляет для нас дополнительную трудность, поскольку оно не находится в форме
si = S(si-1
так как - из-за a[k] - значение k встречается в правой части не только в индексе "k-1". Чтобы преодолеть это, мы используем прием, который может быть назван методом. Если мы назовем nk k-ое натуральное число, то nk = k; номер nk удовлетворяет очевидному рекуррентному соотношению nk = 1 + nk-1. Теперь мы можем переписать определение для последовательности значений maximumk в форме определения для пар nk, maximumk:
при k = 1 |
n1 = 1 |
(7) |
при k > 1 |
nk = 1 + nk-1 maximumk = MAX(maximumk-1, a[1 + nk-1]) |
(7) |
и теперь все рекуррентные соотношения находятся в форме si = S(si-1), единственное - тривиальное - различие состоит в том, что Теорема 8 начинается с i = 0, а здесь - с k = 1. Прием, названный нами методом, показывает, что нам нужна вторая (целая) переменная; назовем ее "m". Наше состояние si будет связано (при k = i + 1)
maxi = maximumk mi = nk
Наша часть программы теперь становится такой:
max:= a[1]; m:=1;
while m < N do begin m:= m+1;
max:= MAX(max, a[m])
end .
Опять-таки, порядок двух присваиваний имеет значение.
Мы имеем вышеприведенные рассуждения и явную ссылку на рекуррентное соотношение Теоремы 8, поскольку она показывает механизм, ведущий к заключению о том, что часть пространства состояний, на которой выполняется повторение, должна содержать в себе дополнительную переменную. Даже не очень тренированный программист придет к такому заключению "интуитивно", и в дальнейшем я буду предполагать, что мой читатель обладает такой интуицией. Тогда - и только тогда! - путь рассуждений, который приведет к созданной нами программе, будет значительно короче. Он не рассматривает - "статически", так сказать - последовательность значений s0, s1, ... в смысле, что он заботится о значениях индекса i в si. Он обращается непосредственно к Теоремам 5 и 6 и работает в терминах утверждений, правомерных для (до и после) любого выполнения повторяющегося оператора. Цена, заплаченная за это, - необходимость отдельно доказывать завершение.
Дана основа
k = 1 maximum1 = a[1]
и шаг
1 < kN maximumk = MAX(maximumk-1, a[k])
программист "интуитивно" вводит две переменные, которые он называет maximum и k для краткости, и отношение, которое должно быть инвариантным
P: 1
(Здесь любое использование maximum и k относится к текущему значению названных переменных, тогда как maximumk относится к значению, задаваемому рекуррентным соотношением. Это двойное использование одного и того же имени является хитростью, но программисты так желают. Я тоже.)
Программа теперь состоит из двух частей: установление соотношения P в соответствие с основой и итерационное увеличение k при инвариантности соотношения P, т.е., в соответствии с шагом.
Инициализация
устанавливает"maximum:= a[1]; k := 1"
while k < N do
begin k:= k + 1;
maximum:= MAX(maximum, a[k])
end
приводит к тому, что повторяющийся оператор выполняется при комбинированном соотношении "B and P", т.е.,
k < N and 1
которое сокращено до
1
Чтобы показать, что выполнение повторяющегося оператора при начальном условии (9) оставляет соотношение P действительным, желательно различать состояния до и после его выполнения; сейчас сделать это трудно из-за индексов (почему?), поэтому мы отличаем значения после выполнения, помечая их штрихом.
Сначала мы имеем соотношение (9); после присваивания k:= k + 1 мы имеем соотношение k' = k+1, а из первой части (9), т.е., 1 , следует k < N2 , что подразумевает
k' < N
1
Второе присваивание теперь становится maximum:= MAX(maximumk, a[k']), приводя в результате к отношению
maximum' = maximumk' (11)
Отношение (10) и (11) превращаются в повторение P, но теперь с величинами, помеченными штрихом.
Завершение следует из того факта, что каждое выполнение повторяющегося оператора включает в себя действительное увеличение целой переменной k. После завершения мы имеем, в соответствии с Теоремой 5, "P and non B", т.е.,
1
из первого и последнего членов мы выводим k = N, а средняя часть
maximum = maximumk
завершает доказательство.
Упражнение. Сделайте программу, присваивающую "prod:= X * Y" для целых X и Y, удовлетворяющих условию X , 0Y
0
| a) | используя только сложение и вычитание, |
| b) | используя, кроме того, булевскую функцию "odd(x)" [odd - нечетный. - прим. перев.], удвоение числа и деление числа пополам. (Так называемая, египетская манипуляция.) |
prod:= REM(X, Y" для целых X и Y, X 0, Y 0, где функция REM(X, Y) - остаток от деления X на Y
| a) | используя только сложение и вычитание, |
| b) | используя, кроме того, удвоение числа и деление числа пополам. Модифицируйте обе программы так, чтобы кроме того имело место "quot:= QUOT(X, Y)" [quot - частное. - прим. перев.]. (Так называемая, китайская нотация.) |
Мы заключаем этот раздел примером (стандартной) ситуации, в которой рекуррентное соотношение не будет вслепую переведено в цикл. Даны две последовательности значений
x[1], x[2], ... , x[N] и y[1], y[2], ... , y[N] при N
сделать программу, присваивающую булевской переменной с именем "eq" значение true, если x[i] = y[i] для всех i, удовлетворяющих 1 , и значение i Nfalse, если в этом ряду значений i есть такие, что x[i] . (Последовательность может быть пустой, в этом случае "
y[i]" должна получать значение true.)
Как мы определим эквивалентность последовательностей длиной N для общего случая N? Опять-таки через рекуррентное соотношение. Пусть eqi означает "не обнаружена разница в первых i парах"; тогда последовательность eqi задается как
при i = 0 |
eq0 = true |
при i > 0 |
eqi = eqi-1 and x[i] = y[i] |
Конечным эффектом программы должно быть eq:= eqN.
Бездумный перевод в инициализацию, за которой следует повторение, приведет к
eq:= true; i:= 0; while i < N do begin i:= i + 1; eq:= (eq and x[i] = y[i]) end
Хотя вышеприведенная программа корректна, следующая программа, кроме того, что она также корректна, является в среднем более эффективной:
eq:= true; i:= 0; while i < N and eq do begin i:= i + 1; eq:= (x[i] = y[i]) end
потому, что она прекращает повторения, как только найдено различие.
Упражнение. Докажите корректность второй программы.
| Назад | Оглавление | Вперед |
| Каталог | Индекс раздела |