# Skuska 23.01.2006

<{ForumPost(poster="Oscar", timestamp=2006-01-23 13:28:24)}>
**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(n*log*^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.
<{/ForumPost}>

<{ForumPost(poster="qk", timestamp=2006-01-23 15:35:53)}>
mohl by nekdo kdo vyresil 2 sem pastnout reseni?
<{/ForumPost}>

<{ForumPost(poster="Isidor", timestamp=2006-01-23 16:05:49)}>

 > 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...
<{/ForumPost}>

<{ForumPost(poster="panther", timestamp=2006-01-23 21:53:20)}>
a jak vypada ustni cast? a je az dalsi den nebo hned po pisemce? (kdyz je vic jak 7 lidi..)
<{/ForumPost}>

<{ForumPost(poster="qwyxyo", timestamp=2006-01-24 00:11:21)}>
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:)
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2006-02-03 17:21:39)}>

 > 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:
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2006-02-03 17:26:40)}>

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

<{/ForumPost}>