Detail předmětu
Paralelní a distribuované algoritmy
FIT-PRLAk. rok: 2018/2019
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 (Parallel Random Access Machine), suma prefixů a její aplikace. Algoritmy nad seznamy, stromy a grafy.
Garant předmětu
Zajišťuje ústav
Výsledky učení 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ů.
Prerekvizity
Základní znalosti algoritmizace.
Doporučená nebo povinná literatura
- Akl, S.: The Design and Analysis of Parallel Algorithms, Prentice-Hall International, ISBN 0-13-200073-3
- Reif, J: Synthesis of Parallel Algorithms, Morgan Kaufmann, 1993, ISBN:155860135X
- Akl, S.: The Design and Analysis of Parallel Algorithms, Prentice-Hall International, ISBN 0-13-200073-3
- Jaja, J.: An Introduction to Parallel Algorithms, Addison-Wesley, 1992, ISBN 0-201-54856-9
- Tvrdík, P.: Parallel Systems and Algorithms, skripta, Praha, Vydavatelství ČVUT 1997.
Způsob a kritéria hodnocení
Bodové hodnocení výsledků půlsemestrálního testu a vypracovaného projektu.
Podmínky zápočtu:
Získání alespoň jednoho bodu z každého projektu a získání alespoň 15 bodů v průběhu semestru. Jakákoli forma plagiátorství nebo nesamostatné práce vede k neudělení zápočtu. Zápočty uděluje cvičící, který opravuje půlsemestrální zkoušku.
Jazyk výuky
čeština
Osnovy výuky
- Osnova přednášek:
- Úvod, vlastnosti paralelních a distribuovaných architektur.
- Abstraktní modely paralelismu, PRAM (Parallel Random Access Machine).
- 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.
- Projects in the laboratory
- Samostatné projekty v paralelním programovacím jazyce.
Osnova počítačových cvičení:
Osnova ostatní - projekty, práce:
Cíl
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 jejich časová složitost.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Písemný půlsemestrální test, průběžná kontrola a hodnocení projektů. Test nemá náhradní termín a závěrečná zkouška má dva možné náhradní termíny. Pro získání bodů ze zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena více body, než je minimální hranice uvedená v informačním systému. V opačném případě bude zkouška hodnocena 0 body.
Zařazení předmětu ve studijních plánech
- Program IT-MGR-2 magisterský navazující
obor MMM , libovolný ročník, letní semestr, 5 kreditů, povinný
obor MGM , libovolný ročník, letní semestr, 5 kreditů, povinně volitelný
obor MPV , libovolný ročník, letní semestr, 5 kreditů, povinně volitelný
obor MBS , 1. ročník, letní semestr, 5 kreditů, povinný
obor MBI , 1. ročník, letní semestr, 5 kreditů, povinný
obor MIS , 1. ročník, letní semestr, 5 kreditů, povinný
obor MIN , 1. ročník, letní semestr, 5 kreditů, povinný
obor MMI , 1. ročník, letní semestr, 5 kreditů, povinný
obor MSK , 1. ročník, letní semestr, 5 kreditů, povinný
Typ (způsob) výuky
Přednáška
39 hod., nepovinná
Vyučující / Lektor
Osnova
- Úvod, vlastnosti paralelních a distribuovaných architektur.
- Abstraktní modely paralelismu, PRAM (Parallel Random Access Machine).
- 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.
Projekt
13 hod., povinná
Vyučující / Lektor
Osnova
- Samostatné projekty v paralelním programovacím jazyce.