PředmětyPředměty(verze: 797)
Předmět, akademický rok 2016/2017
   Přihlásit přes CAS
Paralelní algoritmy - NTIN017
Anglický název: Parallel Algorithms
Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2011
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: RNDr. František Mráz, CSc.
Třída: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: 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.
Literatura -
Poslední úprava: RNDr. František Mráz, CSc. (30.04.2015)

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

Sylabus -
Poslední úprava: 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í.

  1. Model paralelních strojů PRAM, měření složitosti paralelních výpočtů, paralelní teze.
  2. Techniky paralelních algoritmů (balancované stromy, metoda rozděl a panuj, rozdělení úlohy, kaskádovité zrychlení).
  3. Paralelní algoritmy pro grafové úlohy - Eulerova věž, určování souvislosti, hledání kostry, nejkratších cest.
  4. Optimální třídící algoritmus, paralelní mergování (slévání), hledání nejmenšího prvku.
  5. Dolní odhady složitosti pro paralelní algoritmy, výpočet funkce OR, sčítání.
  6. Polylog-třídy složitosti, P-úplnost.

 
Univerzita Karlova | Informační systém UK