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.
Skuska 23.01.2006
- Isidor
- Adoptoval Tutcheka
- Příspěvky: 247
- Registrován: 8. 12. 2004 23:22
- Typ studia: Informatika Mgr.
- Bydliště: mám
- Kontaktovat uživatele:
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 FFTqk píše:mohl by nekdo kdo vyresil 2 sem pastnout reseni?
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...
Inteligentních lidí je menšina. Demokracie je vláda většiny.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 51
- Registrován: 30. 5. 2005 19:26
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
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:)
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?Isidor píše: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 FFTqk píše:mohl by nekdo kdo vyresil 2 sem pastnout reseni?
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...
A moze mat vobec polynom stupna n nulove hodnoty v n roznych bodoch?
Anonymous píše: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?Isidor píše: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 FFTqk píše:mohl by nekdo kdo vyresil 2 sem pastnout reseni?
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...
A moze mat vobec polynom stupna n (tym myslim s najvyssou mocninou x^(n-1)) nulove hodnoty v n roznych bodoch?