35 - Distribuované a paralelní algoritmy - algoritmy vyhledávání
neděle 3. dubna 2016
21:12
Máme sekvenci 𝑋 = {𝑥1, 𝑥2, ..., 𝑥𝑛} a prvek 𝑥.
Máme za úkol zjistit, zda 𝑥 = 𝑥𝑘 a případně zjistit 𝑘.
[link]
Optimální sekvenční algoritmus pro vyhledávání
𝑿 není seřazená - sekvenční vyhledávání
tn=On, je potřeba prozkoumat n prvků.
𝑿 je seřazená - binární vyhledávání
tn=Olog𝑛
Tak mě ještě napadá  co Hash tables? Ty jsou konstantní ne?
Optimální složitost podle sekvenčního algoritmu je lineární (omikron n) pro neseřazenou posloupnost a (omikron log n) pro seřazenou. 
N-ary search
Vyhledává v seřazené posloupnosti.
Princip algoritmu
Při binárním vyhledávání zjistíme v každém kroku ve které polovině se prvek nachází za pomocí jednoho procesoru.
S použitím N procesorů lze provést N+1 ární vyhledávání - v jednom kroku zjistíme, ve které z N+1 části se může prvek nacházet.
Vlastnosti
Je potřeba CREW PRAM
Časový složitost - 𝑡𝑛=𝑂log⁡(n+1)/logN+1
Cena - cn=O(N∗log𝑁+1(𝑛+1)) - není optimální
Unsorted Search
Vyhledává prvek v neseřazené posloupnosti.
Princip algoritmu
Hledaný prvek 𝒙 pošlu paralelně všem N procesorům.
Každý z procesorů sekvenčně prohledá svůj prostor o velikosti 𝐧/𝐍.
Paralelně si projdu si výsledky od procesorů a pokud nějaký z nich prvek našel, tak ho vrátím.
Vlastnosti 
Model je PRAM s N procesory.
EREW
krok = Olog𝑁, data dokážeme mezi procesy destribuovat a log. čase
krok = On/N
krok = OlogN, data dokážeme z procesorů dostat také v log. čase
CREW
krok = O(1), máme concurent read, takže distribuci dat máme hned
krok = O(n/N)
krok = 𝑂(𝑙𝑜𝑔 𝑁), data dokážeme z procesorů dostat v log. čase
CRCW
krok = O1, data dokážeme mezi procesy destribuovat a log. čase
krok = On/N
krok = O1, data dokážeme z procesorů dostat hned jelikož máme concurent write
Tree Search
Vyhledávání v neseřazené posloupnosti.
Princip algoritmu
Kořen načte hledanou hodnotu 𝒙 a předá ji synům ... až se dostane ke všem listům.
Listy obsahují seznam prvků, ve kterých se vyhledává (každý list jeden). Všechny listy paralelně porovnávají 𝑥 a 𝑥𝑖, výsledek je 0 nebo 1.
Hodnoty všech listů se předají kořenu.
Každý ne-list spočte logické OR svých synů a výsledek zašle otci. Kořen dostane 0 - nenalezeno, 1 - nalezeno
Vlastnosti 
Stromová architektura s 𝟐𝒏−𝟏 procesory.
krok - O(log𝑛)
krok - O(1), procesor porovná příchozí hodnotu s tou, kterou obsahuje
krok - O(log𝑛), distribuce výsledku ke kořenu
tn=Olog𝑛
pn=O2n−1
cn=O(n∗log𝑛), což není optimální
Notes