PRL 33. Distribuované a paralelní algoritmy - algoritmy vyhledávání.

Card Set Information

Author:
hrbi
ID:
223279
Filename:
PRL 33. Distribuované a paralelní algoritmy - algoritmy vyhledávání.
Updated:
2013-06-11 05:08:15
Tags:
prl
Folders:

Description:
szz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. 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
  2. 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ů
  3. Seznam algoritmů
    • N-ary Search
    • Unsorted Search
    • Tree Search
  4. 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í
  5. 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í
  6. 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í
  7. Sekvenční transpozice matice
    Sekvenční řešení má složitost O(n2), kde n je počet řádků/sloupců matice
  8. 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í
  9. EREW transpose
    • t(n) = O(1)
    • p(n) = (n2-n)/2 = O(n2)
    • c(n) = O(n2), což je optimální
  10. Násobení matic
    • Mesh multiplication
    • Tree MV multiplication

What would you like to do?

Home > Flashcards > Print Preview