Skuska 23.01.2006

Oscar · Příspěvek od **Oscar** » 23. 1. 2006 13:28

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.

qk · Příspěvek od qk » 23. 1. 2006 15:35

mohl by nekdo kdo vyresil 2 sem pastnout reseni?

Isidor · Příspěvek od **Isidor** » 23. 1. 2006 16:05

qk píše: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

No ale nebol som tam dneska (miesto toho som sa snazil dostat zapocet

), takze toto je len moj tip, co mi napadol po precitani zadania...

panther · Příspěvek od **panther** » 23. 1. 2006 21:53

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

qwyxyo · Příspěvek od **qwyxyo** » 24. 1. 2006 00:11

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:)

Návštěvník · Příspěvek od **Návštěvník** » 3. 2. 2006 17:21

Isidor píše:
qk píše: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
No ale nebol som tam dneska (miesto toho som sa snazil dostat zapocet ), 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?

Návštěvník · Příspěvek od **Návštěvník** » 3. 2. 2006 17:26

Anonymous píše:
Isidor píše:
qk píše: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
No ale nebol som tam dneska (miesto toho som sa snazil dostat zapocet ), 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?