Detail předmětu
Paralelní a distribuované algoritmy
PDA Ak. rok 2004/2005 zimní semestr 6 kreditů
Vlastnosti paralelních a distribuovaných architektur a abstraktní modely paralelismu. Základní typy topologií, synchronní a asynchronní algoritmy. Komunikace v paralelních a distribuovaných systémech. Distribuované a paralelní algoritmy a jejich složitost. Řešení typických problémů paralelismu. Algoritmy řazení, algoritmy vyhledávání, vektorové a maticové algoritmy. Model PRAM, suma prefixů a její aplikace. Algoritmy nad seznamy, stromy a grafy.
Garant předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 26 hod. projekty
Zajišťuje ústav
Získané dovednosti, znalosti a kompetence z předmětu
Studenti se seznámí se základy paralelních a distribuovaných výpočtů a s obecnými principy paralelních a distribuovaných algoritmů a jejich časovou složitostí.
Studenti se naučí obecné principy a možnosti paralelizace algoritmů.
Cíle předmětu
Seznámení studentů se základními obraty paralelních a distribuovaných výpočtů. Obecné principy paralelních a distribuovaných algoritmů a na jejich časovou složitost.
Požadované prerekvizitní znalosti a dovednosti
Nejsou žádné prerekvizity.
Literatura studijní
- Tvrdík, P.: Parallel Systems and Algorithms, skripta, Praha, Vydavatelství ČVUT 1997.
Literatura referenční
- Jaja, J.: An Introduction to Parallel Algorithms, Addison-Wesley, 1992, ISBN 0-201-54856-9
- Akl, S.: The Design and Analysis of Parallel Algorithms, Prentice-Hall International, ISBN 0-13-200073-3
Osnova přednášek
- Úvod, vlastnosti paralelních a distribuovaných architektur.
- Abstraktní modely paralelismu, PRAM.
- Distribuované a paralelní algoritmy a jejich složitost.
- Komunikace v paralelních a distribuovaných systémech.
- Základní typy topologií, synchronní a asynchronní algoritmy.
- Algoritmy řazení.
- Algoritmy vyhledávání.
- Maticové algoritmy.
- Sumy prefixů a jejich aplikace.
- Algoritmy nad seznamy a grafy.
- Synchronizační algoritmy a úlohy.
- Mechanismy pro synchronizaci.
- Jazyky pro paralelní a distribuované výpočty.
Průběžná kontrola studia
Zápočet je udělen po odevzdání všech projektů.
Kontrolovaná výuka
Výuka není kontrolována.