Úloha 1 (Enumerace): Jak vypadají všechny booleovské funkce dvou proměnných s jedním bitem výstupu?

Úloha 2 (Úplnost): Dokažte, že každou booleovskou funkci dvou proměnných lze vyjádřit pomocí hradel and, or a not. Proto lze každý booleovský obvod s nejvýše dvouvstupovými hradly upravit tak, aby používal pouze tyto tři typy hradel. Jeho hloubka přitom vzroste pouze konstanta-krát.

Úloha 3 (Minimalismus): A co pomocí nějaké dvojice z hradel and, or a not? Nebo dokonce jen pomocí jednoho z nich? Rozeberte všechny podmnožiny těchto tří hradel a určete (konstrukce nebo důkaz neexistence), jestli pomocí ní lze vyjádřit všechny funkce. Pokud s žádnou jednoprvkovou podmnožinou neuspějete, jde použít nějaké jiné hradlo?

Úloha 4 (Třídění vkládáním): Jak by vypadala komparátorová síť pro třídění vkládáním? Jak se bude její průběh výpočtu lišit od paralelního bublinkového třídění?

Úloha 5 (Maximum): Navrhněte komparátorovou síť, která dostane-li $n$ prvků a vydá takovou permutaci, v níž bude poslední hodnota největší.

Úloha 6 (Zatřízení): Sestrojte komparátorovou síť, která dostane $(n-1)$-prvkovou setříděnou posloupnost a jeden prvek navíc, vydá setříděnou permutaci.

Úloha 7 (Nula-jedničkový princip): Dokažte, že když komparátorová síť třídí všechny vstupy, ji postačí otestovat na všech posloupnostech nul a jedniček.

Úloha 8 (Batcherovo třídění): Stejné složitosti paralelního třídění lze také dosáhnout následujícím rekurzivním algoritmem pro slévání setříděných posloupností:

Bmerge:

1. Vstup: Setřízené posloupnosti $(x_0, \dots, x_{n-1}), (y_0, \dots, y_{n-1})$
2. Je-li $n \leq 1$, vyřešíme triviálně.
3. $(a_0, \dots, a_{n-1}) \gets$ BMerge$((x_0, x_2, \dots, x_{n-2}), (y_0, y_2, \dots, y_{n-2}))$
4. $(b_0, \dots, \,b_{n-1}) \gets$ BMerge$((x_1, x_3, \dots, x_{n-1}), (y_1, y_3, \dots, y_{n-1}))$
5. Výstup: $(a_0, \min(a_1, b_0), \max(a_1, b_0), \min(a_2, b_1), \max(a_2, b_1), \dots, b_{n-1}) \hskip -1cm$

Pomocí předchozího cvičení dokažte, že tato procedura funguje. Zapište tento algoritmus ve formě třídicí sítě.