Инвариант цикла


Инвариант цикла — в программировании — логическое выражение, истинное после каждого прохода тела цикла (после выполнения фиксированного оператора) и перед началом выполнения цикла, зависящее от переменных, изменяющихся в теле цикла. Инварианты используются в теории верификации программ для доказательства правильности результата, полученного циклическим алгоритмом.

Определение

Инвариант цикла представляет собой математическое выражение (обычно — равенство), в которое неустранимым образом входят по крайней мере некоторые переменные, значения которых изменяются от одного прохода цикла до другого. Инвариант строится таким образом, чтобы быть истинным непосредственно перед началом выполнения цикла (перед входом в первую итерацию) и после каждой его итерации. Причём если в инвариант входят переменные, определённые только внутри цикла (например, счётчик цикла for в Паскале или Аде), то для входа в цикл они учитываются с теми значениями, которые получат в момент инициализации.

Доказательство корректности цикла с применением инварианта

Порядок доказательства работоспособности цикла с помощью инварианта сводится к следующему:

  • Доказывается, что выражение инварианта истинно перед началом цикла.
  • Доказывается, что выражение инварианта сохраняет свою истинность после выполнения тела цикла; таким образом, по индукции, доказывается, что по завершении всего цикла инвариант будет выполняться.
  • Доказывается, что при истинности инварианта после завершения цикла переменные примут именно те значения, которые требуется получить (это элементарно определяется из выражения инварианта и известных конечных значениях переменных, на которых основывается условие завершения цикла).
  • Доказывается (возможно — без применения инварианта), что цикл завершится, то есть условие завершения рано или поздно будет выполнено.
  • Истинность утверждений, доказанных на предыдущих этапах, однозначно свидетельствует о том, что цикл выполнится за конечное время и даст желаемый результат.
  • Также инварианты используют при проектировании и оптимизации циклических алгоритмов. Например, чтобы убедиться, что оптимизированный цикл остался корректным, достаточно доказать, что инвариант цикла не нарушен и условие завершения цикла достижимо.


    Похожие новости:

    Число отрезков (теория узлов)

    Число отрезков (теория узлов)
    В теории узлов число отрезков — это инвариант узла, определяющий наименьшее число прямых «отрезков», которые, соединяя конец к концу, образуют узел. Конкретнее, для любого узла K число отрезков K,

    Перребиянки

    Перребиянки
    «Перребиянки» — трагедия древнегреческого драматурга Эсхила на сюжет, взятый из фессалийского мифологического цикла. Её текст почти полностью утрачен. Сюжет Перребиянки — жительницы региона в

    Цикл Тринклера

    Цикл Тринклера
    Цикл Тринклера (англ. Seiliger cycle, англ. Sabathe cycle) — термодинамический цикл, описывающий рабочий процесс дизельного двигателя со смешанным сгоранием. Объединяет в себе цикл Отто и цикл

    Гигиена и кормление крупного рогатого скота (часть 2)

    Гигиена и кормление крупного рогатого скота (часть 2)
    Наиболее распространенными и желательными типами кормления молочных коров являются полуконцентратный и малоконцентратный, так как при достаточном количестве и хорошем качестве сена, силоса и
    Комментариев пока еще нет. Вы можете стать первым!

    Добавить комментарий!

    Ваше Имя:
    Ваш E-Mail:
    Введите два слова, показанных на изображении: *
    Популярные статьи
    Почему ремонт общественных зданий важен для эффективной эксплуатации
    Почему ремонт общественных зданий важен для эффективной эксплуатации
    Зачем ремонтировать общественные здания? Этот вопрос волнует многих, ведь общественные здания – это...
    Охранное предприятие в Москве – защита и надежность
    Охранное предприятие в Москве – защита и надежность
    В современном мире, где угрозы личной безопасности и сохранности имущества становятся все более...
    Особенности выбора мебели: секреты правильного подбора для интерьера
    Особенности выбора мебели: секреты правильного подбора для интерьера
    При обустройстве интерьера дома или офиса одним из самых важных аспектов является выбор мебели....
    Все новости