Teorie algoritmů (obsah)

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 ...

Algoritmus je schematický postup pro řešení určitého druhu problémů, který je prováděn pomocí konečného množství přesně definovaných kroků. Ačkoliv se dnes tento pojem používá především v informatice a přírodních vědách obecně, tak je jeho působnost daleko širší (kuchyňské recepty, návody a postupy...). Samotné slovo algoritmus pochází ze jména perského matematika 9. století Abu Jafar Muhammada ibn Mūsā al-Chwārizmího, který ve svých dílech polož...