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

<{ForumPost(poster="Chjoodge", timestamp=2008-01-04 19:55:46)}>
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<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ě...
<{/ForumPost}>

<{ForumPost(poster="Wolda", timestamp=2008-01-05 17:12:29)}>
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).
<{/ForumPost}>