# Skúška 13.1

<{ForumPost(poster="Caparzzo", timestamp=2006-01-13 16:46:38)}>
Tak čo povedať...Možno som mal zase raz šťastie, že sa mi podarilo opísať čo to, takže aj keď binárne sčítanie, predsa len úspešne...Hoci piatok trinásteho, všimol som si, že dosť ľudí prešlo zo známkou v indexe, resp. na jeho papieri, keďže niektorí nemali zápočet...Tak veľa zdaru šetkým...
<{/ForumPost}>

<{ForumPost(poster="Tuetschek", timestamp=2006-01-13 18:14:25)}>
No... binarni scitani pry dost hnusny... nekolikrat pry skoncilo vyhozenim (nebyl jsem primym svedkem)... ja nastesti dostal Dinice :).  
Jsem tam byl ted asi od 3... vypadalo to ze to tam bude az do (pozdniho) vecera... stravil jsem tam asi hodinu, z toho vic jak 3/4 jsem sedel a psal... pak prosel jen jeden z mych 3 papiru a zeptal se me na 2 dost nepravdepodobny veci... mou nesouvisle koktavou, ale vicemene spravnou odpoved vzal OK a nechal me projit :D.  
Vypada to ze si chce overit jestli tomu clovek fakt ale fakt rozumi... takze se me ptal kolikrat max. se muze hrana vyhodit (rezerva := 0) a vratit zpet do rezidualniho grafu, taky jak se najdou hrany ktery lezi na nejkr. ceste zdroj->cil ... tyhle otazky ale budou asi dost nepredikovatelny  :?
<{/ForumPost}>

<{ForumPost(poster="jaruch", timestamp=2006-01-13 20:33:13)}>
inak sa asi vykrystalizoval okruh otazok, toci furt dokola zhruba toto:  
Dinitz  
Goldberg  
Voronoi diagram  
RSA + (inverzny?) Fourier  
previest dva NP-uplne problemy + Fourier  
vyhladavanie v texte  
scitacka  
bitonicke triedenie  
... mozno mi este nieco uniklo  
  
Ja som dostal vyhladavanie v texte, napisal som mu Rabin-Karpa, Knuth-Morris-Pratta a Aha-Corasicka, zacal to citat, pri Rabin Karpovi som zabudol "mod p", tak sa ma k tomu snazil naviest nejak tak, ze "keby sme mali velke cisla, ako to napchame do pamate" a potom sa pytal, preco je lepsie mat to p vacsie a preco mensie, pri tom Knuthovi to chcel odo mna sformalizovat, ale ked tomu rozumiete, tak vas k tomu dokope... potom este chcel vediet preco je to O(n), ale to som nevedel odovodnit, tak za dva. Myslim, ze tato otazka sa celkom da.  
A kombinacia NP+FFT=>4 v indexe  
Tak vela stastia
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2006-01-17 12:37:23)}>
takze som dostal FFT a prevod jednej NP ulohy na druhu podal toho, co bolo na prednaske. som sa spyatl ci hociktorej na hociktoru a povedal, ze hej ale radsej si pozrite vsetky tri prevody. sa celkom daju niektore. ked nakreslite tie obrazky na prednaske a popisete co znamenaju a co vlastne riesi ktora NP uloha z tych dvoch a dokazete, preco je mozne tento prevod pouzit, tak snad by ste to mohli mat dobre ;)  
  
FFT som najprv napisal pre n = 4 aby bolo vidno konkretne co sa tam deje. sa ma spytal, ci by som to vedel spravit pre vseobecne n, takze som potreboval nanovo napisat tu sumu (je to aj v Algovison dole) a ked sa to rozdeli na sude a liche stlpce, som mal dokazat, ze po rozdeleni na 4 podmatice sa dve a dve rovnaju s tym, ze som mal povedat ktore dve sa rovnaju.   
 tam v zasade ide, aby sme predtym zadefinovali, ze ked robite kosinovu transformaciu, ze aky vektor dostanete a preco je konecny (odburate sumy a podobne...) a ze mate nejake omega, ktore umocnene na n sa rovna 1 a potom po vas bude chciet, aby ste teda dokazali, ze v tych dvoch podmaticiach v l - tom stlpci sa na pozicii i a i + n/2  tie dve hodnoty rovnaju... cize tam dosadite do tej sumy to i + n/2 a upravujete kym sa vam tam nevycleni e na 2pi.i.j.n/2 a to potom dokazete ze to je 1 a zvysok sa vam uz bude rovnat... aspon by sa mal. ak nie, pozrite si ako je vseobecne definovane omega pomocou e   
  
inak co tam mali carry-look-ahead tak vraj chcel dokaz toho, ze v tej scitacke je v kazdej vrstve n/2 hradiel... sa to myslim indukciou dokazuje.
<{/ForumPost}>

<{ForumPost(poster="lingvik", timestamp=2006-01-26 16:34:01)}>
Ta implikace je blbost. Pokud někdo povídá o FFT a neví ani, co je to ten divný znak omega, tak se potom není čemu divit. Převody mezi NP úlohami jsou jedny z jednodušších věcí (zvlášť když si člověk může vybrat). A pokud člověk danému problému rozumí, tak dokáže odpovídat na všetečné dotazy. Takže FFT + NP->NP za jedna po mírném ptaní. Algoritmy pochopte a potom se nebojte.
<{/ForumPost}>