|
|
Experimentální analýza algoritmů pro hledání nejkratších cest
Truchlý, Peter ; Koubková, Alena (vedoucí práce) ; Mareš, Martin (oponent)
Hľadanie najkratších ciest v grafe, je často riešenou úlohou programovania v mnohých podobách, zvyčajne ako súčasť riešenia iného problému. Vhodnosť algoritmu či implementácie, na riešenie konkrétnej skupiny problémov, nemusí byť na prvý pohľad zrejmá. V praxi preto môže nastať situácia, keď použitý algoritmus z hľadiska správnosti zodpovedá riešenej úlohe, avšak výkonovo o niekoľko rádov zaostáva. Cieľom diplomovej práce je poskytnutie aktuálneho, prakticky použiteľného prehľadu algoritmov, ktorý je doplnený o experimentálne zistenia a odporúčania vhodnosti pre jednotlivé typy úloh. Značná časť uvedených algoritmov bola otestovaná na spoločnej platforme, čím došlo k zjednoteniu a rozšíreniu predošlých výsledkov. Zahrnuté sú predovšetkým algoritmy triedy SSSP, implementovateľné na bežne dostupnom hardware, zmienené sú však aj algoritmy iných tried, napríklad OPSP a APSP. Špeciálna pozornosť je venovaná aktuálnemu trendu zvyšovania paralelizmu, či už vo forme viacjadrových CPU, alebo masívne paralelných výpočtov na platformách odvodených od GPU.
|
|
|
Experimentální analýza algoritmů pro hledání nejkratších cest
Truchlý, Peter ; Mareš, Martin (oponent) ; Koubková, Alena (vedoucí práce)
Hľadanie najkratších ciest v grafe, je často riešenou úlohou programovania v mnohých podobách, zvyčajne ako súčasť riešenia iného problému. Vhodnosť algoritmu či implementácie, na riešenie konkrétnej skupiny problémov, nemusí byť na prvý pohľad zrejmá. V praxi preto môže nastať situácia, keď použitý algoritmus z hľadiska správnosti zodpovedá riešenej úlohe, avšak výkonovo o niekoľko rádov zaostáva. Cieľom diplomovej práce je poskytnutie aktuálneho, prakticky použiteľného prehľadu algoritmov, ktorý je doplnený o experimentálne zistenia a odporúčania vhodnosti pre jednotlivé typy úloh. Značná časť uvedených algoritmov bola otestovaná na spoločnej platforme, čím došlo k zjednoteniu a rozšíreniu predošlých výsledkov. Zahrnuté sú predovšetkým algoritmy triedy SSSP, implementovateľné na bežne dostupnom hardware, zmienené sú však aj algoritmy iných tried, napríklad OPSP a APSP. Špeciálna pozornosť je venovaná aktuálnemu trendu zvyšovania paralelizmu, či už vo forme viacjadrových CPU, alebo masívne paralelných výpočtov na platformách odvodených od GPU.
|
host ::
RSS.