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

• Thesis title in Czech: Schönhageho-Strassenův algoritmus a jeho matematické pozadí
• Thesis title in English: Schönhage-Strassen algorithm and the mathematics behind it
• Key words: okruh|polynom|modulární aritmetika|Fourierova transformace
• English key words: ring|polynomial|modular arithmetic|Fourier transform
• Academic year of topic announcement: 2021/2022
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Logic (21-KLOG)
• Supervisor: doc. RNDr. Vítězslav Švejdar, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 08.03.2022
• Date of assignment: 08.03.2022
• Administrator's approval: not processed yet
• Confirmed by Study dept. on: 23.03.2022
• Date and time of defence: 05.09.2022 11:00
• Date of electronic submission: 31.07.2022
• Date of proceeded defence: 05.09.2022
• Submitted/finalized: committed by student and finalized
• Opponents: doc. Mgr. Radek Honzík, Ph.D.

Guidelines

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.

References

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