Что такое инвариант?

Question

Слово, кажется, используется в нескольких контекстах. Лучшее, что я могу понять, это то, что они имеют в виду переменную, которая не может измениться. Разве это не то, для чего нужны константы / финалы (черт возьми, Java!)?

Answer 1

Инвариант является более «концептуальным», чем переменная. В общем, это свойство состояния программы, которое всегда верно. Говорят, что функция или метод, обеспечивающий выполнение инварианта, поддерживают инвариант.

Например, двоичное дерево поиска может иметь инвариант, что для каждого узла ключ левого дочернего узла меньше, чем собственный ключ узла. Правильно написанная функция вставки для этого дерева будет поддерживать этот инвариант.

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

Answer 2

Это условие, которое, как вы знаете, всегда является истинным в определенном месте вашей логики и может быть проверено при отладке, чтобы выяснить, что пошло не так.

Answer 3

Я обычно смотрю на них с точки зрения алгоритмов или структур.

Например, у вас может быть инвариант цикла, который можно утверждать - всегда true в начале или конце каждой итерации. То есть, если ваш цикл должен был обрабатывать набор объектов из одного стека в другой, вы могли бы сказать, что | stack1 | + | stack2 | = c, в верхней или нижней части цикла.

Если проверка инварианта не удалась, это означает, что что-то пошло не так. В этом примере это может означать, что вы забыли поместить обработанный элемент в окончательный стек и т. Д.

Answer 4

Магия Википедии: Инвариант (информатика)

В информатике, предикат, если это правда, останется верным в течение Конкретная последовательность операций, это называется (ин) инвариантным к этому последовательность.

Answer 5

Как говорится в этой строке:

В компьютерных науках предикат, который, если он истинен, будет оставаться верным в течение определенной последовательности операций, называется () инвариантным к этой последовательности.

Чтобы лучше понять эту надежду, этот пример в C ++ помогает.

Рассмотрим сценарий, в котором необходимо получить некоторые значения и получить их общее количество в переменной с именем count и добавить их в переменную с именем sum

.

Инвариант (опять же, это больше похоже на концепцию):

// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades

Код для вышеупомянутого будет что-то вроде этого,

int count=0;
double sum=0,x=0;
while (cin >> x) {
++count;
sum+=x;
}

Что делает вышеуказанный код?

1) Считывает ввод из cin и помещает их в x

2) После одного успешного чтения увеличиваем count и sum = sum + x

3) Повторите 1-2, пока чтение не остановится (т.е. ctrl + D)

Инвариант петли:

Инвариант должен быть True ВСЕГДА . Итак, изначально вы начинаете свой код только с этого

while(cin>>x){
  }

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

// we have read count grades so far, and

Как сохранить инвариант истинным?

Simple! счетчик приращений.

Так что ++count; будет хорошо! Теперь наш код становится примерно таким:

while(cin>>x){
 ++count; 
 }

Но

Даже сейчас наш инвариант (концепция, которая должна быть ИСТИНА) является ложным, потому что теперь мы не удовлетворили вторую часть нашего инварианта.

// sum is the sum of the first count grades

Так что же теперь делать?

Добавьте x к sum и сохраните его в sum (sum+=x) и в следующий раз cin>>x будет читать новое значение в x.

Теперь наш код становится примерно таким,

while(cin>>x){
 ++count; 
 sum+=x;
 }

Давайте проверим

Соответствует ли код нашему инварианту

// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades

код:

while(cin>>x){
 ++count; 
 sum+=x;
 }

Ах !. Теперь инвариант цикла - True всегда , и код работает нормально.

Приведенный выше пример был взят и изменен из книги Ускоренный C ++ Эндрю-Кенингом и Барбарой-E

Answer 6

То, что не меняется внутри блока кода

Answer 7

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

Answer 8

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

Answer 9

Инвариант ADT определяет отношения среди полей данных (переменные экземпляра) это всегда должно быть правдой до и после выполнение любого метода экземпляра.