CTU FEE Moodle
Algorithms for Distributed and Parallel Systems
Algorithms for Distributed and Parallel Systems A8M01ADP
| Credits | 5 |
| Semesters | Winter |
| Completion | Assessment + Examination |
| Language of teaching | Czech |
| Extent of teaching | 3P+1S |
Annotation
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
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
Study targets
No data.
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.
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 outlines
No data.
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
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
No data.
Responsible for the data validity:
Study Information System (KOS)