zkouska 13.2. - Hric

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)

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

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