En licence de maths, j'ai un cours de python. J'ai commencé à regarder le cours et il y a une notion que j'ai du mal à comprendre: celle d'invariant de Boucle. Ce que je comprend:
Tu peux expliciter un peu ton problème ?
Car tu te mets à parler de très grands nombres, sans avoir précisé de quoi tu parlais avant…
Un invariant de boucle ne répond pas true, il n'est qu'une propriété, ce n'est pas un objet qui existe à proprement parler.
C'est une propriété qui est vraie à chaque itération de la boucle.
Et le variant de boucle est un machin (pas forcément représenté comme une variable si mes souvenirs sont bons) qui décroit jusqu'à atteindre 0, ce qui signifie alors que l'on va quitter la boucle.
Un invariant est une propriété ou une formule logique qui doit être vrai, à l'initialisation et à chaque itération de la boucle.
Il démontre qu'à l'initialisation ou après une itération, le programme est correcte. Peu importe le nombre d'itération ("de très grands nombres"), et c'est là son intérêt. La difficulté réside donc à le trouver
Un variant est une fonction:
entière,
positive
qui décroit strictement
Il vérifie que la boucle se termine: f(i)=0 => !B (non B, ou B est un booléen)
Exemple (en java, sans vérification d'un ide ): A un tableau de N entiers. Trouver le plus petit élément.
int i= 0 ; int x= A[0]; // en java, un tableau est indicé de 0 à longueur -1
while (i < N ) {
if ( A[i] < x )
x= A[i];
i= i + 1;
}
// variant= f(i)= N - i
// invariant: A=A(init) ET x est le plus petit de A[0 .. i] ET 0 <= i <= n
A= A(init) : convention pour dire que le tableau n'a pas changé (aucune affectation vers le tableau)
x est le plus petit de A[0 .. i] : vrai à l'initialisation car le plus petit de A[0..0] est lui même
i est compris entre 0 et n. On couvre donc tout le tableau. La borne supérieur est bien n inclus et non n-1, car l'invariant doit être vrai en sortie de boucle
Cordialement,
Patrice
- Edité par PatriceCoppens 7 décembre 2017 à 8:46:29
Question débutant: Invariant et variant de boucle
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique