# Zkouska Mares 20.12. 17:00

<{ForumPost(poster="Kajinek", timestamp=2007-12-20 22:46:50)}>
Tak druhy predtermin u MJ od 17:00.   
  
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:)
<{/ForumPost}>

<{ForumPost(poster="hardwire2", timestamp=2008-01-05 20:11:54)}>

 > Kajinek wrote: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.

Zkusmo sem si to doma spočítal a vyšlo mi to tak, jak píšeš.  
Ta matice zas tak silena neni, jen je velka :)
<{/ForumPost}>

<{ForumPost(poster="Wolda", timestamp=2008-01-19 12:19:20)}>

 > hardwire2 wrote:
 >  > Kajinek wrote: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.
 > 
 > Zkusmo sem si to doma spočítal a vyšlo mi to tak, jak píšeš.  
 > Ta matice zas tak silena neni, jen je velka :)

A hlavne se to da spocitat i bez ni :-)
<{/ForumPost}>