Předmět Paralelní algoritmy (NTIN017)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN017 - Paralelní algoritmy, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Sylabus
Tato přednáška je úvodem do problematiky paralelních algoritmů pro tzv. masivně paralelní modely počítačů (počet procesorů je funkcí velikosti vstupu) se společnou pamětí. Model paralelních strojů PRAM, měření složitosti paralelních výpočtů, paralelní teze. Techniky paralelních algoritmů (balancované stromy, metoda rozděl a panuj, rozdělení úlohy, kaskádovité zrychlení). Paralelní algoritmy pro grafové úlohy - Eulerova věž, určování souvislosti, hledání kostry, nejkratších cest. Optimální třídící algoritmus, paralelní mergování (slévání), hledání nejmenšího prvku. Dolní odhady složitosti pro paralelní algoritmy, výpočet funkce OR, sčítání. Polylog-třídy složitosti, P-úplnost.
Literatura
I. Parberry: Parallel complexity theory, Pitman Publishing, 1987, (John Wiley & Sons) A. Gibbons, W. Rytter: Efficient parallel algorithms, Cambridge University Press, 1988 J. JáJá: An introduction to parallel algorithms, Addison Wesley, 1992
Garant
RNDr. František Mráz, CSc.