Инварианты и варианты цикла
Наши следующие и последние конструкции утверждений помогут строить корректные циклы. Эти конструкции являются прекрасным дополнением рассмотренных ранее механизмов. Поскольку они не являются специфической частью ОО-метода, то вы вправе пропустить этот раздел при первом чтении.
Трудности циклов
Возможность повторять некоторые вычисления произвольное число раз, не поддаваясь усталости, без случайных потерь чего-либо важного, - в этом принципиальное отличие компьютерных вычислений от возможностей человека. Вот почему циклы так важны. Трудно вообразить, что можно было бы делать в языках, в которых были бы только две управляющие структуры - последовательность и выбор, - но не было бы циклов и не было бы поддержки рекурсии, еще одного базисного механизма поддержки итеративных вычислений.
Но с мощностью приходят и риски. У циклов дурная слава, - их трудно заставить работать правильно. Типичными для циклов являются:
*Ошибки "больше-меньше" (выполнение цикла слишком много или слишком мало раз).
*Ошибки управления пограничными ситуациями, например пустыми структурами. Цикл может правильно работать на больших массивах, но давать ошибки, когда у массива один элемент или он вообще пуст.
*Ошибки завершения ("зацикливание") в некоторых ситуациях.
Бинарный поиск - один из ключевых элементов базового курса "Введение в информатику" (Computer Science 101) - хорошая иллюстрация "коварства" циклов даже в относительно тривиальной ситуации. Рассмотрим целочисленный, упорядоченный по возрастанию массив t с индексами от 1 до n. Используем алгоритм бинарного поиска для ответа на вопрос: появляется ли целое x среди элементов массива. Если массив пуст, ответ должен быть "нет", если в массиве ровно один элемент, то ответ "да" тогда и только тогда, когда элемент массива совпадает с x. Суть бинарного поиска, использующего упорядоченность массива, проста: вначале x сравнивается со средним элементом массива, если есть совпадение, то задача решена, если x меньше среднего элемента, то поиск продолжается в верхней половине массива, в противном случае - в нижней половине. Каждое сравнение уменьшает размер массива вдвое. Ниже представлены четыре попытки реализации этой простой идеи. К несчастью, все они содержат ошибки. Вам предоставляется случай поупражняться в поиске ошибок и установить, в какой ситуации каждый из алгоритмов не работает нужным образом.
|Напомню, t @ m означает элемент массива t с индексом m. Знак операции // означает деление нацело, так что 7 // 2 и 6 // 2 дают значение 3. Синтаксис цикла будет дан ниже, но он должен быть и так понятен. Предложение from вводит инициализацию цикла. |
|
BS1 from
i := 1; j := n until i = j loop
m := (i + j) // 2 if t @ m <= x then i := m
else
j := m end end
Result := (x = t @ i)
|
BS2 from
i := 1; j := n; found := false until i = j and not found loop m := (i + j) // 2
if t @ m < x then i := m + 1
elseif t @ m = x then found := true
else
j := m - 1 end
end
Result := found
|
|
BS3 from
i := 0; j := n until i = j loop
m := (i + j + 1) // 2 if t @ m <= x then
i := m + 1 else
j := m end end
if i >= 1 and i <= n then Result := (x = t @ i) else
Result := false end
|
BS4 from
i := 0; j := n + 1 until i = j loop
m := (i + j) // 2 if t @ m <= x then i := m + 1
else
j := m
end end
if i >= 1 and i <= n then Result := (x = t @ i) else
Result := false end
|
Таблица 11.3.Четыре (ошибочных) попытки реализации бинарного поиска
Сделаем циклы корректными
Разумное использование утверждений может помочь справиться с такими проблемами. Цикл может иметь связанное с ним утверждение, так называемый инвариант цикла ( loop invariant ), который не следует путать с инвариантом класса. Он может также иметь вариант цикла ( loop variant ), являющийся не утверждением, а, обычно целочисленным выражением. Совместно, инвариант и вариант позволяют гарантировать корректность цикла.
Для понимания этих понятий необходимо осознать, что цикл - это способ вычислить некоторый результат последовательными приближениями (successive approximations).
Рассмотрим тривиальный пример вычисления максимума в целочисленном массиве, используя очевидный алгоритм:
maxarray (t: ARRAY [INTEGER]): INTEGER is -- Максимальное значение массива t require
t.capacity >= 1 local
i: INTEGER do
from
i := t.lower
Result := t @ lower until i = t.upper loop i := i + 1
Result := Result.max (t @ i) end
end
В разделе инициализации i получает значение нижней границы массива, а сущность Result - будущий результат вычислений - значение первого элемента. Предусловие гарантирует существование хотя бы одного элемента в массиве. Производя последовательные итерации в цикле, мы достигаем верхней границы массива, увеличивая на каждом шаге i н а 1, и заменяя Result значением элемента t @ i, если этот элемент больше чем Result. Для нахождения максимума двух целых используется функция max, определенная для класса integer: a.max(b) возвращает максимальное значение из a и b.
Это пример вычисления последовательными приближениями. Мы продвигаемся вверх по массиву последовательными нарезками: [lower, lower] , [lower, lower+1] , [lower, lower+2] и так вплоть до полного приближения [lower, upper].
Свойство инварианта цикла состоит в том, что на каждом шаге прохождения цикла Result
представляет максимум текущей нарезки массива. Инициализация гарантирует выполнимость этого свойства непосредственно перед началом работы цикла. Каждая итерация увеличивает нарезку, сохраняя истинность инварианта. Цикл завершает свою работу, когда очередная нарезка массива совпадает со всем массивом. В этом состоянии истинность инварианта означает, что Result является максимумом массива, что и является требуемым результатом работы.
Рис. 11.7. Аппроксимация массива последовательными нарезками
Ингредиенты доказательства корректности цикла
Простой пример вычисления максимума массива иллюстрирует общую схему циклических вычислений, применимую ко многим ситуациям. Вы определяете, что решением некоторой проблемы является элемент, принадлежащий n -мерной поверхности POST. В некоторых случаях POST может содержать ровно один элемент - решение, но обычно может быть более чем одно приемлемое решение проблемы. Циклы полезны, когда нет прямого способа достичь решения "одним выстрелом". Но у вас есть непрямая стратегия, вы можете, например, прицелиться и попасть в m -мерную поверхность INV, включающую POST (для m>n ). Инвариантом является то, что поверхность попадания все время содержит POST. Итерация за итерацией приближаемся к POST, сохраняя истинность INV. Следующий рисунок иллюстрирует этот процесс:
Рис. 11.8. Вычисление цикла (из [М 1990]) Вычисление цикла имеет следующие ингредиенты:
*Цель post, определяемую как свойство, выполняемое в любом допустимом заключительном состоянии. Пример: " Result является максимумом массива". На рисунке цель post представлена множеством состояний POST.
*Инвариант цикла inv, являющийся обобщением цели, так что можно говорить, что цель - это частный случай инварианта. Пример: " Result является максимумом текущей нарезки массива". Инвариант цикла поиска цели, изображенный на рисунке: "Каждая точка лежит на поверхности, содержащей POST.
*Точку инициализации init, о которой известно, что она должна быть в INV, другими словами должна обеспечить выполнение инварианта.
*Преобразование body, начинающееся в INV, но не в POST, вырабатывающее точку более близкую к POST, но все еще остающуюся в INV. Тело цикла функции maxarray является примером подобного преобразования.
*Верхняя граница числа применений body, необходимого для перевода точки из INV в POST. Как будет пояснено ниже, этот параметр необходим для определения варианта.
Последовательные приближения один из главных инструментов численного анализа. Но там эта идея понимается шире. Важная разница состоит в том, что в чистой математике допускаются бесконечные вычисления, последовательность может иметь предел, даже если он не достигается конечным числом приближений. Последовательность 1/n имеет предел 0, хотя среди членов последовательности нет числа 0. В компьютерных вычислениях мы хотим видеть результаты на нашем экране еще при нашей жизни, так что мы настаиваем, все аппроксимирующие последовательности достигают своей цели после конечного числа итераций.
|Компьютерные реализации численных алгоритмов также требуют конечной сходимости. Даже когда математический алгоритм сходится на бесконечности, мы обрываем процесс сходимости, когда полагаем, что решение найдено с требуемой точностью. |