Co je to invariant?
Výraz:
invariant
Význam:
invariant - je tvrzení, které platí před vykonáním i po vykonání každé iterace daného cyklu.
Stanovuje se zpravidla, když chceme dokazovat korektnost algoritmu, jehož součástí je cyklus. V takové situaci je potřeba určit invariant a dokázat jeho pravdivost, tím je dokázána konečnost výpočtu a efekt cyklu.
Například při řazení algoritmem insertion sort (česky řazení vkládáním) může invariantem být tvrzení, že na začátku iterace for cyklu obsahuje seřazované pole stejné prvky jako na začátku výpočtu, ale část tohoto pole je seřazená od nejmenšího po největší prvek.
Stanovuje se zpravidla, když chceme dokazovat korektnost algoritmu, jehož součástí je cyklus. V takové situaci je potřeba určit invariant a dokázat jeho pravdivost, tím je dokázána konečnost výpočtu a efekt cyklu.
Například při řazení algoritmem insertion sort (česky řazení vkládáním) může invariantem být tvrzení, že na začátku iterace for cyklu obsahuje seřazované pole stejné prvky jako na začátku výpočtu, ale část tohoto pole je seřazená od nejmenšího po největší prvek.