Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Třídící sítě

Zdrojem této sekce jsou zápisky z přednášek Prof. L. Kučery Algoritmy a datové struktury II.

Definice (Bitonická posloupnost)

Řekneme, že posloupnost prvků je bitonická, pokud po spojení do cyklu (tedy nultý prvek za -tý) obsahuje dva monotónní úseky. Nebo-li obsahuje až na fázový posuv dva monotónní úseky.

Definice (Komparátor)

Komparátor je speciální typ hradla (představme si pod tím nedělitelnou elektronickou součástku, případně jen virtuální), která má dva výstupy a dva vstupy. Pokud na vstupy přivedeme dva prvky (klíče, čísla), z levého výstupu vydá menší z nich a z pravého výstupu větší (takže vlastně porovná dva prvky a na výstup je vyplivne ve správném pořadí). Pracuje v konstantním čase.

Definice (Třídící síť)

Třídící síť je správně sestavená množina komparátorů dohromady spojená vstupy a výstupy tak, že při přivedení posloupnosti délky na vstup ji vydá setříděnou na výstupu. Komparátory v ní jsou rozčleněné do hladin, jejichž počet pak udává celkovou dobu výpočtu - předpokládá se tam, že komparátory v jednotlivých vrstvách pracují paralelně, takže třídící sítě mohou dosahovat časové složitosti pouhých . Algoritmus s takovou časovou složitostí sice existuje, ale má velmi vysokou multiplikativní konstantu, takže se v praxi nepoužívá. Příkladem třídící sítě je i bitonické třídění.

Algoritmus (Bitonické třídění)

Bitonická třídící síť je založena na použití bitonických posloupností a rekurze. Obvod (pro třídění dat délky ) se dělí na dvě části:

- První část setřídí (rekurzivně) vstupu vzestupně, druhou polovinu sestupně a tím vytvoří bitonickou posloupnost. Obsahuje tedy dvě třídící sítě pro třídění posloupností délky .
- Druhá část třídí jen bitonické posloupnosti - první její vrstva rozdělí bitonickou posloupnost na vstupu na dvě bitonické posloupnosti (z větších a menších čísel). Další vrstvy už jsou opět implementovány rekurzivně - tedy druhá vrstva dostane dvě posloupnosti a vyrobí z nich čtyři atd., až nakonec dojde k bitonickým posloupnostem délky 1.

K rozdělení jedné bitonické posloupnosti délky na dvě stačí jen komparátorů, které porovnávají vždy -tý a -tý prvek. Dojde sice k nějakému fázovému posuvu, ale to ničemu nevadí. Dobře je to vidět při znázornění na kružnici, doporučuji prohlédnout si postup v programu Algovision Prof. Kučery (`http://kam.mff.cuni.cz/~ludek/AlgovisionPage.html`).

Je vidět, že počet vrstev potřebných k dělení bitonických posloupností délky je ( ). Pro celkový počet vrstev, a tedy dobu zpracování - nám vychází následující vzorec

z čehož díky vzorci pro součet aritmetické posloupnosti vyjde