PAR7

Question 1

Neprimy strom

Answer 1

kostra grafu s minimálním stupněm

Question 2

Eulerovská kružnice

Answer 2

Eulerovská kružnice grafu G je kružnice; která prochází každou hranou G právě jednou.

Question 3

Eulerovský graf

Answer 3

Graf G je eulerovský; má-li každý jeho uzel sudý stupeň.

Question 4

Eulerovský strom

Answer 4

Neorientovaný strom může být transformován na eulerovský; je-li každá jeho hrana nahrazena dvojicí anti-paralelních hran.

Question 5

Paralelni redukce

Answer 5

je dano vstupni pole X n hodnot x0; x1; …;xn-1 z mnoziny D a p procesoru : vypocti paralelne S=x0+x1+…+xn-1; kde + = binarni operace nad mnozinou D

Question 6

(add)Prefixovy soucet

Answer 6

Vstupy : a)pole X = x0; … ; xn-1 z mnoziny D b)asociativni binarni operator + v D Vystup: pole Y všech prefixu pole X: yi=x0+x1+…+xi

Question 7

(add)paralelni binarni scitacka s predikci prenosu

Answer 7

Vstup: 2 n-bitova binarni cisla X = xn-1 … x0 a Y = yn-1 … y0 Ukol: Vypocitat Z = zn-1…z0 = X+Y v log n krocich predpocitanim prenosovych bitu; Vystup : C = cn;…; c1; c0 kde vždy c0=0

Question 8

(add)segmentovany paralelni prefixovy soucet

Answer 8

vstup: pole rozdelene libovolne do segmentu ; Vystup: prefixove soucty uvnitr těchto segmentu izolovane