Qu'est-ce qu'un invariant?

Question

Le mot semble être utilisé dans plusieurs contextes. Le mieux que je puisse comprendre, c'est qu'ils signifient une variable qui ne peut pas changer. N’est-ce pas à cela que servent les constantes / finales (sacrément Java!)?

Answer 1

Un invariant est plus "conceptuel" qu'une variable. En général, c'est une propriété de l'état du programme qui est toujours vraie. Une fonction ou une méthode garantissant que l’invariant tient est dite pour maintenir l’invariant.

Par exemple, une arborescence de recherche binaire peut avoir l'invariant que pour chaque nœud, la clé de l'enfant gauche du nœud est inférieure à la clé propre du nœud. Une fonction d’insertion correctement écrite pour cet arbre maintiendra cet invariant.

Comme vous pouvez le constater, ce n’est pas le genre de chose que vous pouvez stocker dans une variable: c’est plus une déclaration à propos de du programme. En déterminant quel type d’invariants votre programme doit maintenir, puis en examinant votre code pour s’assurer qu’il les maintient effectivement, vous pouvez éviter les erreurs logiques dans votre code.

Answer 2

C’est une condition que vous savez être toujours vrai à un endroit particulier de votre logique et qui peut vérifier lors du débogage de déterminer ce qui ne va pas.

Answer 3

Je les considère généralement plus en termes d’algorithmes ou de structures.

Par exemple, vous pourriez avoir un invariant de boucle qui pourrait être affirmé - toujours vrai au début ou à la fin de chaque itération. En d’autres termes, si votre boucle était supposée traiter une collection d’objets d’une pile à l’autre, vous pourriez dire que | stack1 | + | stack2 | = c, en haut ou en bas de la boucle.

Si la vérification invariante échoue, cela signifie que quelque chose s'est mal passé. Dans cet exemple, cela pourrait signifier que vous avez oublié de placer l'élément traité dans la pile finale, etc.

Answer 4

La magie de wikipedia: Invariant (informatique)

  

En informatique, un prédicat qui,   si vrai, restera vrai tout au long d'un   séquence spécifique d'opérations, est   appelé (un) invariant à cette   séquence.

Answer 5

Comme l'indique cette ligne:

  

En informatique, un prédicat qui, s'il est vrai, restera vrai tout au long d'une séquence d'opérations spécifique, est appelé un invariant de cette séquence.

Pour mieux comprendre cet espoir, cet exemple en C ++ aide.

Prenons un scénario dans lequel vous devez obtenir des valeurs et en obtenir le nombre total dans une variable appelée count , puis les ajouter dans une variable appelée sum

l'invariant (encore une fois, il s'agit davantage d'un concept):

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

Le code pour ce qui précède serait quelque chose comme ceci,

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

À quoi sert le code ci-dessus?

1) Lit l'entrée de cin et la met dans x

2) Après une lecture réussie, incrémentez nombre et somme = somme + x

3) Répétez les étapes 1 à 2 jusqu'à ce que la lecture s'arrête (c.-à-d. ctrl + D)

Invariant de boucle:

L'invariant doit être True TOUJOURS . Donc, au début, vous commencez votre code avec juste ceci

while(cin>>x){
  }

Cette boucle lit les données de l’entrée standard et les stocke dans x. Bel et bien. Mais l'invariant devient faux car la première partie de notre invariant n'a pas été suivie (ou est restée vraie).

// we have read count grades so far, and

Comment garder l'invariant vrai?

Simple! nombre d'incréments.

Donc ++ count; ferait du bien !. Maintenant, notre code devient quelque chose comme ça,

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

Mais

Même maintenant, notre invariant (un concept qui doit être vrai) est Faux, car nous ne satisfaisons plus la deuxième partie de notre invariant.

// sum is the sum of the first count grades

Alors, que faire maintenant?

Ajoutez x à somme et stockez-le dans somme ( somme + = x ) et la prochaine fois. cin > > x lira une nouvelle valeur dans x.

Maintenant, notre code devient quelque chose comme ça,

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

Vérifions

Si le code correspond à notre invariant

<*>

code:

<*>

Ah !. Désormais, l'invariant de boucle est défini sur True toujours et le code fonctionne correctement.

L'exemple ci-dessus est repris et modifié à partir du livre C ++ accéléré par Andrew-koening et Barbara-E

Answer 6

Quelque chose qui ne change pas dans un bloc de code

Answer 7

Dans la continuité de ce qu’il est, les invariants sont très utiles pour écrire du code propre, car connaître conceptuellement quels invariants doivent être présents dans votre code vous permet de décider facilement comment organiser votre code pour les atteindre. objectifs. Comme mentionné plus tôt, ils sont également utiles pour le débogage, car vérifier si l'entretien de l'invariant est souvent un bon moyen de voir si la manipulation que vous essayez d'exécuter fait réellement ce que vous voulez.

Answer 8

Il s’agit généralement d’une quantité qui ne change pas sous certaines opérations mathématiques. Un exemple est un scalaire qui ne change pas en fonction des rotations. En imagerie par résonance magnétique, par exemple, il est utile de caractériser une propriété de tissu par un invariant en rotation, car son estimation ne dépend donc pas idéalement de l’orientation du corps dans le scanner.

Answer 9

L'invariant ADT spécifie des relations parmi les champs de données (variables d'instance) cela doit toujours être vrai avant et après l'exécution de toute méthode d'instance.