Ing. Václav Blažej

Závěrečné práce

Bakalářské práce

Paralelizace algoritmů pro toky v síti

Autor
Jan Groschaft
Rok
2019
Typ
Bakalářská práce
Vedoucí
Ing. Václav Blažej
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Tato práce se zabývá možnostmi paralelizace vybraných algoritmů pro nalezení maximálního toku v síti. Je zaveden potřebný teoretický základ, na který navazuje popis existujících sekvenčních a paralelních algoritmů. Následně je prezentována nová modifikace Goldbergova algoritmu vhodná pro paralelní zpracování v systémech se sdílenou pamětí, která je rovněž rozšířena na škálovací verzi. Všechny popsané algoritmy jsou implementovány v jazyce C++ a jejich efektivita je porovnána na sadě různorodých vstupních dat.