Na zkousce nas bylo 20 a vsichni dostali stejne 3 priklady. Na vyreseni bylo "rozumne mnoho" casu, jakmile mel nekdo vetsi cast hotovou, tak k nemu MJ prisel a spolecne to probrali. V pripade nejasnosti jste jeste dostali cas si to promyslet (i nekolikrat
).Priklady:
1, DFT pro vektor (1,-1,1,-1,1,-1,1,-1).
Jen se vynasobi s tou silenou matici, vyjde tusim (0,0,0,0,8,0,0,0) - nejsem si jist pozici te osmicky.
2, Sestrojit hradlovou sit, ktera zjisti pro 2 n-bitova (binarni) cisla x a y zda je x mensi nez y.
Jde to udajne prevest na neco velmi podobneho binarnimu scitani (to jak se predpocitava prenos
). Kdyz tak prosim nekoho o doplneni, nemel jsem tohle kompletni.3, Prevest 3-sat na Nezavislou mnozinu
Delalo se na prednasce.
3* (nepovinne) - 3-sat -> Nezavisla mnozina, ale tak, aby kazdy vrchol vysledneho grafu mel stupen <= 4.
Jednoduse 3-sat prevedeme na 3,3-sat, tim eliminujeme moznost, aby z jednoho vrcholu vedly vice jak 4 hrany.
Tot vse, odchazel jsem asi po 2 hodinach (parkrat jsem si neco musel rozmyslet) s krasnou 1. Priklady 1 a 3 jsem mel vicemene bez chyb (jen par doplnujicich otazek), 2 jsem nevymyslel celou a kdyz videl, ze na to asi neprijdu, tak mi rekl, at zkusim vyresit 3*. Na tu jsem prisel po par minutach a nasledne jsem odkracel domu. Jinak cela zkouska probihala skutecne v prijemne atmosfere, vsichni co odchazeli prede mnou tak dostali za 1 nebo za 2 a zatim nevim o nikom, kdo by byl vyhozen. Docela me prekvapilo, ze MJ po nikom nechtel dukaz cehokoli, spise mu zalezelo na tom, jak danemu alogitmu rozumite.
Tak hodne stesti:)