# Zkouška  Hric 8.2.2010

<{ForumPost(poster="JT", timestamp=2010-02-08 16:16:01)}>
Písemková část:  4 otázky, prý aspoň 2,5 dobře.  
  
1) Spočítat FFT a inverzní FT nějakého čtyřsložkového vektoru. Skutečně přes FFT, tedy rekurzivně/dynamicky - přes Vandermondovu matici to (očividně) nestačilo. Inverzní se dělalo přirozeně přes inverzní matici.    
  
2a) Definovat výšku (nebo hloubku, nepamatuju si to slovo - prostě počet hladin) obvodu a velikost obvodu (tj. počet hradel).  
  
2b) Důkaz o třídící síti - končí na str. 30 tady: [http://mff.cz/data/ADS2.pdf](http://mff.cz/data/ADS2.pdf)  
  
3) Důkaz složitosti Aho-Corasickové. Napsal jsem důkaz složitosti interpretace strojem - a že důkazy složitostí alg.2, alg.3 případně napíšu u ústní části, ale že mi nepřijdou tak podstatné - stačilo to, ani se pak neptal.  
  
4a) Převést max. párování na toky v sítích.  
  
4b) složitosti tokových algoritmů na obecném grafu + složitosti na grafu typu z 4a.  
  
Přísnost hodnocení...no nevím. Měl jsem prve 15/20, u ústní jsem ještě něco opravil/doplnil, pak se ptal na aprox. algoritmus na Problém obchodního cestujícího - to jsem mu v pohodě řekl. Dostal jsem dvojku.
<{/ForumPost}>