PAR8

Question 1

radici sit (neprime)

Answer 1

Řadící síť’ = sít’ složená ze sloupců komparátorů (jako MIN).

Question 2

komparator (neprime)

Answer 2

HW implementace operace C&E (vzestupně; sestupně)

Question 3

Statická řadící sít’ (neprime)

Answer 3

HW implementace datově necitlivého řadícího alg.

Question 4

radici sit (prime)

Answer 4

C&E operace mezi dvojicí procesorů:

Question 5

primy radici alg

Answer 5

posloupnost dokonalých párování procesorů (perfect matchings) odvozených z jejich lineárního očíslování.

Question 6

Datově necitlivé řazení

Answer 6

způsob párování nezávisí na vstupních datech

Question 7

Triviální spodní mez na složitost C&E řazení

Answer 7

prumer grafu

Question 8

bitonicka posloupnost

Answer 8

posloupnost je bitonicka; pokud obsahuje prave 1 udoli a prave 1 vrchol nezavisle na rotaci udoli = prvek ktery je mensi nez oba jeho sousedi.

Question 9

razeni binarni posloupnosti

Answer 9

Jestliže datově necitlivý řadící algoritmus dokáže setřídit (seřadit) libovolnou binární vstupní posloupnost; pak dokáže setřídit libovolnou vstupní posloupnost.