CTU FEE Moodle
Algorithms for Distributed and Parallel Systems
B211 - Winter 21/22
This course is not present in Moodle. You can visit its homepage by clicking the "Course page (outside Moodle)" button on the right (if available).
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
None
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
None
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
None