Dovada corectitudinii algoritmului folosind invarianți
Bună ziua! Puteți explica cum să demonstrați corectitudinea algoritmului folosind invarianți de buclă. Să presupunem o căutare liniară: in:A[], u //array, search element out:i //index of element u în tabloul A begin i=0; pentru j:=1 la lungime(a) face dacă A[j]=u atunci i:=j Sfârşit;
Un invariant este o expresie logică care este adevărată după fiecare trecere a corpului buclei (după execuția unei instrucțiuni fixe) și înainte de începerea buclei, în funcție de variabilele care se modifică în corpul buclei.[3]
Invarianții sunt utilizați în teoria verificării programelor pentru a demonstra corectitudinea execuției buclei. Procedura de demonstrare a operabilității ciclului cu ajutorul unui invariant este următoarea:
1.Se demonstrează că expresia invariantului este adevărată înainte de începerea ciclului. 2.Se demonstrează că expresia invariantului rămâne adevărată după executarea corpului ciclului; astfel, prin inductie, se demonstreaza ca la sfarsitul ciclului invariantul va fi indeplinit. 3. Se demonstreaza ca daca invariantul este adevarat, dupa terminarea ciclului, variabilele vor lua exact valorile. care trebuie obținute (aceasta se determină elementar din expresia invariantului și a variabilelor valorilor finale cunoscute pe care se bazează condiția de terminare a ciclului). 4.Se demonstrează (eventual fără aplicarea invariantului) că ciclul se va termina, adică condiția de terminare va fi îndeplinită mai devreme sau mai târziu. rezultatul dorit. Invarianții sunt utilizați și în proiectarea și optimizarea algoritmilor ciclici. De exemplu, pentru a vă asigura că bucla optimizată rămâne corectă, este suficient să demonstrați că invariantul buclei nu este încălcat și condițiafinalizarea ciclului este realizabilă.
Conceptul de invariant este folosit și în programarea orientată pe obiecte pentru a desemna o stare consistentă a unui obiect. Se înțelege că apelarea oricărei metode lasă obiectul într-o stare invariantă.