An introductory course on parallelism devoted to theoretical models of the so-called massively parallel computations and their relation to sequential computations, basic techniques used in parallel algorithm design and hard parallelisable problems.
Last update: T_KSVI (30.04.2015)
Ú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.
Literature -
Last update: RNDr. František Mráz, CSc. (30.04.2015)
A. Gibbons, W. Rytter: Efficient parallel algorithms, Cambridge University Press, 1988
J. JáJá: An introduction to parallel algorithms, Addison Wesley, 1992
Syllabus -
Last update: RNDr. František Mráz, CSc. (30.04.2015)
This lecture is an introduction into parallel algorithms for the so-called massively parallel models of computers (the number of processors is a function of the input size) with shared memory.
Parallel RAM, complexity measures for parallel computations, parallel thesis.
Lower bounds for parallel computations, computing OR, summation.
Polylog-complexity classes P-complete problems.
Last update: RNDr. František Mráz, CSc. (30.04.2015)
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.