Název:

Paralelní a distribuované algoritmy

Zkratka:PRL
Ak.rok:2009/2010
Semestr:letní
Studijní plán:
ProgramOborRočníkPovinnost
IT-MGR-2 MPV2.povinný
IT-MGR-2MBI1.povinný
IT-MGR-2MBS1.povinný
IT-MGR-2MGM-povinně volitelný - skupina M
IT-MGR-2MGM.2.volitelný
IT-MGR-2MIN1.povinný
IT-MGR-2MIN.1.povinný
IT-MGR-2MIS1.povinný
IT-MGR-2MIS.1.povinný
IT-MGR-2MMI1.povinný
IT-MGR-2MMM1.povinný
IT-MGR-2MPS-volitelný
IT-MGR-2MSK1.povinný
IT-MGR-2EITE1.povinný
Vyučovací jazyk:čeština
Informace pro zapsané:http://www.fit.vutbr.cz/study/courses/PRL/private/
Kredity:5 kreditů
Ukončení:zápočet+zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:3900013
 zkouškatestycvičenílaboratořeostatní
Body:70100020
Garant:Hanáček Petr, doc. Dr. Ing., UITS
Přednášející:Hanáček Petr, doc. Dr. Ing., UITS
Cvičící:Kaluža Vlastimil, Ing., UITS
Michlovský Zbyněk, Ing., UITS
Pindryč Milan, Ing., UITS
Zbořil František, Ing., Ph.D., UITS
Žák Jakub, Ing., UITS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav inteligentních systémů FIT VUT v Brně
Nahrazuje:
Paralelní a distribuované algoritmy (PDA), 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.
Anotace:
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.
Požadované prerekvizitní znalosti a dovednosti:
Základní znalosti algoritmizace.
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ů.
Osnova přednášek:
  1. Úvod, vlastnosti paralelních a distribuovaných architektur.
  2. Abstraktní modely paralelismu, PRAM (Parallel Random Access Machine). 
  3. Distribuované a paralelní algoritmy a jejich složitost.
  4. Komunikace v paralelních a distribuovaných systémech.
  5. Základní typy topologií, synchronní a asynchronní algoritmy.
  6. Algoritmy řazení.
  7. Algoritmy vyhledávání.
  8. Maticové algoritmy.
  9. Sumy prefixů a jejich aplikace.
  10. Algoritmy nad seznamy a grafy.
  11. Synchronizační algoritmy a úlohy.
  12. Mechanismy pro synchronizaci.
  13. Jazyky pro paralelní a distribuované výpočty.
Osnova počítačových cvičení:
  1. Projects in the laboratory
Osnova ostatní - projekty, práce:
  1. Samostatné projekty v paralelním programovacím jazyce.
Literatura referenční:
  1. Akl, S.: The Design and Analysis of Parallel Algorithms, Prentice-Hall International, ISBN 0-13-200073-3
  2. Jaja, J.: An Introduction to Parallel Algorithms, Addison-Wesley, 1992, ISBN 0-201-54856-9
  3. Tvrdík, P.: Parallel Systems and Algorithms, skripta, Praha, Vydavatelství ČVUT 1997.
Literatura studijní:
  1. Akl, S.: The Design and Analysis of Parallel Algorithms, Prentice-Hall International, ISBN 0-13-200073-3
  2. Reif, J: Synthesis of Parallel Algorithms, Morgan Kaufmann, 1993, ISBN:155860135X
Kontrolovaná výuka:
Písemný půlsemestrální test, 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.
Průběžná kontrola studia:
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.