Matfyz Wiki

pocitacova algebra

kesy at 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

jajo at 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.

oblacik at 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)

  2. dokazat, ze smolnych prvocisel je konecne mnoho