Schönhageho-Strassenův algoritmus a jeho matematické pozadí

• Název práce v češtině: Schönhageho-Strassenův algoritmus a jeho matematické pozadí
• Název v anglickém jazyce: Schönhage-Strassen algorithm and the mathematics behind it
• Klíčová slova: okruh|polynom|modulární aritmetika|Fourierova transformace
• Klíčová slova anglicky: ring|polynomial|modular arithmetic|Fourier transform
• Akademický rok vypsání: 2021/2022
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra logiky (21-KLOG)
• Vedoucí / školitel: doc. RNDr. Vítězslav Švejdar, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 08.03.2022
• Datum zadání: 08.03.2022
• Schválení administrátorem: zatím neschvalováno
• Datum potvrzení stud. oddělením: 23.03.2022
• Datum a čas obhajoby: 05.09.2022 11:00
• Datum odevzdání elektronické podoby: 31.07.2022
• Datum proběhlé obhajoby: 05.09.2022
• Odevzdaná/finalizovaná: odevzdaná studentem a finalizovaná
• Oponenti: doc. Mgr. Radek Honzík, Ph.D.

Zásady pro vypracování

Pro písemné násobení dvou čísel obvykle používáme tzv. školní algoritmus pro násobení: zadaná čísla zapíšeme jedno nad druhé tak, aby číslice nejnižšího řádu byly nad sebou, pod podtržítkem jsou doleva ubíhající řádky patřící k jednotlivým číslicím druhého čísla, pod dalším podtržítkem je součet těchto řádků. Pokud každé z násobených čísel má v zápisu n číslic, pak mezi dvěma podtržítky je mezi n² a n²+n číslic, z čehož plyne, že čas, který školní algoritmus potřebuje k vynásobení dvou n-ciferných čísel, je úměrný hodnotě n². Říká se také, že školní algoritmus pro násobení pracuje v kvadratickém čase. Ze základní školy známe také školní algoritmus pro sčítání. Ten má výhodnější algoritmickou klasifikaci, pracuje v lineárním čase. Čas nutný k nalezení součtu dvou n-ciferných čísel je úměrný hodnotě n, což souvisí s tím, že pod jedno podtržítko píšeme jediný řádek číslic, výsledný součet.

V případě sčítání není z hlediska teorie algoritmů co řešit, protože žádnou rozumnou klasifikaci časových nároků algoritmu přiznivější než lineární čas, dá se říci, neznáme. Školní algoritmus pro sčítání lze považovat za nejlepší možný. Avšak otázka, zda existují algoritmy pro násobení, které jsou lepší než školní algoritmus, má smysl a je důležitá jak z teoretického, tak praktického hlediska. Vynásobit dvě čísla, která mají v zápisu stovky nebo tisíce cifer, a mít součin přesně, může být důležité například v kryptografii. Občas se vyskytující představa, že s rychlým rozvojem počítačů úvahy o efektivnosti algoritmů ztrácejí význam, není správná. Při práci s velmi velkými čísly je důležitější mít dobrý algoritmus než mít rychlý počítač. Není proto překvapivé, že operace násobení byla v nedávných desetiletích předmětem výzkumu a že algoritmy časově úspornější než školní algoritmus byly objeveny. Jedním z nich je Schönhageho-Strassenův algoritmus objevený v roce 1971. Ten pracuje v čase n . log(n) . log(log(n)), což je podstatně příznivější odhad než n², a je na něm zajímavé to, že v jeho konstrukci se uplatňují netriviální matematické poznatky: vědomosti o okruzích a polynomech, čínská zbytková věta a zejména Fourieova transformace. I poté, co v tomto století byly publikovány ještě o něco rychlejší algoritmy, Schönhageho-Strassenův algoritmus zůstává jak důležitým objevem, tak vynálezem použitelným a používaným v počítačových technologiích.

Vypracujte vlastní popis Schönhageho-Strassenova algoritmu takový, aby byl položen důraz na matematické pozadí. Ke všem potřebným matematickým poznatkům pokud možno podejte čitelné důkazy. Fungování algoritmu ukažte na vhodně zvolených příkladech. Porovnejte různé popisy algoritmu vyskytující se v odborné literatuře. Pokuste se podat i nějaké informace k historii a vývoji této problematiky. Podejte i zdůvodnění časového odhadu n . log(n) . log(log(n)). Věnujte pozornost české terminologii, nepřijímejte nekriticky existující překlady z angličtiny.

Seznam odborné literatury

[AHU74] A. V. Aho, J. E. Hopcroft a J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
[DPV08] S. Dasgupta, C. H. Papadimitriou a U. V. Vazirani. Algorithms. McGraw-Hill, 2008.
[Pap94] C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.