Ингредиенты доказательства корректности цикла

Ингредиенты доказательства корректности цикла

Простой пример вычисления максимума массива иллюстрирует общую схему циклических вычислений, применимую ко многим ситуациям. Вы определяете, что решением некоторой проблемы является элемент, принадлежащий n-мерной поверхности POST. В некоторых случаях POST может содержать ровно один элемент - решение, но обычно может быть более чем одно приемлемое решение проблемы. Циклы полезны, когда нет прямого способа достичь решения "одним выстрелом". Но у вас есть непрямая стратегия, вы можете, например, прицелиться и попасть в m-мерную поверхность INV, включающую POST (для m>n). Инвариантом является то, что поверхность попадания все время содержит POST. Итерация за итерацией приближаемся к POST, сохраняя истинность INV. Следующий рисунок иллюстрирует этот процесс:

Рис. 11.8.  Вычисление цикла (из [М 1990])

Вычисление цикла имеет следующие ингредиенты:

[x]. Цель post, определяемую как свойство, выполняемое в любом допустимом заключительном состоянии. Пример: "Result является максимумом массива". На рисунке цель post представлена множеством состояний POST.

[x]. Инвариант цикла inv, являющийся обобщением цели, так что можно говорить, что цель - это частный случай инварианта. Пример: "Result является максимумом текущей нарезки массива". Инвариант цикла поиска цели, изображенный на рисунке: "Каждая точка лежит на поверхности, содержащей POST.

[x]. Точку инициализации init, о которой известно, что она должна быть в INV, другими словами должна обеспечить выполнение инварианта.

[x]. Преобразование body, начинающееся в INV, но не в POST, вырабатывающее точку более близкую к POST, но все еще остающуюся в INV. Тело цикла функции maxarray является примером подобного преобразования.

[x]. Верхняя граница числа применений body, необходимого для перевода точки из INV в POST. Как будет пояснено ниже, этот параметр необходим для определения варианта.

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

Практический способ гарантии завершения циклического процесса состоит в связывании с итерационным процессом целочисленной величины - варианта цикла, обладающего следующими свойствами:

[x]. Вариант всегда не отрицателен.

[x]. Любое выполнение тела цикла уменьшает вариант.

Так как целочисленная неотрицательная величина не может уменьшаться бесконечно, то наличие варианта позволяет гарантировать завершение цикла. Вариант является верхней границей, максимальным числом применений body, приводящим точку в POST. В задаче нахождения максимума найти вариант просто: t.upper - i. Это выражение удовлетворяет обоим условиям:

[x]. Предусловие программы требует положительности t.capacity; другими словами, программа применима только к непустым массивам. Инвариант класса ARRAY задает: capacity = upper - lower + 1. Отсюда следует, что свойство i <= t.upper будет выполняться после инициализации i значением t.lower.

[x]. Любое выполнение тела цикла выполняет инструкцию i := i + 1, уменьшая вариант на единицу.

В этом примере цикл является простым итерированием на последовательности целых чисел в конечном интервале, известный в языках программирования, как "цикл For" или "цикл DO", завершение которого не трудно проверить. Для более изощренных циклов число требуемых итераций определить не так просто, выявление завершения становится сложной задачей, единственным универсальным способом является нахождение варианта.

Нам понадобится еще одно понятие, преобразующее только что набросанную схему в программный текст, описывающий цикл. Мы нуждаемся в простом способе определения того, что текущая итерация достигла цели (постусловия) post. Поскольку итерация конструируется так, чтобы обеспечить выполнение INV, а POST является частью INV, то обычно можно найти условие exit такое, что элемент из INV принадлежит POST тогда и только тогда, когда выполняется exit. Другими словами, постусловие post и инвариант inv связаны соотношением:

post = inv and exit

так что мы можем остановить цикл, - чьи промежуточные состояния по построению удовлетворяют inv, - как только выполнится exit. В этом состоянии, следовательно, будет выполнено и post.