Počítačová algebra ZS 2026/2027

Kontakt

Domácí úkoly

1.10.2026

1. Napište program pro výpočet největšího společného dělitele v oboru Gaussovských celých čísel, a jeho běh ilustrujte na výpočtu největšího společného dělitele čísel 4 a 9+5i.

8.10.2026

2. Napište vlastní programy na násobení (dlouhých) celých čísel: porovnejte metody školského násobení pod sebou, Karatsuby a Toom-3. Na základě experimentu určete, které metody jsou nejvhodnější pro dané délky čísel. To jest, určete, od jaké délky se vyplatí používat (vaší implementaci) Karatsuby, od jaké Toom-3.

15.10.2026

3. Napište funkci, která znásobí číslo a délky 2n s číslem b délky 3n s využitím metody rozděl a panuj a rozdělením na úseky délky n (Toom-2.5); (na násobení čísel délky n pak použijte násobicí algoritmus dle svého uvážení)

22.10.2026

4. Je možné dělat rychlou Fourierovu transformaci pomocí dělení na "třetiny"? Jakou by to mělo asymptotickou složitost?

29.10.2026

5. Napište vlastní implementaci rychlého násobení polynomů

5.11.2026

6. Implementujte subrezultantovou PRS pro výpočet NSD(f,g), kde f,g jsou celočíselné polynomy jedné proměnné. (Můžete využít knihoven, které umí dělit polynomy se zbytkem.)

Seznam probraných témat

1.10.2026

1. Reprezentace čísel v počítači
2. Délka čísla v soustavě o základu B
3. Sčítání, odčítání, násobení a dělení pod sebou s časy O(n+m), O(n+m), O(mn), O(n(m-n+1)); převod do jiné báze
4. Rozšířený Euklidův algoritmus a jeho použití pro řešení soustavy kongruencí (Čínská zbytková věta); Garnerův a Lagrangeův algoritmus - zatím bez odhadu časové a paměťové složitosti
5. Reprezentace polynomu jedné proměnné (husté vs řídké reprezentace)

8.10.2026

1. Složitost rozšířeného Euklidova algoritmu
2. Složitost algoritmů pro Čínskou zbytkovou větu
3. Interpolace polynomů jako speciální případ ČVZ
4. Metoda rozděl a panuj:
   • Mistrovská metoda pro odhad časové složitosti
   • Karatsubův algoritmus pro násobení čísel
   • Algoritmy Toom-k pro násobení čísel

15.10.2026

1. Opakování: Zobecněná verze mistrovské metody i s důkazem
2. Násobení čísel pomocí metod Toom-k, odhad časové složitosti pomocí zobecněné mistrovské metody
3. Rychlé násobení matic: Strassenův a Winogradův algoritmus s odhadem časové složitosti, zavedení exponentu maticového násobení ω: nejmenšího čísla takového, že každé dvě matice n×n lze znásobit v čase O(n^ω+o(1))

22.10.2026

1. Rozdělení do bloků a využití blokových úprav pro výpočet inverzní matice a determinantu v čase O(n^ω+o(1)), kde ω označuje exponent maticového násobení.
2. Vandermondův determinant
3. n-té odmocniny z jednotky
4. Diskrétní Fourierova transformace (reprezentace polynomu stupně < n pomocí jeho hodnot v n bodech) a rychlá Fourierova transformace (algoritmus jak rychlou Fourierovu transformaci provést v čase O(nlog n), pokud ony body jsou právě všechny 2^k-té odmocniny z jednotky )

29.10.2026

1. Opakování rychlé Fourierovy transformace
2. Rychlé násobení a rychlé dělení polynomů

5.11.2026

1. Opakování mocninných řad a rychlého výpočtu prvních n členů inverzní mocninné řady
2. Rychlé dělení polynomů
3. Posloupnost polynomiálních zbytků PRS (aneb jak se zbavit zlomků, které vycházejí při počítání největšího společného dělitele dvou polynomů nad podílovým tělesem)
4. Ukázky kódu jednotlivých PRS v Sagemath
   1. Společné nastavení:
      
   2. Největší společný dělitel v podílovém tělese:
      
   3. Eukleidovská PRS:
      
   4. Redukovaná PRS:
      
5. Sylvestrova matice, rezultant a Sylvestrovo kritérium: dva polynomy jsou soudělné v podílovém tělese, právě tehdy když mají nulový rezultant.

Seznam doplňkových příkladů probíraných na cvičení

22.10.2026

1. Dokažte, že má-li těleso T primitivní n-tou odmocninu z jedné, tak součet n jedniček je v T invertibilní.
2. Víme, že výsledkem diskrétní Fourierovy transformace polynomu f nad ℤ₁₇ při využití primitivní čtvrté odmocniny 4 je vektor (2,0,2,0). Určete původní polynom.
3. Kolik primitivních n-tých odmocnin z jedné existuje v q-prvkovém tělese?
4. Kolik primitivních n-tých odmocnin z jedné existuje v ℤ_m?
5. Dokažte následující vlastnosti Eulerovy funkce φ(n):
   1. Je-li n sudé, tak φ(n)/n ≤ 1/2
   2. Pokud má n méně než 8 prvočíselných dělitelů, tak φ(n)/n > 1/6
   3. limsup φ(n)/n = 1
   4. liminf φ(n)/n = 0

5.11.2026

1. V oboru formálních mocninných řad R[[x]] spočtěte 1/f, pro mocninnou řadu f=e^x a f=sin x. (Existují vůbec?)
2. Označme t_i počet binárních stromů s n vrcholy, kde binární strom je definován rekurzivně: strom s nula vrcholy je prázdná množina, a strom s n+1 vrcholy se sestáva z kořene a levého stromu s k vrcholy, a pravého stromu s l vrcholy, kde n=k+l+1. Buď T formální mocninná řada ∑t_ixⁱ. Dokažte, že tato řada splňuje T = 1 + xT^2.
3. Vydělte se zbytkem (x⁸ - x⁶+x) a (2x⁵+x⁴ + x³ + x).
4. Dokažte, že pro těleso T je T[[x]] Gaussovský obor. (Nápověda: Pokud je konstantní člen nenulový, řada lze invertovat; takže existuje jediný maximální ideál.)
5. (Těžší příklad) Dokažte, že redukovaná posloupnost polynomiálních zbytků funguje, tj. že při jejím průběhu nevznikají žádné zlomky.
6. Je nějaký způsob jak rozumně definovat skládání formálních mocniných řad? Za jakých podmínek je složení dvou takových řad dobře definováno? Pro které f je dobře definována inverzní mocninná řada vůči skládání?, tj. pro která f existuje g taková, že f(g(x))=x = g(f(x))?

Literatura