-
Algoritmy vyhledávání
- Máme sekvenci X = {x1, x2, ..., xn} a prvek x
- Máme za úkol zjistit, zda x = xk a případně zjistit k
-
Optimální sekvenční algoritmus vyhledávání
- X není seřazená - sekvenční vyhledávání:
- t(n)=O(n), c(n)=O(n); je třeba prozkoumat n prvků
- X je seřazená - binární vyhledávání:
- t(n)=O(log n), c(n)=O(log n); pro rozlišení mezi n prvky je třeba prozkoumat log n prvků
-
Seznam algoritmů
- N-ary Search
- Unsorted Search
- Tree Search
-
N-ary Search
- Vyhledává v seřazené posloupnosti
- Princip:
- (a) 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.
- (b) 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 částí se může prvek nacházet.
- Počet kroků je g = log(n+1)/log(N+1)
- Je třeba CREW PRAM.
- t(n): O(log(n+1)/log(N+1)) = O(logN+1(n+1))
- c(n): O(N.logN+1(n+1)), což není optimální
-
Unsorted Search
- vyhledává prvek v neseřazené posloupnosti
- model je PRAM s N procesory
- EREW: t(n)=O(logN+n/N); c(n)=O(N.logN+n)
- CREW: t(n)=O(logN+n/N); c(n)=O(N.logN+n)
- CRCW: t(n) = O(n/N); c(n) = O(n), což je optimální
-
Tree Search
- Vyhledávání v neseřazené posloupnosti
- Stromová architektura s 2n-1 procesory
- t(n): O(log n)
- c(n): t(n).p(n) = O(n.log n), není optimální
-
Sekvenční transpozice matice
Sekvenční řešení má složitost O(n2), kde n je počet řádků/sloupců matice
-
Mesh transpose
- Mřížka n x n procesorů
- Každý procesor má 3 registry A (svoje hodnoty), B (hodnoty pravého horního souseda) a C (hodnoty levého dolního souseda)
- t(n) = O(n)
- p(n) = n2
- c(n) = O(n3), což není optimální
-
EREW transpose
- t(n) = O(1)
- p(n) = (n2-n)/2 = O(n2)
- c(n) = O(n2), což je optimální
-
Násobení matic
- Mesh multiplication
- Tree MV multiplication
|
|