Zkouška - Martin Mareš - 4. 1. 2008

[Chjoodge]

Zadání:

1) 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.

2) 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é.

3) Měli jsme navrhnout algoritmus, který dostane přirozená čísla x₁, ..., x_n 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ě...

[Wolda]

Dodam jen, ze u 3 se mel vymyslet algoritmus v P(n, K) a pak bylo jeste 3*) zda to jde ci nejde v P(n).