Počítačová algebra LS 2018/19
Zkoušková témata
První otázka (formulace a důkaz správnosti algoritmu/věty)
10) Karacubův algoritmus pro násobení v Z
11) Toom-3 pro násobení v Z
12) Binární mocnění v Z
13) Eukleidův algoritmus v Z
14) Binární Eukleidův algoritmus v Z (v učebnici cvičení 18 na konci sekce 4)
15) Karacubův algoritmus pro násobení v R[x]
16) Hornerovo schéma pro vyhodnocení polynomu v bodě
17) Inverz v Q(q), kde q je algebraické komplexní číslo (známe-li minimální polynom q)
18) Lagrangeův algoritmus na převod z modulární reprezentace
19) Garnerův algoritmus na převod z modulární reprezentace
20) Naivní modulární násobení polynomů
21) Naivní modulární násobení v Z
22-25) Rychlá Fourierova transformace (FFT)
26) Násobení polynomů pomocí FFT, pokud máme primitivní 2^k-tou odmocninu z 1
27) Násobení v Z[x] přes FFT, pokud známe vhodné FFT-prvočíslo (vč. definice FFT prvočísel)
28) Modulární násobení v Z[x], kde počítáme modulo 2^(2^(k-1)u)+1
29) Dělení polynomů nad tělesem přes inverzní mocninné řady
30) Výpočet prvních n členů inverzní mocninné řady Newtonovou metodou
31) Aproximace čísla 1/a (s asymptoticky kvadratickou konvergencí)
32-35) Newtonova metoda pro f hladkou konvexní s kladnými derivacemi na intervalu [a,b], kde f(a)f(b)<0, konverguje kvadraticky
36) Pokud x_1, x_2, ... konvergují k u s řádem konvergence 2, najděte a dokažte horní odhad pro |x_i-u| pro i velké.
37) Výpočet NSD pro obecné polynomy nad gaussovským okruhem R pomocí PRS primitivních častí polynomů
38) Výpočet NSD pro primitivní polynomy nad gaussovským okruhem R pomocí euklidovské PRS
39) Výpočet NSD pro primitivní polynomy nad gaussovským okruhem R pomocí redukované PRS (v důkazu správnosti můžete vynechat to, co jsme vynechali na přednášce)
40) Důkaz, že obecná PRS umožňuje spočíst NSD primitivních polynomů nad gaussovským oborem. Co zhruba za druh objektů jsou subrezultanty a co zhruba říká fundamentální věta o PRS a jak z toho plyne správnost subrezultantového PRS algoritmu (stačí v rozsahu, jak to bylo na přednášce).
41) Definice rezultantu, formulace a důkaz Sylvesterova kritéria nesoudělnosti.
42) Definice rezultantu, formulace a důkaz tvrzení, zaručující existenci u,v, že uf+vg=res(f,g) (vč. podmínek na u,v a okruh R, nad kterým polynomy bereme)
43) Modulární výpočet NSD v Z[x] pomocí výpočtu ve vhodném Z_p[x]
44) Modulární výpočet NSD v Z[x] s použitím ČZV
45) Modulární algoritmus pro NSD polynomů z T[x,y], kde T je těleso (v rozsahu z přednášky, tj. bez řešení problému vedoucího koeficientu)
46) Vztah DFT a IDFT nad tělesem
47) Vztah DFT a IDFT v Z[x] modulo 2^(2^(k-1)u)+1
48) Čtyři ekvivalentní formulace soudělnosti polynomů nad gaussovským oborem R
49) Použitelná, šťastná a smolná prvočísla -- definice a význam (tj. co platí pro použitelná prvočísla a NSD počítaný v Z versus modulo p, proč jsou šťastná prvočísla dobrá pro výpočet NSD). Důkaz věty, že smolných prvočísel je jen konečně mnoho
Druhá otázka
(časová složitost algoritmu; očekává se, že algoritmus také zformulujete a že víte, jak se běžně složitost výpočetních algoritmů měří)10) Školské násobení v Z
11) Školské dělení se zbytkem v Z
12) Školský převod mezi bázemi (pro Z)
13) Karacubův algoritmus pro násobení v Z
14) Toom-3 pro násobení v Z
15) Naivní mocnění v Z
16) Binární mocnění v Z
17-21) Rozšířený Eukleidův algoritmus v Z (tj. včetně Bézoutových koeficientů)
22) Binární Eukleidův algoritmus v Z
23) Školské násobení v R[x]
24) Školské dělení v T[x] pro T těleso
25-26) Násobení v R[x] pomocí Karacubova algoritmu
27) Hornerovo schéma pro vyhodnocení polynomu v bodě
28) Sčítání v Q
29) Násobení v konečném tělese (máme zadaný generátor tělesa a jeho minimální polynom)
30) Inverz v Q(q), kde q je algebraické komplexní číslo (známe minimální polynom q)
31) Lagrangeův algoritmus na převod z modulární reprezentace
32) Garnerův algoritmus na převod z modulární reprezentace
33) Přidání jednoho nového interpolačního bodu, známe-li data z běhu Garnerova algoritmu
34) Modulární násobení polynomů bez použití FFT
35-39) Rychlá Fourierova transformace pro polynomy z T[x], máme-li vhodnou primitivní odmocninu z 1
40) Násobení polynomů pomocí FFT, pokud známe vhodnou primitivní
41) Násobení v Z[x] pomocí FFT, pokud známe vhodné FFT-prvočíslo
42) Násobení v Z[x], kde počítáme modulo 2^(2^(k-1)u)+1 pro vhodné u, k
43-46) Rychlé dělení polynomů nad tělesem, včetně výpočtu inverzní mocninné řady Newtonovou metodou.
47) Výpočet NSD pro náhodné polynomy stupně n, n-1 nad Z pomocí Euklidovské PRS (odhad složitosti stačí dělat zhruba podobně jako na přednášce)
48-49) Výpočet NSD pro (primitivní) polynomy nad Z pomocí redukované PRS, pokud víme, že délka koeficientů členů PRS roste lineárně