Инвариант.

[ИС]

Что такое инвариант? не смог найти что значит это слово =)
постоянно встречаеться в книге Шень "Программирование. Теоремы и задачи".
Расскажите что это такое или где об этом почитать.

[gris]

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

[Xaositect]

Инвариант цикла - это предикат, который выполняется на каждой итерации цикла.
Вот, например, возьмем такой цикл:

q = 0;
while (a >= b)
{
  a = a - b;
  q++;
}

Инвариантом будет $P(a,b,q) \equiv (a + qb = a_0)$ ($a_0$ - начальное значение переменной $a$)

Инварианты используются для доказательства того, что программа действительно делает то, что надо. В нашем случае поскольку инвариант выполняется на каждой итерации цикла, то после выхода из цикла будет $a + qb = a_0$ (инвариант) и $a<b$(условие выхода из цикла), т.е. $q$ - неполное частное и $a$ - остаток от деления $a_0$ на $b$.
До полного доказательства не хватает утверждения о том, что цикл обязательно завершится. В нашем случае если $a_0>0$, $b>0$, то цикл завершится, так как на каждой итерации значение $a$ уменьшается.

[ИС]

Пасибо ) вроде стало чуть чуть яснее.
А где можно почитать об этом по подробнее?

[Xaositect]

А я вот даже не знаю что посоветовать, все, что нашел - серьезные книги по верификации, начинают с логики Хоара, сложно это.
В Шене примеров много, почитайте - освоитесь.

[Maslov]

ИС в сообщении #254865 писал(а):

А где можно почитать об этом по подробнее?

Э.Дейкстра. Дисциплина программирования.
Д.Грис. Наука программирования.

[ИС]

Не дает скачивать ) просит ввести пароль

[Xaositect]

ИС в сообщении #255057 писал(а):

Не дает скачивать ) просит ввести пароль

Там на окошке ввода пароля загадка

Еще можете на http://gen.lib.rus.ec/ поискать

[ИС]

Блин! имя должно быть с большой буквы XD