Algoritmy pro distribuované a paralelní systémy

Předmět není vypsán Nerozvrhuje se

Kód	Zakončení	Kredity	Rozsah	Jazyk výuky
A8M01ADP	Z,ZK	5	3P+1S	česky

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Předmět slouží jako teoretická průprava pro pokročilou algoritmizaci, paralelní a distribuovanou implementaci algoritmů

v oblasti zpracování signálů, optimalizačních úlohách a algoritmech komunikačních sítí.

Požadavky:

Osnova přednášek:

1. Asymptotická složitost algoritmů, třídy složitosti P, NP a NPC

2. Polynomiálně řešitelné grafové úlohy: minimalní kostra, nejkratší cesta

3. NP úplné grafové úlohy: problém barevnosti grafu, distribuované algoritmy pro barvení grafu

4. Modely a representace pro paralelní a distribuované algoritmy, topologie, komunikace, synchronizace.

Paralelizovatelné úlohy.

5. Paralelní algoritmy na síťové architektruře, třídění, rekurze, směrování.

6. Paralelní algoritmy na dalších arthitekturách - hypercube, hvězda, kruh.

7. Sdílení paměti, pipeline, scheduling, masivně paralelní úlohy.

8. Aplikace paralelních algoritmů v numerických úlohách, zpracování signálu, optimalizace a komunikacích.

9. Programovací jazyky pro paralelní výpočty.

10. Distribuované algoritmy - komunikace, koordinace, symetrie, lokálnost

11. Volba koordinátora.

12. Distribuovaný konsensus (problém byzantských generálů).

13. Synchronizace.

14. Aplikace distribuovaných algoritmů v komunikačních a rozhodovacích sítích.

Osnova cvičení:

Cíle studia:

Studijní materiály:

1. F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan

Kaufmann, 1992.

2. N. Lynch, Distributed Algorithms. Morgan Kaufmann, 1996.

3. G. Tel: Introduction to distributed algorithms, Cambridge 1994

4. D. P. Bertsekas, J. N. Tsitsiklis: Parallel and distributed computation: numerical methods

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: