"Информатика (базовый и углублённый уровень)", Гейн А.Г., Сенокосов А.И.
Инвариант цикла — утверждение о переменных, которое верно до первой проверки условия и остаётся верным после каждой итерации. Он помогает описать, какая часть задачи уже выполнена и что означают текущие значения переменных. Чтобы доказать правильность цикла, проверяют начальную истинность инварианта, его сохранение и то, что при остановке из него следует нужный результат. Сам по себе инвариант не гарантирует завершение цикла.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Инвариант цикла — утверждение о переменных программы, истинное перед первой проверкой условия цикла и сохраняющее истинность после каждой итерации. Оно связывает значения переменных с уже выполненной частью задачи. Благодаря этому можно не просто проследить команды, а объяснить, почему алгоритм движется к правильному ответу.
Инициализация инварианта — начальные присваивания, после которых проверяют, что инвариант уже выполняется. Это необходимо, потому что доказательство сохранения работает только при истинном утверждении до очередного шага. Если оно неверно с самого начала, последующие итерации не исправят доказательство.
Сохранение инварианта — свойство тела цикла: если утверждение верно перед итерацией и тело выполняется, то после него утверждение остаётся верным. Проверка показывает, что описанный смысл переменных не теряется по ходу вычислений. Учитывать нужно все команды тела и их порядок.
Условие завершения — условие, при котором цикл прекращает работу. Вместе с инвариантом оно помогает обосновать правильность результата: условие остановки сообщает, что работа закончена, а инвариант — что именно было вычислено. Отдельно ещё требуется убедиться, что остановка действительно наступит.
Инвариант связывает текущее состояние программы с ходом решения задачи: он описывает, что уже обработано и какой смысл имеют значения переменных. Например, при просмотре массива переменная-счётчик может показывать число обработанных элементов, а другая переменная — максимум среди них. Такая связь нужна, чтобы перейти от отдельных команд к утверждению о всей выполненной работе. Без неё значения переменных остаются лишь числами, не объясняющими, почему результат верен.
Инвариант выбирают, исходя из требуемого результата. Если он слишком общий, то может оставаться верным, но не сообщать ничего полезного о вычислении; если в нём слишком много лишних деталей, его трудно проверять после каждой итерации. Подходящая формулировка должна описывать уже обработанную часть задачи и смысл накопленных данных. После остановки из неё вместе с условием выхода должно быть возможно вывести ответ.
Корректность инварианта доказывают в три шага. Сначала проверяют, что он верен в начальном состоянии, то есть до первого выполнения тела цикла. Затем рассматривают одну произвольную итерацию: предполагают истинность утверждения перед ней и показывают, что после команд тела оно сохраняется. Наконец, используют инвариант и факт остановки, чтобы получить требуемый результат; это похоже на доказательство по индукции, где начальный случай сменяется переходом.
При проверке сохранения нужно проследить все команды тела в их настоящем порядке. Переменные могут временно получить значения, при которых инвариант на середине итерации не выполняется, хотя к её концу он восстановится. Поэтому утверждение обычно проверяют на границах итераций — например, непосредственно перед телом и после него. Если в теле несколько присваиваний, полезно записать, как меняются величины после каждого из них.
Инвариант не доказывает, что цикл когда-нибудь остановится: он может сохраняться при бесконечном выполнении. Для завершения отдельно анализируют условие и изменение переменных. Например, проверяют, что счётчик приближается к границе, не застревает и не перескакивает через неё. Таким образом, правильность результата и факт окончания работы — связанные, но разные вопросы.
| Этап | Что проверяют | Что это даёт |
|---|---|---|
| Инициализация | Инвариант верен до первой итерации | Подтверждает начальную основу доказательства |
| Сохранение после итерации | Истинность утверждения после выполнения тела | Показывает, что свойство действует на каждом шаге |
| Завершение цикла | При каких значениях переменных цикл останавливается | Позволяет применить условие выхода |
| Вывод результата | Следует ли ответ из инварианта и остановки | Обосновывает правильность вычисления |
Пользуйся таблицей как последовательностью проверок: не переходи к выводу результата, пока не обоснованы начальная истинность и сохранение. На этапе остановки учитывай отрицание условия, при котором цикл продолжался. Последняя строка связывает доказанное свойство переменных с формулировкой задачи.
Цикл суммирует целые числа от 1 до n. Перед очередной итерацией i — следующее число, которое нужно прибавить, а S — уже накопленная сумма. Требуется доказать, что после цикла S равна сумме всех чисел от 1 до n. Будем считать, что тело выполняется при i ≤ n, прибавляет i к S, а затем увеличивает i на 1.
Выберем инвариант S = 1 + 2 + … + (i − 1). Он говорит, что S содержит сумму всех чисел, которые стоят перед текущим i. Перед первой итерацией i = 1, а S = 0; сумма пустого набора равна 0, поэтому утверждение верно.
Пусть перед итерацией инвариант выполняется. Сначала к S прибавляют i, и сумма становится равной 1 + 2 + … + i. Затем i увеличивают на 1, поэтому новое значение правой части — 1 + 2 + … + (i − 1) для нового i. Значит, инвариант сохранён.
Цикл останавливается, когда i = n + 1. По инварианту S = 1 + 2 + … + ((n + 1) − 1), то есть S = 1 + 2 + … + n. Следовательно, программа получила требуемую сумму.
Ответ: инвариант верен вначале, сохраняется после каждой итерации, а при остановке из него следует, что S — сумма чисел от 1 до n. Для полного доказательства завершения дополнительно учитывают, что i увеличивается на 1 и в итоге становится больше n.
Дан непустой массив, элементы которого цикл просматривает по порядку. Переменная max хранит текущий максимум, а k обозначает число уже обработанных элементов. Докажем, что после завершения max равен наибольшему элементу всего массива. Первый элемент удобно сразу записать в max, считая, что уже обработан один элемент.
Сформулируем инвариант: после обработки первых k элементов max равен наибольшему из них. При k = 1 он верен, поскольку единственный элемент одновременно является максимумом обработанной части. Это и есть начальная проверка.
Пусть инвариант верен для k элементов. Цикл сравнивает max со следующим элементом массива и сохраняет больший из двух. После этого в max находится наибольший среди первых k + 1 элементов: прежний максимум учитывает первые k, а сравнение добавляет новый элемент. Значит, утверждение сохраняется.
После обработки массива k равно числу его элементов. Инвариант тогда говорит, что max — наибольший элемент всего массива. Поскольку массив непустой и каждый элемент просмотрен, других значений, способных увеличить максимум, не осталось.
Ответ: переменная max содержит максимум массива. Для завершения цикла счётчик обработки должен увеличиваться, пока не достигнет длины массива.
Алгоритм начинает с исходных чисел a и b и повторяет присваивание (a, b) := (b, a mod b), пока b ≠ 0. Здесь a mod b — остаток от деления a на b. Нужно доказать, что в конце a является наибольшим общим делителем исходной пары чисел. Рассматриваем положительные целые числа.
Возьмём инвариант НОД(a, b) = НОД исходных чисел. В начале a и b как раз равны исходным числам, поэтому утверждение верно. НОД обозначает наибольший общий делитель пары.
Пусть перед переходом a = qb + r, где r = a mod b. Число делит и a, и b тогда и только тогда, когда оно делит b и r: из a = qb + r следует делимость r, а из a = qb + r следует делимость a, если делятся b и r. Поэтому НОД(a, b) = НОД(b, r), и присваивание сохраняет инвариант.
Алгоритм останавливается при b = 0. Тогда НОД(a, 0) = a для положительного a. Инвариант сообщает, что это значение совпадает с НОД исходных чисел, значит, ответ найден.
Ответ: в конце a — НОД исходной пары. При положительных числах остаток на каждом шаге уменьшается, поэтому алгоритм завершается; сохранение инварианта само по себе этого не доказывает.
Слишком расплывчатое утверждение вроде «алгоритм работает правильно» нельзя проверить по значениям переменных и использовать при остановке. Такое утверждение выбирают, потому что оно похоже на цель задачи, но пропускает смысл промежуточных вычислений. Сформулируй, что именно уже обработано и что хранит каждая важная переменная. Проверь себя: можно ли подставить конкретные значения переменных и определить, истинно ли утверждение?
Иногда инвариант проверяют только в начале и конце, забывая доказать его сохранение на каждом шаге. Начальное и конечное состояния ничего не говорят о том, что происходит между ними: алгоритм мог нарушить свойство в середине. Чтобы не пропустить этот этап, возьми произвольное состояние перед итерацией и проследи все команды тела. Проверка себя проста: объяснено ли, почему истинность до шага влечёт истинность после него?
Инвариант путают с условием цикла, потому что оба утверждения относятся к переменным. Но условие отвечает на вопрос, выполнять ли тело дальше, а инвариант описывает сохраняющийся смысл состояния. Например, условие i ≤ n может быть истинно только во время работы цикла, тогда как инвариант о накопленной сумме должен оставаться верным и при остановке. Проверь себя: если заменить условие цикла, изменится ли описание того, что уже вычислено? Если да, вероятно, смешаны разные понятия.
Доказательство инварианта иногда принимают за доказательство завершения. Однако цикл может сохранять утверждение бесконечно, если его переменные не приближаются к остановке. Для проверки завершения отдельно исследуй изменение величин и условие выхода, например докажи, что счётчик за конечное число шагов пересечёт границу. Спроси себя: есть ли причина, по которой цикл не может продолжаться бесконечно?
Для работы с инвариантами нужны переменные, присваивания, условия и циклы: без понимания порядка команд трудно проследить состояние программы. Доказательство инварианта связано с математической индукцией: проверка начала соответствует базовому случаю, а сохранение — переходу от одного шага к следующему. Этот метод применяют при обосновании сортировки, поиска, обработки массивов и вычисления НОД. Во всех таких задачах инвариант связывает уже выполненную часть алгоритма с ответом.
Как понять, каким должен быть инвариант цикла?
Отталкивайся от результата, который должен выдать алгоритм: сформулируй, что переменные означают после нескольких шагов. Утверждение должно быть проверяемым до и после итерации, а при остановке вместе с условием выхода приводить к нужному ответу.
В какой момент инвариант должен быть истинным?
В выбранной формулировке он должен быть истинен до первой проверки условия цикла и сохраняться на границах итераций. Важно договориться, что именно считается началом итерации: например, состояние перед выполнением тела.
Чем инвариант отличается от условия цикла?
Условие цикла определяет, продолжать ли выполнение тела или остановиться. Инвариант описывает свойство значений переменных, которое сохраняется во время работы цикла.
Почему для доказательства нужны три шага?
Проверка начального состояния показывает, что инвариант верен до первой итерации, а проверка сохранения — что он не теряется дальше. Затем при остановке объединяют инвариант с отрицанием условия цикла и выводят из них правильность результата.
Доказывает ли инвариант, что цикл обязательно завершится?
Нет. Инвариант доказывает свойство состояний цикла, но цикл может сохранять его бесконечно. Завершение обосновывают отдельно, анализируя условие цикла и изменения переменных.
§ 50. Инвариант цикла
