Je lis "Introduction à l'algorithme" par CLRS. Dans le chapitre 2, les auteurs mentionnent les "invariants de boucle". Qu'est-ce qu'une boucle invariante?
268
Je lis "Introduction à l'algorithme" par CLRS. Dans le chapitre 2, les auteurs mentionnent les "invariants de boucle". Qu'est-ce qu'une boucle invariante?
Réponses:
En termes simples, un invariant de boucle est un prédicat (condition) valable pour chaque itération de la boucle. Par exemple, regardons une
for
boucle simple qui ressemble à ceci:Dans cet exemple, il est vrai (pour chaque itération) que
i + j == 9
. Un invariant plus faible qui est également vrai est celai >= 0 && i <= 10
.la source
J'aime cette définition très simple: ( source )
En soi, un invariant de boucle ne fait pas grand-chose. Cependant, étant donné un invariant approprié, il peut être utilisé pour aider à prouver l'exactitude d'un algorithme. L'exemple simple dans CLRS a probablement à voir avec le tri. Par exemple, laissez votre boucle invariante être quelque chose comme, au début de la boucle, les premières
i
entrées de ce tableau sont triées. Si vous pouvez prouver qu'il s'agit bien d'un invariant de boucle (c'est-à-dire qu'il tient avant et après chaque itération de boucle), vous pouvez l'utiliser pour prouver l'exactitude d'un algorithme de tri: à la fin de la boucle, l'invariant de boucle est toujours satisfait et le compteuri
est la longueur du tableau. Par conséquent, les premièresi
entrées sont triées signifie que l'ensemble du tableau est trié.Un exemple encore plus simple: invariants de boucles, correction et dérivation de programme .
La façon dont je comprends un invariant de boucle est un outil formel systématique pour raisonner sur les programmes. Nous faisons une seule déclaration que nous nous concentrons à prouver vrai, et nous l'appelons l'invariant de boucle. Cela organise notre logique. Bien que nous puissions tout aussi bien argumenter de manière informelle sur l'exactitude de certains algorithmes, l'utilisation d'un invariant de boucle nous oblige à réfléchir très attentivement et garantit que notre raisonnement est hermétique.
la source
Il y a une chose que beaucoup de gens ne réalisent pas tout de suite lorsqu'ils traitent de boucles et d'invariants. Ils se confondent entre l'invariant de boucle et la boucle conditionnelle (la condition qui contrôle la fin de la boucle).
Comme les gens le soulignent, l'invariant de boucle doit être vrai
(bien que cela puisse être temporairement faux pendant le corps de la boucle). D'un autre côté, la boucle conditionnelle doit être fausse après la fin de la boucle, sinon la boucle ne se terminerait jamais.
Ainsi la boucle invariante et la boucle conditionnelle doivent être des conditions différentes.
Un bon exemple d'invariant de boucle complexe est pour la recherche binaire.
Ainsi, la boucle conditionnelle semble assez simple - lorsque start> end la boucle se termine. Mais pourquoi la boucle est-elle correcte? Quel est l'invariant de boucle qui prouve son exactitude?
L'invariant est l'énoncé logique:
Cette déclaration est une tautologie logique - elle est toujours vraie dans le contexte de la boucle / algorithme spécifique que nous essayons de prouver . Et il fournit des informations utiles sur l'exactitude de la boucle après sa fin.
Si nous revenons parce que nous avons trouvé l'élément dans le tableau, alors la déclaration est clairement vraie, car si
A[mid] == a
alors sea
trouve dans le tableau etmid
doit être entre le début et la fin. Et si la boucle se termine parce questart > end
alors il ne peut y avoir nombre tel questart <= mid
etmid <= end
par conséquent , nous savons que la déclarationA[mid] == a
doit être fausse. Cependant, par conséquent, l'énoncé logique global est toujours vrai dans le sens nul. (En logique, l'énoncé si (faux) alors (quelque chose) est toujours vrai.)Maintenant, qu'en est-il de ce que j'ai dit à propos de la boucle conditionnelle étant nécessairement fausse lorsque la boucle se termine? Il semble que lorsque l'élément est trouvé dans le tableau, la boucle conditionnelle est vraie lorsque la boucle se termine!? Ce n'est pas le cas, car la boucle implicite est vraiment conditionnelle,
while ( A[mid] != a && start <= end )
mais nous raccourcissons le test réel car la première partie est implicite. Cette condition est clairement fausse après la boucle, quelle que soit la façon dont la boucle se termine.la source
a
est présente dansA
. De manière informelle, ce serait "si la cléa
est présente dans le tableau, elle doit se produire entrestart
etend
inclus". Il s'ensuit alors que siA[start..end]
est vide, cea
n'est pas présent dans A.Les réponses précédentes ont très bien défini un invariant de boucle.
Voici comment les auteurs de CLRS ont utilisé l'invariant de boucle pour prouver l' exactitude du tri par insertion.
Algorithme de tri par insertion (comme indiqué dans le livre):
Boucle invariante dans ce cas: le sous-tableau [1 à j-1] est toujours trié.
Vérifions maintenant cela et prouvons que l'algorithme est correct.
Initialisation : Avant la première itération j = 2. Le sous-tableau [1: 1] est donc le tableau à tester. Comme il n'a qu'un seul élément, il est donc trié. L'invariant est donc satisfait.
Maintenance : Ceci peut être facilement vérifié en vérifiant l'invariant après chaque itération. Dans ce cas, il est satisfait.
Terminaison : C'est l'étape où nous prouverons l'exactitude de l'algorithme.
Lorsque la boucle se termine, la valeur de j = n + 1. L'invariant de boucle est à nouveau satisfait. Cela signifie que le sous-tableau [1 à n] doit être trié.
C'est ce que nous voulons faire avec notre algorithme. Notre algorithme est donc correct.
la source
En plus de toutes les bonnes réponses, je suppose qu'un excellent exemple de How to Think About Algorithms, de Jeff Edmonds, peut très bien illustrer le concept:
la source
Il convient de noter qu'un invariant de boucle peut aider à la conception d'algorithmes itératifs lorsqu'il est considéré comme une assertion qui exprime des relations importantes entre les variables qui doivent être vraies au début de chaque itération et lorsque la boucle se termine. Si tel est le cas, le calcul est sur la voie de l'efficacité. Si faux, l'algorithme a échoué.
la source
Invariant dans ce cas signifie une condition qui doit être vraie à un certain point dans chaque itération de boucle.
Dans la programmation sous contrat, un invariant est une condition qui doit être vraie (par contrat) avant et après l'appel de toute méthode publique.
la source
Le sens de l'invariant n'est jamais changé
Ici, l'invariant de boucle signifie "Le changement qui arrive à la variable dans la boucle (incrémenter ou décrémenter) ne change pas la condition de boucle, c'est-à-dire que la condition est satisfaisante", de sorte que le concept d'invariant de boucle est venu
la source
La propriété invariante de boucle est une condition qui s'applique à chaque étape de l'exécution d'une boucle (c'est-à-dire pour les boucles, tandis que les boucles, etc.)
Ceci est essentiel à une preuve invariante de boucle, où l'on est en mesure de montrer qu'un algorithme s'exécute correctement si à chaque étape de son exécution cette propriété invariante de boucle est respectée.
Pour qu'un algorithme soit correct, l'invariant de boucle doit tenir à:
Initialisation (le début)
Maintenance (chaque étape après)
Résiliation (lorsqu'elle est terminée)
Ceci est utilisé pour évaluer un tas de choses, mais le meilleur exemple est les algorithmes gourmands pour la traversée de graphe pondérée. Pour qu'un algorithme gourmand donne une solution optimale (un chemin à travers le graphique), il doit atteindre connecter tous les nœuds dans le chemin de poids le plus bas possible.
Ainsi, la propriété invariante de boucle est que le chemin emprunté a le moins de poids. Au début, nous n'avons ajouté aucun bord, donc cette propriété est vraie (ce n'est pas faux, dans ce cas). À chaque étape , nous suivons le bord de poids le plus bas (l'étape gourmande), donc encore une fois nous prenons le chemin de poids le plus bas. À la fin , nous avons trouvé le chemin pondéré le plus bas, donc notre propriété est également vraie.
Si un algorithme ne fait pas cela, nous pouvons prouver qu'il n'est pas optimal.
la source
Il est difficile de garder une trace de ce qui se passe avec les boucles. Les boucles qui ne se terminent pas ou ne se terminent pas sans atteindre leur comportement cible sont un problème courant en programmation informatique. Les invariants de boucle aident. Un invariant de boucle est une déclaration formelle sur la relation entre les variables de votre programme qui reste vraie juste avant l'exécution de la boucle (établissement de l'invariant) et qui se vérifie à nouveau au bas de la boucle, chaque fois à travers la boucle (maintien de l'invariant ). Voici le schéma général de l'utilisation des invariants de boucle dans votre code:
... // le Loop Invariant doit être vrai ici
tandis que (TEST CONDITION) {
// haut de la boucle
...
// bas de la boucle
// le Loop Invariant doit être vrai ici
}
// Termination + Loop Invariant = Objectif
...
Entre le haut et le bas de la boucle, des progrès sont probablement faits pour atteindre l'objectif de la boucle. Cela pourrait perturber (fausser) l'invariant. Le point des invariants de boucle est la promesse que l'invariant sera restauré avant de répéter le corps de boucle à chaque fois. Il y a deux avantages à cela:
Le travail n'est pas reporté à l'étape suivante de manière compliquée et dépendante des données. Chaque passage à travers la boucle est indépendant de tous les autres, l'invariant servant à lier les passes ensemble dans un tout fonctionnel. Le raisonnement selon lequel votre boucle fonctionne est réduit au raisonnement selon lequel l'invariant de la boucle est restauré à chaque passage dans la boucle. Cela brise le comportement global compliqué de la boucle en petites étapes simples, chacune pouvant être considérée séparément. La condition de test de la boucle ne fait pas partie de l'invariant. C'est ce qui fait que la boucle se termine. Vous considérez séparément deux choses: pourquoi la boucle doit-elle jamais se terminer et pourquoi la boucle atteint son objectif lorsqu'elle se termine. La boucle se terminera si, à chaque fois, vous vous rapprochez de la condition de terminaison. Il est souvent facile de le garantir: par exemple incrémenter une variable compteur d'une unité jusqu'à ce qu'elle atteigne une limite supérieure fixe. Parfois, le raisonnement derrière la résiliation est plus difficile.
L'invariant de boucle doit être créé de sorte que lorsque la condition de terminaison est atteinte et que l'invariant est vrai, le but est atteint:
invariant + terminaison => objectif
Il faut de la pratique pour créer des invariants simples et liés qui capturent tous les objectifs, à l'exception de la terminaison. Il est préférable d'utiliser des symboles mathématiques pour exprimer des invariants de boucle, mais lorsque cela conduit à des situations trop compliquées, nous nous appuyons sur une prose claire et du bon sens.
la source
Désolé, je n'ai pas la permission de commenter.
@Tomas Petricek comme vous l'avez mentionné
Comment est-ce une boucle invariante?
J'espère que je ne me trompe pas, pour autant que je sache [1] , l'invariant de boucle sera vrai au début de la boucle (initialisation), ce sera vrai avant et après chaque itération (maintenance) et ce sera aussi vrai après la fin de la boucle (terminaison) . Mais après la dernière itération, i devient 10. Ainsi, la condition i> = 0 && i <10 devient fausse et termine la boucle. Il viole la troisième propriété (terminaison) de l'invariant de boucle.
[1] http://www.win.tue.nl/~kbuchin/teaching/JBP030/notebooks/loop-invariants.html
la source
L'invariant de boucle est une formule mathématique telle que
(x=y+1)
. Dans cet exemple,x
ety
représentent deux variables dans une boucle. Compte tenu du changement de comportement de ces variables tout au long de l'exécution du code, il est presque impossible de tester tous les possiblex
et lesy
valeurs et voir si elles produisent tout bug. Disons quex
c'est un entier. Un entier peut contenir un espace de 32 bits dans la mémoire. Si ce nombre dépasse, un dépassement de tampon se produit. Nous devons donc être sûrs que tout au long de l'exécution du code, il ne dépasse jamais cet espace. pour cela, nous devons comprendre une formule générale qui montre la relation entre les variables. Après tout, nous essayons juste de comprendre le comportement du programme.la source
En termes simples, c'est une condition LOOP qui est vraie dans chaque itération de boucle:
En cela, nous pouvons dire que l'état de i est
i<10 and i>=0
la source
Un invariant de boucle est une assertion qui est vraie avant et après l'exécution de la boucle.
la source
Dans la recherche linéaire (selon l'exercice donné dans le livre), nous devons trouver la valeur V dans un tableau donné.
C'est aussi simple que de scanner le tableau à partir de 0 <= k <longueur et de comparer chaque élément. Si V est trouvé ou si le balayage atteint la longueur du tableau, il suffit de terminer la boucle.
Selon ma compréhension du problème ci-dessus-
Invariants de boucle (initialisation): V n'est pas trouvé dans l'itération k - 1. Très première itération, ce serait -1 donc on peut dire que V ne se trouve pas à la position -1
Maintien: dans la prochaine itération, V non trouvé en k-1 est vrai
Terminaison: si V trouvé en position k ou k atteint la longueur du réseau, terminer la boucle.
la source