Algoritmus je korektní, pokud pro každý vstup dá v konečném množství kroků správný výsledek. Abychom toto dokázali, zavedeme dva pojmy – variant a invariant.

Variant a invariant

Variant je hodnota daná přirozeným číslem, která se v průběhu algoritmu stále snižuje, dokud nenabude hodnoty, při které algoritmus terminuje.

Invariant je naproti tomu tvrzení, které platí na počátku algoritmu (nebo po jeho prvním kroku), po provedení každého dalšího kroku a po terminaci algoritmu zaručuje správnost řešení.

Příklad

Mějme Euklidův algoritmus, který vypočte pro dvě přirozená čísla jejich největšího společného dělitele:

 /**
  * Vstup: Čísla a > 0, b > 0
  * Výstup: gcd(a, b)
  */
 function gcd(a, b)
     if a >= b then
         m = a
         n = b
     else
         m = b
         n = a
 
     while n != 0 do 
         m = p*n + z
         m = n
         n = z
 
     return m
 

Variantem je zbytek po dělení, který se v každém kroku algoritmu snižuje, když je nulový, algoritmus terminuje.

Invariantem je tvrzení, že dvojice čísel a mají stejné společné dělitele.

Toto tvrzení vychází z rovnosti:

Pokud nějaké číslo dělí , tak musí dělit i pravou stranu zmíněné rovnosti. Jelikož hledáme největšího společného dělitele a , tak je ze zadání zřejmé, že dělí i . Složíme-li obě tvrzení, tak je zřejmé, že musí dělit i druhého sčítance na pravé straně – číslo .

Literatura

• DEMLOVÁ, Marie. Teorie algoritmů : Text k přednášce.