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.
Anotace
Úvodní přednáška z paralelizmu věnovaná teoretickým modelům tzv. masivně paralelních výpočtů a jejich vztahu k sekvenčním modelům, základním technikám používaným v paralelních algoritmech a těžko paralelizovatelným
úlohám.
Předpokládají se znalosti v rozsahu bakalářského kursu NTIN061 Algoritmy a datové struktury II.