Fakulta elektrotechnická

České vysoké učení technické v Praze

ČVUT v Praze

Popis předmětu - A8M01ADP

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
A8M01ADP Algoritmy pro distribuované a paralelní systémy Rozsah výuky:3+1c
Garanti:  Role:PO Jazyk výuky:CS
Vyučující:Kencl L., Macejko P. Zakončení:Z,ZK
Zodpovědná katedra:13101 Kreditů:5 Semestr:L

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: A8M01ADP

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

Osnovy cvičení:

Literatura:

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

Požadavky:

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
MPOES1 Komunikace a zpracování signálu PO 1


Stránka vytvořena 12.12.2017 05:47:39, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.