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.
Katedra
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.