Paralelné algoritmy - NTIN017

Prednáška sa koná v stredu od 12:20 v S9

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