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