Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Algoritmy pro distribuované a paralelní systémy

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
A8M01ADP Z,ZK 5 3+1c česky
Přednášející:
Lukáš Kencl, Peter Macejko
Cvičící:
Lukáš Kencl, Peter Macejko
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í.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A8M01ADP

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:
Rozvrh na zimní semestr 2018/2019:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
Čt
místnost T2:B3-703
Macejko P.
09:15–11:45
(přednášková par. 1)
Dejvice
Laboratoř K132
místnost T2:B3-703
Macejko P.
11:45–12:30
(přednášková par. 1
paralelka 101)

Dejvice
Laboratoř K132

Rozvrh na letní semestr 2018/2019:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 25. 6. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet2693306.html