# Skuska Mares 20.12.2007 14:00

<{ForumPost(poster="matwej...", timestamp=2007-12-20 16:28:49)}>
Ahoj,  
tak tato skuska urcite nepatrila medzi tie lahke, Mares zadal kazdemu(bolo nas tam 10) inu ulohu... napr. ja som mal vymysliet prevod z 3Dmatch na SAT...  :shock:  Casu nam dal kolko sme chceli... niektori ludia tam este stale sedia... ked ste mali tu ulohu tak vam zadal este nieco co na prednaske bolo.. nejaku teoriu .. ja som dostal definiciu NP, NP tazky problem, NP uplny problem, def. prevoditelnosti. ...   
Nastastie som  sa nejak tym prikladom aj s jeho pomocou prehryzol a dal mi za 1.  8)
<{/ForumPost}>

<{ForumPost(poster="nardew", timestamp=2007-12-20 18:24:52)}>
ja som najprv dostal ulohu na toky: je dany graf, ktoreho kapacity su od 1 do 5 a mal som najst maximalny tok cez ktorykolvek algoritmus ktory som si vybral. k tomu algoritmu bolo treba klasicky popisat vsetko co bolo na prednaske ale explicitne chcel vyjadrenie jeho zlozitosti pre konkretny pripad s kapacitami od 1 do 5. to uz take lahke nebolo(teda aspon pre mna), nieco som vymyslel, ale nakoniec mi to aj tak napisal on, lebo videl ze moc uz neviem ako. potom mi dal este previest 3-sat na nezavislu mnozinu. suma sumarom, az na ten dokaz s tymi kapacitami som mal vsetko a tak som odchadzal s jednotkou :)
<{/ForumPost}>

<{ForumPost(poster="Osiris", timestamp=2007-12-20 21:29:42)}>
Já jsem měl zkonstruovat počítadlo slov v textu, který má lineární časovou složitost také vzhledem k počtu nalezených slov... Trochu jsem se na tom zamotal, neuměl jsem podat důkaz o tom, že můj algoritmus je lineární. Mareš řekl, že to mám mezi 1 a 2, tak jestli chci další otázku nebo 2 rovnou, radši jsem si vybral 2 :)
<{/ForumPost}>

<{ForumPost(poster="MateSC", timestamp=2007-12-21 00:43:01)}>
Ja jsem mel priklad na komparatorove site. Mam setridenou posloupnost n-1 prvku mam do ni zatridit n-ty prvek. A ukolem bylo najit obecny navod na to, jak vypada nejvice melka sit. To jest s nejmensim poctem hladin. Docela easy, i kdyz jsem se s tim trosku pachtil. Pak mi dal jeste ukazat, ze to nejde lepe nez (log n). S tim jsem se rady moc nevedel, kdyz za mnou prisel, tak jsem mu oznamil par postrehu, co jsem o tom zjistil, ale ve smes nic zajimaveho. Nakonec mi ukazal, jak se to da ukazat (pomoci grafu). Nasledne se me jeste zeptal, jakou hloubku bude mit komparatorova sit pro nesetridenou posloupnost. To jsem mu tam nakreslil obrazky z prednasky (o mergovani a bit. tridickach) a pak uz jsem jen spokojene odchazel s 1 :D  Myslim, ze zkouska u MJ neni z tech, na kterych se vyhazuje. Myslim, ze to da kazdy, kdo se na to alespon trochu podiva a vi wo co de  :D  Tak hodne stesti ostatnim.
<{/ForumPost}>