zkouska 13.2. - Hric

[hannah]

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)

[Jakobicek]

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