# zkouska 13.2. - Hric

<{ForumPost(poster="hannah", timestamp=2007-02-13 20:23:47)}>
Dnesni pisemka:  
1) pro vektor (2,3,1,3) spocitat FFT a inverzni FFT  
2) definovat hloubku a velikost hradlove site  
    indukci podle m dokazat, ze s(Sm)=(m/4)(log m)(log(m) - 1)+m-1  
    muzete pouzit s(Mm)=m log(m) + 1  
3)dokazat, ze interpret vyhledavaciho stroje pri pouziti Aho-Corasickove          metody pracuje v case O(n)  
4) a)jak lze pouzit algoritmus hledani max toku pro ulohu nalezeni max parovani v bipartitnim grafu   
b)napiste slozitost ruznych algoritmu pro hledani max toku pro obecny graf a pro graf z a)
<{/ForumPost}>

<{ForumPost(poster="Jakobicek", timestamp=2007-02-14 00:39:12)}>
bilance byla myslim velmi dobra  
pred ustni vyhodil dva kvuli nedostatku bodu/tentokrat zadani neobsahovalo zadne vetsi zaludnosti typu vrstevnatych siti/  
u ustni byl hric dnes v pohode  
ja jsem dostal prevod CNF---klika  
stacilo mu vysvetleni prevodu spolu s urcitym vagnim naznakem korektnosti a polynomialnosti prevodu--- mira tolerance nepresnosti asi stale castecne zavisi na pisemce  
pta se ale zjevne temer na vsechno vcetne konvexnich obalu, scitacek :?  a aproximacnich algoritmu/subset sum, obch. cestujici, vrch. pokryti/  u ustni je jako vzdy potreba i trochu stesti aby clovek nedostal neco o cem nevi vubec nic... i kdyz muzete otazku odmitnout a dostanete jinou--- jen jednou .)
<{/ForumPost}>