Тапсырмалар № 19, 20, 21 · ЕГЭ

Инварианты в алгоритмах

Как сохраняющиеся свойства помогают доказывать правильность алгоритмов

3 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

Инвариант — это свойство или утверждение, которое остаётся истинным после каждого шага алгоритма. Инварианты помогают строго доказать, что алгоритм сохраняет правильность промежуточных результатов и в конце выдаёт верный ответ.

Инвариант алгоритма

Свойство, истинное перед началом выполнения, сохраняющееся после каждого допустимого шага алгоритма и позволяющее сделать вывод о результате после его завершения. Особенно часто инварианты используют при доказательстве корректности циклов.

Как доказывают инвариант

Для цикла обычно проверяют три условия. Инициализация: инвариант верен до первого шага цикла. Сохранение: если он верен перед очередной итерацией, то после неё тоже остаётся верным. Завершение: после остановки цикла инвариант вместе с условием завершения даёт требуемый результат. Такой подход является частью доказательства корректности алгоритмов из раздела продвинутых алгоритмов и вычислений.

\[I_0 \Rightarrow I_1 \Rightarrow I_2 \Rightarrow \dots \Rightarrow I_k\]1

Здесь \(I_i\) означает, что инвариант истиннен после \(i\) шагов. Формула показывает: если свойство верно в начале и каждый шаг его сохраняет, оно верно на всём протяжении выполнения.

№

Пример: поиск максимума

Алгоритм просматривает массив слева направо и хранит переменную \(m\). Инвариант: после обработки первых \(i\) элементов значение \(m\) равно максимуму среди этих элементов. Сначала \(m\) содержит первый элемент. На каждой итерации сравнение с новым элементом сохраняет инвариант. После обработки всего массива \(m\) — максимум всего массива.

Проверь себя

Какой шаг доказательства показывает, что инвариант не нарушается при переходе от одной итерации к следующей?

Не путайте с условием цикла

Условие продолжения цикла отвечает на вопрос, нужно ли выполнять следующую итерацию. Инвариант описывает то, что сохраняется независимо от количества уже выполненных итераций. Например, условие может быть \(i<n\), а инвариантом — «обработаны все элементы с индексами от \(0\) до \(i-1\)».

Инварианты применяются не только в циклах. В динамическом программировании можно поддерживать утверждение о том, что таблица уже содержит правильные ответы для решённых подзадач. В алгоритмах на числах инвариантом может быть сохранение общего делителя, как в алгоритме Евклида для поиска наибольшего общего делителя.

Главное за минуту

Главное

Инвариант — свойство, истинное до начала и после каждого шага алгоритма.
Для доказательства проверяют инициализацию, сохранение и завершение.
В конце инвариант вместе с условием остановки должен гарантировать правильный результат.