Что такое инвариант цикла
Инвариант цикла
Программисты часто составляют циклы, как правило, чтобы достичь какой-то конкретной цели: найти элемент с заданными свойствами, выполнить сортировку и т. п. Но как убедиться в том, что цель будет достигнута, не выполняя цикл непосредственно? В этом нам поможет инвариант цикла.
Рассмотрим использование инварианта цикла на примере поиска индекса наименьшего элемента в целочисленном массиве.
Инвариант цикла будет выглядеть так:
Инициализируем переменные, входящие в инвариант, так, чтобы он был истинным до начала выполнения цикла:
Инвариант цикла && Условие_окончания_цикла => Цель цикла
Вместо условия окончания можно использовать условие выполнения цикла. В нашем случае это: nextToCheck (пока есть элементы для проверки). Как только оно будет нарушено (станет ложным), выполнение цикла прекратится
Таким образом, подобрав инвариант цикла и обеспечив его сохранение, мы можем гарантировать достижение цели, не выполняя сам цикл.
Вопросы для самопроверки при составлении циклов:
При составлении циклов может оказаться удобным понятие области неопределенности, используемое в вычислительных методах математики. Область изменения параметров задачи (в нашем примере: [0,n)) можно разделить на две части: исследованную область (для которой найден TemporarySmallest : [0,nextToCheck) ) и область неопределенности ( [nextToCheck,n) ). Необходимо составлять цикл так, чтобы на каждой итерации область неопределенности сокращалась.
Инвариант цикла будет таким:
Непосредственно перед циклом инициализируем значение numSorted :
что делает инвариант цикла истинным.
На каждой итерации количество numSorted увеличивается на единицу. Чтобы этого достичь, выбирается наименьший среди первых [0,n-numSorted) неотсортированных элементов, и меняется местами (с помощью функции swap() ) c элементом n-numSorted
Таким образом, отсортированный «хвост» массива всякий раз удлиняется на один элемент, а неотсортированная «голова» уменьшается.
Что почитать
Вирт Н. Алгоритмы + структуры данных = программы
Что такое инвариант цикла
Начнем, как обычно, с задачки. В строке, содержащей цепочки одинаковых символов, нужно их обнаружить и заменить на счетчик повторений и один такой символ. Например, из строки « abcdddddddddefggggggggggggggggggx » получить « abc 9 def 18 gx ». Извечный вопрос русской интеллигенции: «Что делать?».
Типичный ход рассуждений: «Будем просматривать строку в цикле. Если обнаружим повторяющийся фрагмент…» содержит одну существенную недосказанность: как процесс обнаружения повторяющегося фрагмента связан с циклом посимвольного просмотра неповторяющихся символов. Это отдельный процесс – цикл, или он является частью предыдущего.
// «Склеивание» повторяющихся символов строки.
// Использование счетчика повторений. «Грязная программа»
Мы здесь одним условием убили двух зайцев. В паре неодинаковых символов первый сохраняется всегда, а если он еще заканчивает цепочку повторяющихся, то выводится счетчик.
Здесь есть еще один «заяц». Вспомните, что любой цикл нужно проверять на первый и последний шаг. Они могут «вписаться» в имеющийся текст, а могут и нет. В нашем случае, когда текущий символ – последний в строке, мы сравниваем его с символом «конец строки», т.е. заведомо будет несовпадение и программа сработает правильно. В других случаях, например, когда строка задана объектом или типом данных, состоящим из массива символов и текущей размерности, придется в явном виде записывать условие – последний символ строки. В классическом Си это выглядит так:
if (i!=strlen(in) && in[i]==in[i+1]) k++; // Символ не последний и за ним такой же
Перейдем теперь к решению задачи. Технологически возможны два варианта обработки строки: переписывание в новую или сжатие текущей. Вариант с п ереписыванием будет проще. Мы сможем сохранить «грязную» программу, добавив в нее процесс переписывания – массив и индекс в нем. И не только. Чтобы записать счетчик в виде числа, необходимо перевести его во внешнюю форму представления, в виде цепочки символов-цифр (см.4.5).
// Использование счетчика повторений. Переписывание строки
void F2(char in[], char out[])<
int k1,j1; // Записать k в виде символов-цифр
for (k1=k; k1!=0;k1=k1/10,j++);
out[j++]=in[i]; // Переписать текущий символ
out[j]=0;> // Добавить «конец строки»
Инвариант цикла
// Отдельный цикл «измерения» повторений. «Грязная программа»
for(k=1;in[i]==in[i+k];k++); // Измерить длину цепочки
i=i+k; // Шаг цикла – длина цепочки
// Отдельный цикл «измерения» повторений. «Сжатие строки»
for(k=1;in[i]==in[i+k];k++); // Измерить длину цепочки
j=i+k; // Запомнить начало «хвоста»
int k1,j1; // Записать k в виде символов-цифр
for (k1=k; k1!=0;k1=k1/10,i++);
in[j1]=k%10+’0′; // Затереть символы цифрами числа
i++; // «Оставить» один символ
j1=i; // i – начало следующего шага
Обратите внимание, мы пилим сук, на котором сидим: сдвигаем содержимое части строки, которую еще будем просматривать. Но «пилить» нужно аккуратно, сохраняя свойство, которое мы установили в «грязной» программе: за один шаг цикла мы просматриваем (и преобразуем) фрагмент. Следовательно, по окончании этого шага индекс i должен устанавливаться сразу после сжатого фрагмента (на символе e).
Инвариант цикла и метод математической индукции
Есть еще одна неожиданная параллель между программированием и математикой. В математических доказательствах иногда используется метод математической индукции ( ММИ). Звучит он примерно так: если утверждение верно при i=0, и если из того, что оно верно при произвольном i, можно вывести, что оно будет верно при i+1, то оно будет верно всегда.
На первый взгляд, метод достаточно очевиден: некоторое свойство сохраняется на всей цепочке (последовательности), если оно выполняется в первой точке и сохраняется при переходе из каждой точки в следующую. Но в самом доказательстве есть элемент диалектики общего и частного. Метод определен для последовательности частных шагов, а доказательство проводится в общем виде для произвольного перехода от i-го шага к i+1.
Инвариант цикла может быть разным. Самым простым является утверждение типа: «в начале каждого шага цикл находится в…». Например, программа обработки слов в строке может быть построена по принципу «один шаг = одно слово». Тогда инвариантным утверждением будет: «в начале шага программа находится на начале очередного слова».
// Пословная обработка: «1 шаг = 1 слово». «Грязная программа»
while (in[i]==’ ‘)i++; // ДЛЯ ПЕРВОГО ШАГА
В соответствии с ММИ необходимо обеспечить справедливость утверждения (инварианта) на первом шаге. Для контекста суммирования это естественно: сумма последовательности из 0 элементов равна 0. Для контекста поиска максимума максимальное значение последовательности из 0 элементов или не определено, или не должно быть «меньше меньшего». Поэтому следует в качестве максимума выбирать значение первого элемента, либо использовать «защелку» для первого шага.
for (s=A[0],i=1;i if (A[i]>s) s=A[i];
for (k=-1,i=0; i // поиск минимального из положительных
if (A[i] // пропуск отрицательных
if (k==-1) k=i; // «защелка» на первый положительный
Метод математической индукции как способ доказательства, все же имеет ограниченную область применения. Гораздо важнее, что он является заключительным шагом индуктивного подхода в таких областях формально-логической деятельности как установление зависимостей, вывод формул и т.п.. Сущность его состоит в следующем:
· для решения задачи в общем виде (например, вывода формулы последовательности) первоначально рассматривается одна или несколько конкретных (частых) последовательностей шагов;
· на этой последовательности формально-логически или интуитивно формулируется искомая зависимость;
· справедливость установленной зависимости доказывается (или, наоборот, опровергается) с использованием ММИ.
Снова проведем аналогию с программированием:
· как правило, проектирование цикла начинается с анализа частного случая его работы на конкретной последовательности данных;
· на конкретном примере определяются составные части цикла и из них составляется фрагмент циклической программы;
· определяется инвариант цикла;
· проверяется, во всех ли случаях сохраняется инвариант при переходе от текущего шага к следующему, при необходимости в цикл вводятся коррективы.
При проектировании циклов часто встречаются два вида ошибок, которые имеют прямое отношение к индуктивному принципу его построения:
Что такое инвариант цикла?
Я читаю «Введение в алгоритм» от CLRS. В главе 2 авторы упоминают «петлевые инварианты». Что такое инвариант цикла?
Мне нравится это очень простое определение: ( источник )
Я понимаю, что инвариант цикла является систематическим, формальным инструментом для рассуждения о программах. Мы делаем единственное утверждение, которое сосредотачиваемся на доказательстве истинности, и называем это циклическим инвариантом. Это организует нашу логику. В то же время мы можем неформально спорить о правильности какого-либо алгоритма, но использование инварианта цикла заставляет нас очень тщательно мыслить и гарантирует, что наши рассуждения будут герметичными.
Есть одна вещь, которую многие люди не осознают сразу, имея дело с циклами и инвариантами. Они путаются между инвариантом цикла и условным циклом (условием, контролирующим завершение цикла).
Как указывают люди, инвариант цикла должен быть истинным
(хотя это может временно быть ложным во время тела цикла). С другой стороны, условное условие цикла должно быть ложным после завершения цикла, иначе цикл никогда не завершится.
Таким образом, инвариант цикла и условие цикла должны быть разными условиями.
Хорошим примером инварианта сложного цикла является бинарный поиск.
Предыдущие ответы очень хорошо определили инвариант цикла.
Алгоритм сортировки вставкой (как указано в книге):
Инвариант цикла в этом случае: под-массив [от 1 до j-1] всегда сортируется.
Теперь давайте проверим это и докажем, что алгоритм корректен.
инициализация : до первой итерации j = 2. Таким образом, под-массив [1: 1] является массивом для тестирования. Поскольку у него есть только один элемент, он сортируется. Таким образом, инвариант выполняется.
Обслуживание : это можно легко проверить, проверяя инвариант после каждой итерации. В этом случае это выполняется.
Прекращение : это шаг, на котором мы докажем правильность алгоритма.
Когда цикл заканчивается, значение j = n + 1. Снова цикл-инвариант выполняется. Это означает, что под-массив [от 1 до n] должен быть отсортирован.
Это то, что мы хотим сделать с нашим алгоритмом. Таким образом, наш алгоритм правильный.
Помимо всех хороших ответов, я полагаю, замечательный пример Джеффа Эдмондса из книги « Как думать об алгоритмах» может очень хорошо проиллюстрировать эту концепцию:
ПРИМЕР 1.2.1 «Алгоритм Find-Max с двумя пальцами»
1) Спецификации: входной экземпляр состоит из списка L (1..n) элементов. Вывод состоит из индекса i, такого, что L (i) имеет максимальное значение. Если существует несколько записей с одним и тем же значением, возвращается любая из них.
2) Основные шаги: вы выбираете метод двумя пальцами. Ваш правый палец бежит вниз по списку.
3) Мера прогресса: мера прогресса заключается в том, насколько далеко вдоль списка находится ваш правый палец.
4) Инвариант петли: петли утверждает, что ваш левый палец указывает на одну из самых больших записей, с которыми когда-либо сталкивался ваш правый палец.
5) Основные шаги: на каждой итерации вы перемещаете правый палец вниз на одну запись в списке. Если ваш правый палец сейчас указывает на вход, который больше, чем вход левого пальца, то переместите левый палец, чтобы он был правым.
6) Сделать прогресс: вы делаете успехи, потому что ваш правый палец перемещается на одну запись.
7) Поддерживать инвариант цикла. Вы знаете, что инвариант цикла поддерживается следующим образом. Для каждого шага новым элементом левого пальца является Макс (старый элемент левого пальца, новый элемент). По инварианту цикла это Max (Max (более короткий список), новый элемент). Математически это Макс (длинный список).
8) Создание инварианта петли: Сначала вы устанавливаете инвариант петли, указав двумя пальцами на первый элемент.
9) Условие выхода: вы закончите, когда ваш правый палец закончит обход списка.
10) Окончание: В конце концов, мы знаем, что проблема решается следующим образом. По условию выхода ваш правый палец встретил все записи. С помощью инварианта цикла ваш левый палец указывает на максимум из них. Верните эту запись.
11) Завершение и время выполнения: требуемое время в несколько раз превышает длину списка.
12) Особые случаи: проверьте, что происходит, когда существует несколько записей с одинаковым значением или когда n = 0 или n = 1.
14) Формальное доказательство. Корректность алгоритма следует из приведенных выше шагов.
Следует отметить, что инвариант цикла может помочь в разработке итерационных алгоритмов, если рассматривать утверждение, которое выражает важные отношения между переменными, которые должны быть истинными в начале каждой итерации и когда цикл завершается. Если это имеет место, вычисления находятся на пути к эффективности. Если false, алгоритм потерпел неудачу.
Инвариант в этом случае означает условие, которое должно быть истинным в определенной точке каждой итерации цикла.
Значение инварианта никогда не меняется
Здесь инвариант цикла означает, что «изменение, которое происходит с переменной в цикле (увеличение или уменьшение), не изменяет условие цикла, т.е. условие удовлетворяет», так что концепция инварианта цикла пришла
Это важно для циклического инвариантного доказательства, где можно показать, что алгоритм выполняется правильно, если на каждом этапе его выполнения выполняется свойство инвариантного цикла.
Чтобы алгоритм был корректным, инвариант цикла должен содержать:
Инициализация (начало)
Техническое обслуживание (каждый шаг после)
Прекращение (когда это закончено)
Таким образом, свойство инварианта цикла состоит в том, что выбранный путь имеет наименьший вес. В начале мы не добавляли ребер, поэтому это свойство имеет значение true (в данном случае это не false). На каждом шаге мы следуем по краю наименьшего веса (жадный шаг), поэтому мы снова выбираем путь с наименьшим весом. В конце мы нашли путь с наименьшим весом, поэтому наше свойство также верно.
Если алгоритм этого не делает, мы можем доказать, что он не оптимален.
Работа не переносится на следующий этап сложными, зависящими от данных способами. Каждый проход по циклу не зависит от всех остальных, а инвариант служит для связывания проходов в рабочее целое. Рассуждение о том, что ваш цикл работает, сводится к рассуждению о том, что инвариант цикла восстанавливается при каждом прохождении цикла. Это разбивает сложное общее поведение цикла на маленькие простые шаги, каждый из которых может рассматриваться отдельно. Условие проверки цикла не является частью инварианта. Это то, что заставляет цикл завершаться. Вы рассматриваете отдельно две вещи: почему цикл должен когда-либо завершаться, и почему цикл достигает своей цели, когда завершается. Цикл завершится, если каждый раз, проходя через цикл, вы приближаетесь к выполнению условия завершения. Это часто легко гарантировать: например, пошаговое изменение переменной счетчика до тех пор, пока она не достигнет фиксированного верхнего предела. Иногда обоснование прекращения является более сложным.
Инвариант цикла должен быть создан таким образом, чтобы при достижении условия завершения и инварианта «истина» цель достигалась:
invariant + termination => target
Требуется практика для создания простых и взаимосвязанных инвариантов, которые охватывают все достижения цели, кроме завершения. Лучше всего использовать математические символы для выражения инвариантов цикла, но когда это приводит к слишком сложным ситуациям, мы полагаемся на ясную прозу и здравый смысл.
С точки зрения методологии программирования, инвариант цикла можно рассматривать как более абстрактную спецификацию цикла, которая характеризует более глубокую цель цикла за пределами деталей этой реализации. Обзорная статья охватывает фундаментальные алгоритмы из многих областей информатики (поиск, сортировка, оптимизация, арифметика и т. Д.), Характеризуя каждый из них с точки зрения его инварианта.
СОДЕРЖАНИЕ
Неформальный пример
Логика Флойда – Хора
< C ∧ я >б о d у < я > < я >ш час я л е ( C ) б о d у < ¬ C ∧ я > <\ displaystyle <\ frac <\ 
Пример
В следующем примере показано, как работает это правило. Рассмотрим программу
Тогда можно доказать следующую тройку Хоара:
< Икс ≤ 10 >ш час я л е ( Икс 10 ) Икс знак равно Икс + 1 < Икс знак равно 10 > <\ displaystyle \
< Икс 10 ∧ Икс ≤ 10 >Икс знак равно Икс + 1 < Икс ≤ 10 > <\ Displaystyle \ <х
Исходя из этой предпосылки, правило while петель позволяет сделать следующий вывод:
< Икс ≤ 10 >ш час я л е ( Икс 10 ) Икс знак равно Икс + 1 < ¬ ( Икс 10 ) ∧ Икс ≤ 10 > <\ Displaystyle \ <х \ Leq 10 \>\; <\ mathtt
Поддержка языков программирования
Эйфелева
Язык программирования Whiley также обеспечивает первоклассную поддержку инвариантов цикла. Инварианты цикла выражаются с помощью одного или нескольких where предложений, как показано ниже:
Использование инвариантов цикла
Инвариант цикла может служить одной из следующих целей:
Для 1. достаточно комментария на естественном языке (как // m equals the maximum value in a[0. i-1] в приведенном выше примере).
Для 3. существуют некоторые инструменты для поддержки математических доказательств, обычно основанные на показанном выше правиле Флойда – Хоара, что данный код цикла фактически удовлетворяет заданному (набору) инварианту (ам) цикла.
Технику абстрактной интерпретации можно использовать для автоматического определения инварианта цикла данного кода. Однако этот подход ограничен очень простыми инвариантами (такими как 0 ).
Отличие от кода, инвариантного к циклам
где вычисления x = y+z и x*x можно переместить перед циклом, в результате получится эквивалентная, но более быстрая программа:
Напротив, например, свойство 0 является инвариантом цикла как для исходной, так и для оптимизированной программы, но не является частью кода, поэтому не имеет смысла говорить о «перемещении его из цикла».
Что такое инвариант цикла?
Я читаю» введение в алгоритм » CLRS. и авторы говорят об инвариантах цикла в главе 2 (сортировка вставки). Я понятия не имею, что это значит.
15 ответов
мне нравится очень простое определение: (источник)
инвариант цикла-это условие [среди переменных программы], которое обязательно верно непосредственно перед и сразу после каждой итерации цикла. (Обратите внимание, что это ничего не говорит о его истинности или ложности частично через итерацию.)
как я понимаю, инвариант цикла является систематическим, формальным инструментом для рассуждения о программах. Мы делаем одно утверждение, которое мы фокусируем на доказательстве истинности, и мы называем его инвариантом цикла. Это упорядочивает нашу логику. В то время как мы можем просто неофициально спорить о правильность некоторого алгоритма, используя инвариант цикла, заставляет нас думать очень тщательно и гарантирует, что наши рассуждения герметичны.
есть одна вещь, которую многие люди не понимают сразу при работе с петлями и инвариантами. Они путаются между инвариантом цикла и условным циклом ( условием, которое управляет завершением цикла ).
как указывают люди, инвариант цикла должен быть истинным
( хотя он может временно быть ложным во время тела цикла ). С другой стороны, условный цикл должны будет false после завершения цикла, иначе цикл никогда не завершится.
таким образом, инвариант цикла и условного цикла должны быть разные условия.
хорошим примером инварианта комплексного цикла является двоичный поиск.
таким образом, цикл условный кажется довольно прямо вперед-когда start > end цикл завершается. Но почему петля правильная? Что такое инвариант цикла, который доказывает его правильность?
инвариантом является логическое утверждение:
это утверждение является логической тавтологией-оно всегда истинно в контексте конкретного цикла / алгоритма мы пытаемся доказать. И он предоставляет полезную информацию о правильности цикла после него прекращает.
если мы вернемся, потому что мы нашли элемент в массиве, то утверждение очевидно, так как если A[mid] == a затем a находится в массиве и mid должна быть между началом и концом. И если цикл завершается, потому что start > end тогда не может быть такого числа, что start и mid и поэтому мы знаем, что заявление A[mid] == a должно быть false. Однако в результате общее логическое утверждение остается истинным в нулевом смысле. ( В логике утверждение if (false ) тогда ( something) всегда истинно. )
предыдущие ответы очень хорошо определили инвариант цикла.
теперь позвольте мне попытаться объяснить, как авторы CLRS использовали инварианты цикла для доказательства достоверность рода вставки.
алгоритм сортировки вставки(как указано в книге):
инвариант цикла в этом случае (источник: CLRS book): Subarray[1 to j-1] всегда сортируется.
теперь давайте проверим это и докажем, что алгоритм правильный.
Мейнтаненс: Это можно легко проверить, проверив инвариант после каждой итерации.В этом случае он удовлетворен.
прекращение: это шаг, на котором мы докажем правильность алгоритм.
когда цикл завершается, то значение j=n+1. Снова выполняется инвариант цикла.Это означает, что Подрешетка[от 1 до n] должна быть отсортирована.
Это то, что мы хотим сделать с нашим алгоритмом.Таким образом, наш алгоритм верен.
помимо всех хороших ответов, я думаю, отличный пример из Как думать об алгоритмах, Джефф Эдмондс может проиллюстрировать концепцию очень хорошо:
пример 1.2.1 «алгоритм двух пальцев Find-Max»
1) Технические характеристики: входной экземпляр состоит из списка L (1..n) элементы. Выход состоит из индекса i такого, что L (i) имеет максимум значение. Если есть несколько записей с этим же значением, то любые один из них возвращается.
2) основные шаги: вы принимаете решение о методе двух пальцев. На пальце правой руки пробегает по списку.
3) мера прогресса: мера прогресса, как далеко вдоль список ваш правый палец.
4) Инвариант Цикла: инвариант петли заявляет, что ваш левый палец указывает на одну из самых больших записей, встреченных до сих пор вашим правый палец.
5) Основные шаги: каждая итерация, ты двигаешь правым пальцем вниз. запись в списке. Если ваш правый палец теперь указывает на запись это больше, чем вход левого пальца, а затем переместите левый палец, чтобы быть с правым пальцем.
6) прогресс: вы делаете прогресс, потому что ваш правый палец движется одна запись.
7) Поддерживать Инвариант Цикла: вы знаете, что инвариант цикла сохраняется следующим образом. Для каждого шага новый элемент левого пальца есть Max (старый элемент левого пальца, новый элемент). По инварианту цикла, это Max (Max (shorter list), новый элемент). Математически, это Макс(длинный список).
8) установление инварианта цикла: вы изначально устанавливаете инвариант петли, указывая обоими пальцами на первый элемент.
9) условие выхода: вы сделаны когда ваш правый палец заканчивал просматриваю список.
10) конец: в конце концов, мы знаем задача решается следующим образом. От при условии выхода, ваш правый палец столкнулся со всеми вступления. По инварианту петли ваш левый палец указывает на максимум из этих. Верните эту запись.
11) прекращение и продолжительность: требуемое время некоторая константа умножьте длину списка.
12) особые случаи: проверьте, что происходит, когда есть несколько записей с тем же значением, или, когда n = 0 или N = 1.
14) формальное доказательство правильности алгоритма вытекает из вышеупомянутые шаги.
следует отметить, что инвариант цикла может помочь в разработке итерационных алгоритмов при рассмотрении утверждения, которое выражает важные отношения между переменными, которые должны быть истинными в начале каждой итерации и когда цикл завершается. Если это так, то расчет находится на пути к эффективности. Если false, то алгоритм не удалось.
инвариант в этом случае означает условие, которое должно быть истинным в определенной точке каждой итерации цикла.
в контрактном программировании инвариантом является условие, которое должно быть истинным (по контракту) до и после вызова любого открытого метода.
значение инварианта никогда не меняется
здесь инвариант цикла означает » изменение, которое происходит с переменной в цикле (инкремент или декремент), не изменяет условие цикла i.e условие удовлетворяет » так, что пришло инвариантное понятие цикла
трудно отслеживать, что происходит с петель. Циклы, которые не заканчиваются или заканчиваются без достижения их поведения цели, являются общей проблемой в компьютерном программировании. Помогают инварианты цикла. Инвариант цикла-это формальное утверждение о взаимосвязи между переменными в вашей программе, которое выполняется непосредственно перед запуском цикла (установление инварианта) и снова выполняется в нижней части цикла, каждый раз через цикл (поддержание инварианта). Вот общий шаблон использования инвариантов цикла в вашем коде:
. // инвариант цикла должен быть истинным здесь
while (условие тестирования ) <
// top of the loop
.
// нижняя часть петли
// инвариант цикла должен быть истинным здесь
>
// Завершение + Инвариант Цикла = Цель
.
Между верхней и нижней частью петли, прогресс предположительно делается к достижению петли цель. Это может нарушить (сделать ложным) инвариант. Точка инвариантов цикла-это обещание, что инвариант будет восстановлен перед повторением тела цикла каждый раз. В этом есть два преимущества:
работа не переносится на следующий проход сложными, зависящими от данных способами. Каждый проход через петлю независим от всех других, с инвариантом, служащим для связывания проходов вместе в рабочее целое. Рассуждение о том, что ваш цикл работает, сводится к рассуждению что инвариант цикла восстанавливается с каждым проходом через цикл. Это разбивает сложное общее поведение цикла на небольшие простые шаги, каждый из которых можно рассматривать отдельно. Тестовое условие цикла не является частью инварианта. Это то, что заставляет цикл завершаться. Вы рассматриваете отдельно две вещи: почему цикл должен когда-либо завершаться и почему цикл достигает своей цели, когда он завершается. Цикл завершится, если каждый раз через цикл вы приближаетесь к удовлетворяющ условие прекращения. Часто это легко гарантировать: например, шагая переменную счетчика по одному, пока она не достигнет фиксированного верхнего предела. Иногда причина прекращения сложнее.
инвариант цикла должен быть создан таким образом, чтобы при достижении условия окончания и истинности инварианта была достигнута цель:
инвариант + увольнение => цель
Требуется практика для создания инвариантов, которые просты и связаны которые охватывают все достижения цели, кроме прекращения. Лучше всего использовать математические символы для выражения инвариантов цикла, но когда это приводит к чрезмерно сложным ситуациям, мы полагаемся на ясную прозу и здравый смысл.
Извините, у меня нет разрешения на комментарий.
@Tomas Petricek, как вы упомянули
более слабый инвариант, который также истинен, заключается в том, что i >= 0 && i
Как это инвариант цикла?
свойство инварианта цикла является условием, которое выполняется для каждого шага выполнения циклов(т. е. для петли, а петли и т. д.)
Это важно для доказательства инварианта цикла, где можно показать, что алгоритм выполняется правильно, если на каждом шаге его выполнения это свойство инварианта цикла выполняется.
чтобы алгоритм был правильным, инвариант цикла должен иметь значение:
инициализации (the начало)
техническое обслуживание (каждый шаг)
прекращение (когда он закончил)
Это используется для оценки множества вещей, но лучшим примером являются жадные алгоритмы для обхода взвешенного графика. Чтобы жадный алгоритм дал оптимальное решение (путь по графу), он должен достичь соединения всех узлов в наименьшем возможном пути веса.
таким образом, свойство инварианта цикла состоит в том, что выбранный путь имеет наименьший вес. На начало мы не добавили ребер, поэтому это свойство true (в данном случае это не false). At каждый шаг, мы следуем за самым низким краем веса (жадный шаг), поэтому снова мы принимаем самый низкий путь веса. At конец, мы нашли самый низкий взвешенный путь, поэтому наше свойство также верно.
Если алгоритм этого не делает, мы можем доказать, что он не является оптимальным.
простыми словами, это условие цикла, которое истинно в каждой итерации цикла:
в этом мы можем сказать, что состояние i i =0
инвариант цикла-это утверждение, которое истинно до и после выполнения цикла.
в линейном поиске (согласно упражнению, приведенному в книге), нам нужно найти значение V в данном массиве.
его просто, как сканирование массива из 0
содержание: На следующей итерации V, не найденный в k-1, имеет значение true
Terminatation: Если V найдено в K позиции или k достигает длины массива, завершите цикл.