20.500.12556/RUL-95139 Hibridizacija požrešnih algoritmov in hitrega urejanja Hybridization of greedy algorithms and quicksort Požrešna metoda je ena izmed najbolj uporabljenih tehnik pri načrtovanju algoritmov, za katero obstaja več vrst optimizacij. Naša ideja je bila optimiziranje požrešnih algoritmov s pomočjo algoritma hitrega urejanja. V algoritem hitrega urejanja smo vstavili požrešni algoritem. Na tak način ustvarjen hibridni algoritem, lahko na določenih primerih deluje precej hitreje kot navadni požrešni algoritem. Hibridizacijo smo preizkusili na problemih preprostega nahrbtnika, menjave kovancev in izbora aktivnosti ter na Kruskalovem algoritmu in pri razvrščanju poslov v delavnici z enim strojem. Hibridni algoritem je deloval bolje od navadnega požrešnega algoritma pri preprostem problemu nahrbtnika in pri problemu menjave kovancev. The greedy method is one of the most commonly used techniques in algorithm design and there are many different optimizations available. This thesis presents one of them. Our idea for optimization was improving the running time of greedy algorithms with the help of the quicksort algorithm. We integrated the greedy algorithm into quicksort to produce a hybrid algorithm, which can solve certain problems significantly faster than the normal greedy algorithm. In the thesis we chose to test hybridization on the activity-selection problem, the fractional knapsack problem, the coin changing problem, Kruskal's algorithm and unit-task scheduling. We experimentally confirmed that hybrid algorithms (do) indeed perform better with the coin changing problem and the fractional knapsack problem. požrešno nahrbtnik posli aktivnosti Kruskal kovanci urejanje hibridizacija algoritmi greedy hybridization algorithms activity-selection knapsack Kruskal coin-changing quicksort unit-tasks true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2017-09-15 14:49:48 2017-09-15 14:49:49 2022-08-10 02:19:33 0000-00-00 00:00:00 2017 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 20039 Vehovec_Nina_-_Hibridizacija_pozresnih_algoritmov_in_hitrega_urejanja.pdf Vehovec_Nina_-_Hibridizacija_pozresnih_algoritmov_in_hitrega_urejanja.pdf 1 04BE661C0D5AB053CECFCC9A44441921 d400778397793845996e0f71ed01de468d0140ef9a3822e7a96c68a8152d39a5 b1f3ee51-a1b3-11eb-a523-00155dcfd717 20.500.12556/rul/bf3ea3f1-dc2b-4e9c-b80e-bb4fa567c543 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=103704 Fakulteta za računalništvo in informatiko 0 0 0