Detail předmětu

Paralelní a distribuované algoritmy

FIT-PRLAk. rok: 2017/2018

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.

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

doc. Dr. Ing. Petr Hanáček

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

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.

Způsob a kritéria hodnocení

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.

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.

    Osnova počítačových cvičení:
    • Projects in the laboratory

    Osnova ostatní - projekty, práce:
    1. Samostatné projekty v paralelním programovacím jazyce.

Učební cíle

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í zkouška, průběžná kontrola a hodnocení projektů. 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.

Základní literatura

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.

Doporučená 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

Zařazení předmětu ve studijních plánech

  • Program IT-MGR-2 magisterský navazující

    obor MMI , 1 ročník, letní semestr, povinný
    obor MBI , 1 ročník, letní semestr, povinný
    obor MSK , 1 ročník, letní semestr, povinný
    obor MMM , 0 ročník, letní semestr, povinný
    obor MBS , 1 ročník, letní semestr, povinný
    obor MPV , 0 ročník, letní semestr, povinně volitelný
    obor MIS , 1 ročník, letní semestr, povinný
    obor MIN , 1 ročník, letní semestr, povinný
    obor MGM , 0 ročník, letní semestr, povinně volitelný