Skuska 23.01.2006

Zadanie bolo:

1. Zkonstruujte tridici sit S8 (sit sirky 8 realizujici paralelni Merge-Sort). Staci popis obrazkem ovsem vcetne odvozeni, tj. popisu mensich siti ze kterych se S8 sklada (rekurzivne od trivialni siti sirky dve). Spocitejte velikost a hloubku zkonstruovane site.

2. Mejme dan seznam n po dvou ruznych komplexnich cisel z0, z1, ... zn-1. Navrhnete algoritmus, ktery v case O(nlog^2 n) spocita koeficienty polynomu P(x) s mezi stupne n, ktery nabyva nulove hodnoty prave na z0, z1, ... zn-1.

3. Predpokladejte, ze mate "cernou skrinku", ktera umi resit problem SAT (rozhodnout o Booleovske formule zadane v KNF) v polynomialnim case. Navrhnete algoritmus, ktery za pomoci teto "cerne skrinky" nalezne pro libovolnou splnitelnou KNF v polynomialnim case pravdivostni ohodnoceni promennych,ktere danou KNF splnuje.

mohl by nekdo kdo vyresil 2 sem pastnout reseni?

qk wrote:mohl by nekdo kdo vyresil 2 sem pastnout reseni?

No tak neviem, mne to vychadza na polynom (x-z0).(x-z1)...(x-zn-1), tzn. ide o to, nejak efektivne medzi sebou vynasobit tie zatvorky... A snad nebudem daleko od pravdy, ak poviem, ze sa na to pouzije FFT :lol:
No ale nebol som tam dneska (miesto toho som sa snazil dostat zapocet :P), takze toto je len moj tip, co mi napadol po precitani zadania...

a jak vypada ustni cast? a je az dalsi den nebo hned po pisemce? (kdyz je vic jak 7 lidi..)

Ustna cast je tak ako minuly semester zhruba 2-3 hodiny po skonceni pisomnej... staci 2 body(potom je sanca nas 1 celkom realna). Asi pripustia aj s 1.5 bodom ale lepsie ako 3 potom necakajte:( Osobne si myslim ze je jedno co dostanes, lebo ta skuska je dost ostra a casovo narocna... Bol som dnes a som rad, ze si to uz nemusim zopakovat:)

Isidor wrote:

qk wrote:mohl by nekdo kdo vyresil 2 sem pastnout reseni?

No tak neviem, mne to vychadza na polynom (x-z0).(x-z1)...(x-zn-1), tzn. ide o to, nejak efektivne medzi sebou vynasobit tie zatvorky... A snad nebudem daleko od pravdy, ak poviem, ze sa na to pouzije FFT :lol:
No ale nebol som tam dneska (miesto toho som sa snazil dostat zapocet :P), takze toto je len moj tip, co mi napadol po precitani zadania...

Asi tomu celkom nerozumiem, ale ak vynasobim tie zatvorky, tak mi tam vide x^n a to je uz polynom s medzou stupna n+1, nie?

A moze mat vobec polynom stupna n nulove hodnoty v n roznych bodoch? :oops:

Anonymous wrote:

Isidor wrote:

qk wrote:mohl by nekdo kdo vyresil 2 sem pastnout reseni?

No tak neviem, mne to vychadza na polynom (x-z0).(x-z1)...(x-zn-1), tzn. ide o to, nejak efektivne medzi sebou vynasobit tie zatvorky... A snad nebudem daleko od pravdy, ak poviem, ze sa na to pouzije FFT :lol:
No ale nebol som tam dneska (miesto toho som sa snazil dostat zapocet :P), takze toto je len moj tip, co mi napadol po precitani zadania...

Asi tomu celkom nerozumiem, ale ak vynasobim tie zatvorky, tak mi tam vide x^n a to je uz polynom s medzou stupna n+1, nie?

A moze mat vobec polynom stupna n (tym myslim s najvyssou mocninou x^(n-1)) nulove hodnoty v n roznych bodoch? :oops: