Subject description - A8M01ADP

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
A8M01ADP Algorithms for Distributed and Parallel Systems
Roles:PO Extent of teaching:3P+1S
Department:13101 Language of teaching:CS
Guarantors:Macejko P. Completion:Z,ZK
Lecturers:Kencl L., Macejko P. Credits:5
Tutors:Kencl L., Macejko P. Semester:Z

Anotation:

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

Course outlines:

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.

Exercises outline:

Literature:

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

Requirements:

Subject is included into these academic programs:

Program Branch Role Recommended semester
MPOES1 Communications and Signal Processing PO 1


Page updated 6.8.2020 17:51:45, semester: Z,L/2020-1, L/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)