Paralelné algoritmy - NTIN017
Prednáška sa koná v stredu od 12:20 v S9
Sylabus prednášky
Pomocné texty
- 1. časť - úvod, literatúra, PRAM, niektoré základné techniky, paralelná téza, optimálne a efektívne paralelné algoritmy - pdf na obrazovku (pdf pre tlač)
- 2. časť - počítanie vybraných funkcií na PRAMe - pdf na obrazovku (pdf pre tlač)
- 3. časť - simulácie medzi sekvenčnými a paralelnými modelmi - pdf na obrazovku (pdf pre tlač)
- 4. časť - dolné odhady časovej zložitosti pre PRAM - pdf na obrazovku (pdf pre tlač)
- 5. časť - efektívne paralené algoritmy - pdf na obrazovku (pdf pre tlač)
- 6. časť - technika Eulerových cyklov na stromoch, hľadanie najkratších ciest - pdf na obrazovku (pdf pre tlač)
- 7. časť - komponenty súvislosti, kostra grafu, 2-súvislé komponenty - pdf na obrazovku (pdf pre tlač)
- 8. časť - Eulerove cykly pre obecné grafy - pdf na obrazovku (pdf pre tlač) a alternatívne slidy
- 9. časť - Paralne optimálne triedenie - pdf na obrazovku (pdf pre tlač)
- 10. časť - P-úplnosť, ťažko paralelizovateľné úlohy - pdf na obrazovku (pdf pre tlač)
- 11. časť - Rozpoznávanie a analýza bezkontextových jazykov - pdf na obrazovku (pdf pre tlač)
- 12. časť - Maximálne párovanie - pdf na obrazovku (pdf pre tlač)
- Počítanie niektorých funkcií, simulácie Turingovho stroja na PRAMe s veľkou šírkou slova, dolné odhady - výňatok z
Michal Chytil a František Mráz: Složitost paralelních výpočtů (po slovensky). In Miroslav Bartošek, editor, SOFSEM'90, str. 157-186, Janské Lázně, Československo, November 1990.
Základná literatúra
[1] I. Parberry: Parallel complexity theory, Pitman Publishing, John Wiley
& Sons, 1987.
[2] A. Gibbons, W. Rytter: Efficient parallel algorithms, Cambridge University
Press, 1988.
[3] J. JáJá: An introduction to parallel algorithms, Addison
Wesley, 1992.