Matfyz Wiki
Zadání:
Goldbergův algoritmus - dostali jsme ho nejprve popsat, dokázat korektnost, pak popsat zvláštní chování pro síť s jednotkovými kapacitami, navrhnout pro takový případ implementaci a odvodit pro něj složitost.
Měli jsme sestavit síť komparátorů, která na vstupech 1, ..., n-1 dostane setřízenou rostoucí posloupnost a na vstupu n nějaké další číslo a za pomoci asymptoticky co nejmenšího množství vrstev komparátorů ono nové číslo zatřídí na správné místo tak, aby na výstupu byla setřízená posloupnost.
2*) Ve volném čase jsme mohli dokázat, že naše řešení příkladu (2) je asymptoticky nejlepší možné.
Měli jsme navrhnout algoritmus, který dostane přirozená čísla x<sub>1</sub>, ..., x<sub>n</sub> a přirozené číslo K a rozhodne, zda je možné čísla rozdělit do tří množin tak, aby součet v každé z nich byl menší nebo roven K.
Zkouška probíhala tak, jak lidé popisovali jiné zkoušky u MM - ten nejdřív vysvětlí zadání, pak člověk samostatně přemýšlí a když má nějaký ucelený kus vymyšlený (třeba jeden příklad), tak se ozve, MM přijde a daná věc se probere ústně. Času je víc než dost, dneska zkouška končila cca po třech a půl hodině...