Zkouška Hric 8.2.2010

Pokračování přednášky TIN060 Algoritmy a datové struktury I
JT

Zkouška Hric 8.2.2010

Příspěvek od JT »

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.
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“