Teorie algoritmů:

Stabilita algoritmu

Stabilita algoritmu je jedním z klíčových konceptů teorie algoritmů i praktické informatiky. Obvykle se o ní hovoří ve dvou významech:

Numerická stabilita — vztahuje se k algoritmům pracujícím s reálnými čísly, zaokrouhlovacími chybami a postupným hromaděním numerických nepřesností (Higham, 2002).

Stabilita u třídicích algoritmů — vztahuje se k zachování relativního pořadí prvků se stejným klíčem (Cormen et al., 2022).

Tento článek se věnuje oběma významům, protože v odborné literatuře existují a používají se současně.

Numerická stabilita algoritmů

Numerická stabilita popisuje, jak algoritmus reaguje na malé změny vstupu (např. chyby měření) nebo na chyby způsobené omezenou přesností výpočtů v plovoucí řádové čárce.

Algoritmus je numericky stabilní, pokud malé změny ve vstupu nebo mezivýpočtech způsobují jen malé změny ve výstupu.

Pokud malé nepřesnosti způsobí neúměrně velké chyby, algoritmus je numericky nestabilní.

Příklady numerické nestability

Typickým příkladem nestability je výpočet diskriminantu u kvadratické rovnice:

$$ax^2 + bx + c = 0$$

Pokud je b² velmi blízko 4ac, dochází při odečítání dvou podobných hodnot k jevu zvanému catastrophic cancellation (Higham, 2002).

Stabilita algoritmů při třídění

Třídicí algoritmus je stabilní, pokud zachová relativní pořadí prvků se stejným klíčem.

Stabilní algoritmus po setřídění podle věku zachová pořadí Adam, Bára, zatímco nestabilní nikoliv.

Python příklad: ukázka stability třídění

V Pythonu je vestavěná funkce sorted() i metoda list.sort() stabilní, protože používají variantu Timsort (Tim Peters, 2002).

Ukázkový příklad


    data = [
        ("Adam", 20),
        ("Bára", 20),
        ("Cyril", 19),
        ("Dana", 21),
        ("Eliška", 20)
    ]

    # Třídění podle věku
    sorted_data = sorted(data, key=lambda x: x[1])

    print("Původní data:")
    for item in data:
        print(item)

    print("\nSetříděná data (stabilní třídění):")
    for item in sorted_data:
        print(item)

Interpretace výsledku

Python zachová původní pořadí položek se stejným klíčem (věk 20):

Původní pořadí 20letých: Adam → Bára → Eliška

Po třídění podle věku se pořadí nemění.

To dokazuje, že Python používá stabilní třídění.

Význam stability pro praxi

Pro numerické výpočty

Numerická stabilita je zásadní v:

simulacích fyziky,

výpočtech diferenciálních rovnic,

zpracování signálu,

počítačové grafice,

strojovém učení.

Nestabilní algoritmus může vést k výsledkům, které nesouvisí s realitou.

Pro třídění a databázové systémy

Stabilita třídění je klíčová tam, kde:

třídíme vícekrát za sebou podle různých klíčů (lexikografické třídění),

zpracováváme databázové záznamy,

pracujeme s víceokruhovými prioritami.

Například postupné třídění:

podle příjmení

následně podle jména

vyžaduje stabilní třídění, aby výsledky byly konzistentní (Cormen et al., 2022).

Stabilita algoritmů je zásadní vlastností, která ovlivňuje přesnost, spolehlivost a interpretovatelnost výsledků.

Je důležitá jak v numerických výpočtech, tak při praktických úlohách, jako je třídění rozsáhlých dat.

Python poskytuje dobře implementovanou stabilní metodu Timsort, která v praxi umožňuje bezpečné a deterministické pořadí při třídění.

Zdroje

CORMEN, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2022). Introduction to Algorithms. MIT Press.

KNUTH, D. E. (1998). The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley.

HIGHAM, N. J. (2002). Accuracy and Stability of Numerical Algorithms. SIAM.

Press, W. H., TEUKOLSKY, S. A., Vetterling, W. T., Flannery, B. P. (2007). Numerical Recipes: The Art of Scientific Computing. Cambridge University Press.

MCILROY, P. M. (1993). Optimistic Sorting and Information Theoretic Complexity. SODA.

GOLDBERG, D. (1991). What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys