Fakulta informačních technologií VUT v Brně

Detail předmětu

Paralelní a distribuované algoritmy

PRL Ak. rok 2018/2019 letní semestr 5 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 (Parallel Random Access Machine), suma prefixů a její aplikace. Algoritmy nad seznamy, stromy a grafy.

Garant předmětu

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 zkouška, 10 půlsemestrální test, 20 projekty

Zajišťuje ústav

Přednášející

Cvičící

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í.

Dovednosti, znalosti a kompetence obecné

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

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

Cílem předmětu je naučit studenty vytvářet 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í

  • 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
  • Reif, J: Synthesis of Parallel Algorithms, Morgan Kaufmann, 1993, ISBN:155860135X
  • Andrew Adamatzky, Selim Akl, Georgios Ch. Sirakoulis: From Parallel to Emergent Computing, CRC Press, 2019, ISBN 9781138054011

Literatura referenční

  • 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
  • Tvrdík, P.: Parallel Systems and Algorithms, skripta, Praha, Vydavatelství ČVUT 1997.

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.

Kontrolovaná výuka

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.

Rozvrh

DenTypTýdnyMístn.OdDoPSKSkupInfo
Pozkouška2019-05-06 D105 14:0016:50 1MIT 2MIT řádná
Pozkouška2019-05-20 D105 14:0015:50 1MIT 2MIT 1. oprava
Poostatní2019-03-25 C127.1 16:0016:50STUDIUM
Útzkouška2019-06-04 E112 16:0017:50 1MIT 2MIT 2. oprava
Útpřednáškavýuky E112 16:0018:50 1MIT 2MIT MBI MBS MIN MIS MMI MSK xx
Útpřednáška2019-03-26 E104 E105 16:0018:50 1MIT 2MIT MBI MBS MIN MIS MMI MSK xx

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

Nahoru