Detail předmětu

Paralelní a distribuované algoritmy

PRL Ak. rok 2023/2024 letní semestr 5 kreditů

Aktuální akademický rok

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

Hanáček Petr, doc. Dr. Ing. (UITS)

Koordinátor předmětu

Zbořil František, doc. Ing., Ph.D. (UITS)

Jazyk výuky

česky

Zakončení

zápočet+zkouška (písemná)

Rozsah

  • 39 hod. přednášky
  • 13 hod. projekty

Bodové hodnocení

  • 70 bodů závěrečná zkouška (písemná část)
  • 10 bodů půlsemestrální test (písemná část)
  • 20 bodů projekty

Zajišťuje ústav

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

Přednášející

Hanáček Petr, doc. Dr. Ing. (UITS)
Zbořil František, doc. Ing., Ph.D. (UITS)

Cvičící

Veigend Petr, Ing., Ph.D. (UITS)

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 jejich časová složitost.
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ů.

Proč je předmět vyučován

Cílem předmětu je naučit studenty vytvářet paralelní algoritmická řešení základních úloh jako jsou řazení, vyhledávání, práce se seznamy a pod. Dále student bude schopen vytvářet správně paralelní a distribuované aplikace a správně využívat synchronizačními mechanismy.

Požadované prerekvizitní znalosti a dovednosti

Základní znalosti algoritmizace.

Literatura studijní

  • 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
  • Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar: Introduction to Parallel Computing, Addison Wesley, 2003, ISBN: 0-201-64865-2
  • Jaja, J.: An Introduction to Parallel Algorithms, Addison-Wesley, 1992, ISBN 0-201-54856-9

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 ostatní - projekty, práce

  1. Samostatné projekty v paralelním programovacím jazyce.

Průběžná kontrola studia

Bodové hodnocení výsledků půlsemestrálního testu a vypracovaného projektu.
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.

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.

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

Nahoru