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
Role:PO Rozsah výuky:3P+1S
Katedra:13101 Jazyk výuky:CS
Garanti:  Zakončení:Z,ZK
Přednášející:  Kreditů:5
Cvičící:  Semestr:Z

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 28.3.2024 14:50:14, semestry: L/2023-4, Z/2024-5, Z/2023-4, 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)