Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Pokročilé paralelní algoritmy

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah
PI-PPA ZK 4 3C
Garant předmětu:
Pavel Tvrdík
Přednášející:
Pavel Tvrdík
Cvičící:
Pavel Tvrdík
Předmět zajišťuje:
katedra počítačových systémů
Anotace:

Studenti se naučí složité paralelní algoritmy a techniky pro vyhodnocování jejich správnosti, efektivity a optimality.

Požadavky:

MI-PAR

Osnova přednášek:

1. PRAM algoritmy pro zobecněný prefixový součet nad poli a jejich aplikace.

2. PRAM deterministické algoritmy pro prefixové výpočty nad seznamy.

3. PRAM algoritmy pro kontrakci stromů a vyhodnocování výrazů.

4. PRAM deterministické algoritmy pro výpočet souvislých komponent grafu.

5. PRAM randomizované algoritmy pro výpočet souvislých komponent grafu.

6. PRAM deterministické optimální řazení.

7. Optimální řazení na mřížkách.

8. Paralelní algoritmy pro výpočetní geometrii.

9. Paralelní algebraické algoritmy.

10. Paralelní složitost a třídy složitosti P a NC.

Osnova cvičení:
Cíle studia:

Seznámit s pokročilými technikami, na kterých jsou založeny základní paralelní algoritmy a které tudíž dovolují efektivní paralelizaci řešení problémů. Tyto techniky jdou nad obvyklý rámec datového paralelismu kombinovaného s redukcemi či prefixovými výpočty. Kromě vysvětlení myšlenek těchto netriviálních algoritmů se studenti seznámí s propracovanými postupy pro analýzu těchto časově a cenově efektivních nebo optimálních paralelních algoritmů na PRAM modelech a mřížkách.

Studijní materiály:

J. H. Reif, ed. Synthesis of Parallel Algorithms, Morgan Kaufmann Publ., 1993, ISBN 1-55860-135-X.

J. Ja'Ja'. An Introduction to Parallel Algorithms. Addison-Wesley. 1992.

Poznámka:

Bude vypisován v zimních semestrech

Rozvrh na zimní semestr 2024/2025:
Rozvrh není připraven
Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 8. 10. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet1601706.html