20.500.12556/RUL-155936 Sprotna strežba s k-strežniki v ravnini The K-server problem in the plane Problem k-strežnikov obravnava dinamično dodeljevanje omejenega števila strežnikov za obdelavo zahtev v realnem času, pri čemer poskuša optimizirati premike strežnikov z namenom zmanjšanja skupne prepotovane razdalje. Ta računalniški izziv raziskuje strategije za učinkovito prilagajanje dinamičnim zahtevam, pri čemer se odločitve sprejemajo brez poznavanja prihodnjih zahtev. Cilj je razviti algoritme, ki dosegajo ravnotežje med odzivnostjo in optimalnostjo, ko so jim predstavljena nepredvidljiva zaporedja zahtev. Uspešnost algoritmov se preučuje s konkurenčnimi razmerji med sprotnimi algoritmi in optimalnim statičnim algoritmom. V okviru diplomskega dela sem implementiral (v pythonu) najbolj znane algoritme za reševanje problema k-strežnikov ter ocenil njihovo uspešnost. Za najuspešnejšega se je izkazal hitri algoritem delovne funkcije. The k-server problem deals with the dynamic allocation of a limited number of servers to process requests in real-time, aiming to optimize server movements to reduce the overall traveled distance. This computational challenge explores strategies for efficiently adapting to dynamic demands, making decisions without knowledge of future requests. The goal is to develop algorithms that strike a balance between responsiveness and optimality when presented with unpredictable sequences of requests. Algorithm performance is evaluated through competitive ratios between online algorithms and an optimal static algorithm. In this thesis, I implemented (in Python) the most well-known algorithms for solving the k-server problem and assessed their effectiveness. The Fast Work Function algorithm proved to be the most successful. sprotni algoritmi konkurenčna analiza obdelava zahtev optimizacija python pretoki v grafu testiranje online algorithms competitive analysis request processing optimization Python network flows testing true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2024-04-24 12:53:23 2024-04-24 12:53:23 2024-05-17 06:31:37 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 36666 189058819 Volcjak_Domen_-_Sprotna_strezba_s_k-strezniki_v_ravnini.pdf Volcjak_Domen_-_Sprotna_strezba_s_k-strezniki_v_ravnini.pdf 1 AEC3069F140186E8BF2C82E9734E6215 442a3e03f1b50a34a8975a28f64bdbf98115d8a91a27b6b71eeebae223c1fa61 df21444e-0228-11ef-a15b-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=183072 Fakulteta za računalništvo in informatiko 0 0 0