45 - Distribuované a paralelní algoritmy - algoritmy vyhledávání

Question 1

Optimální algo

Answer 1

Optimální sekvenční algoritmus pro vyhledávání
a. X není seřazená - sekvenční vyhledávání
○ t(n)=O(n), je potřeba prozkoumat n prvků.

b. X je seřazená - binární vyhledávání
○ t(n)=O(log⁡n )

Tak mě ještě napadá co Hash tables? Ty jsou konstantní ne?

Question 2

N-ary search - seřazená posloupnost

Answer 2

Vyhledává v seřazené posloupnosti. - rozdělíme na části podle počtu procesorů, zjistíme v jaké části se nachází

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 - t(n)=O(log⁡(n+1)/log⁡(N+1) )
• Cena - c(n)=O(N∗log_(N+1)⁡〖(n+1)〗) - není optimální

Question 3

N-ary search - NEseřazená posloupnost - OPTIMÁLNÍ S CRCW

Answer 3

Vyhledává prvek v neseřazené posloupnosti.
Princip algoritmu
1. Hledaný prvek x pošlu paralelně všem N procesorům.
2. Každý z procesorů sekvenčně prohledá svůj prostor o velikosti n/N.
3. 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
1. krok = O(log⁡N ), data dokážeme mezi procesy destribuovat a log. čase
2. krok = O(n/N)
3. krok = O(log⁡N ), data dokážeme z procesorů dostat také v log. čase
○ t(n)=O(log⁡N+n/N) — c(n)=O(N∗log⁡N+n)
• CREW
1. krok = O(1), máme concurent read, takže distribuci dat máme hned
2. krok = O(n/N)
3. krok = O(log N), data dokážeme z procesorů dostat v log. čase
○ t(n)=O(log⁡N+n/N) — c(n)=O(N∗log⁡N+n)
• CRCW
1. krok = O(1), data dokážeme mezi procesy destribuovat a log. čase
2. krok = O(n/N)
3. krok = O(1), data dokážeme z procesorů dostat hned jelikož máme concurent write
○ t(n)=O(n/N) — c(n)=O(n), což je optimální

Question 4

Tree Search - NEseřazená posloupnost

Answer 4

pošleme hodnotu do listů, pokud je přítomna, list pošle zpátky 1, jinak 0

Princip algoritmu
1. Kořen načte hledanou hodnotu x a předá ji synům … až se dostane ke všem listům.
2. Listy obsahují seznam prvků, ve kterých se vyhledává (každý list jeden). Všechny listy paralelně porovnávají x a x_i, výsledek je 0 nebo 1.
3. 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 2n−1 procesory.
	1. krok - O(log⁡n)
	2. krok - O(1), procesor porovná příchozí hodnotu s tou, kterou obsahuje
	3. krok - O(log⁡n), distribuce výsledku ke kořenu
	• t(n)=O(log⁡n )
	• p(n)=O(2n−1)
	• c(n)=O(n∗log⁡n), což není optimální