# pocitacova algebra

<{ForumPost(poster="kesy", timestamp=2008-05-29 15:29:33)}>
dnes som bol na skuske z pocitacovej algebry... mali sme byt dvaja, ale hubi ochorel, takze som tam bol sam. uplna romantika.  
stanovsky najprv meskal, vraj si myslel, ze to je az od 11.00 - takze si pre istotu skontrolujte, ci aj ostatne terminy neposunul na 11.00  
  
inak to vyzera presne tak, ako pisal - 3 ulohy. moje boli:  
1) res(f,g) = uf +vg aj s dokazom, sylvestrovo kriterium aj s dokazom  
2) spocitat zlozitost rychleho delenia polynomov nad Z_p so zvyskom v zavislosti na stupni a p  
3) rozlozit x^8-1 nad Z_3 pomocou berlekampa  
  
vo vseobecnosti plati, ze technicke detaily nie su dolezite, v 1) som napisal, ako sa ten dokaz robi, nie presne vyjadrenia a bolo to ok  
  
inak, tych 80 minut je len orientacnych, ak budete potrebovat viac casu, dostanete ho.  
  
potom sme si este pokecali o rezultantoch, NSD polynomov a smolnych prvocislach - takze sa to vsetko tocilo okolo rezultantov  
  
skuska to vlastne bola prijemna, ako inak
<{/ForumPost}>

<{ForumPost(poster="jajo", timestamp=2008-06-11 14:05:17)}>
caute  
bol som na termine 10.6. 2008  
  
otazky boli nasledovne:  
1. dokazat zlozitost algoritmu na NSD v celych cislach...cize zlozitost Euklidovho algoritmu v **Z**;  
2. algoritmus FFT s dokazom spravnosti;  
3. odsimulovat na zadanom priklade beh algoritmu:  
           bol zadany polynom zo Z\[x] (uz si nepamatam aky) a jeho rozklad v Z<sub>5</sub>\[x]. ulohou bolo simulovat poslednu fazu Berlekamp-Henselovho algoritmu, tj. kombinaciu faktorov.  
  
v tej 1. som nemusel dokazovat max. pocet krokov Euklid. alg., ale chcel tam dokaz Suma(l(q<sub>i</sub>)) = O(n)  
  
potom sa ma este pytal na FFT, chcel odo mna vysvetlit princip vyuzitia FFT pri rychlom nasobeni. ako sa obchadza problem v telese **Q**, kde nie su primitivne odmocniny.
<{/ForumPost}>

<{ForumPost(poster="oblacik", timestamp=2008-06-20 01:02:36)}>
Ahojte, pridavam zadanie zo 17.6.  
  
1) faktorizacia v F_q\[x,y]... sformulovat algoritmus a spocitat jeho zlozitost  
2a) rychle nasobenie (FFT) polynomov: (x^2+1)*(x^3-1), sformulovat algoritmus  
2b) kedze som mala FFT na zapoctaku, tak som dostala pozmenene zadanie a namiesto rychleho nasobenia, som mala rychle delenie polynomov:  
(x^4+1):(x^3-1)  
3) dokazat, ze smolnych prvocisel je konecne mnoho
<{/ForumPost}>