20.500.12556/RUL-120776 Urejanje terk glede na medsebojno oddaljenost Sorting tuples based on their distances Diplomska naloga Urejanje terk glede na medsebojno oddaljenost rešuje problem urejanja. Želimo poiskati zaporedje n k-terk, da dosežemo minimizacijo ali maksimizacijo kriterijske funkcije. Če problem še podrobneje opišemo, je rezultat urejanja zaporedje, ki minimizira ali maksimizira vsoto ali maksimum razdalj med sosednjimi terkami v zaporedju. Problem smo podrobno definirali in določili težavnost iskanja rešitve. S prevedbo že znanega, sorodnega NP-težkega problema, smo dokazati NP-težkost problema urejanja terk. V nalogi smo predstavili natančne in približne algoritme. Natančne algoritme smo implementirani v pogramskem jeziku Java in eksperimentalno primerjali njihovo učinkovitost. V zaključku sledi predstavitev ključnih ugotovitev. The diploma thesis Sorting tuples based on their distances deals with the problem of sorting. We want to find a sequence of n k-tuples that gives us the minimization or maximization of the criterion function. If we describe the problem in a more detailed way, the result of the sorting is a sequence that minimizes or maximizes the sum or the maximum of the distances between the tuples which are next to each other in a sequence. We defined the problem and determined the complexity of finding the solutions. By transforming the already known NP-hard problem into the problem of sorting tuples, we have proved that sorting tuples is also NP-hard. The thesis presents the exact and approximate algorithms. Exact algorithms were implemented in Java and used in an experiment. We experimentally compared their efficiency and presented it in a graph. Finally, we can check the representation of the key findings. Terka razdalja urejanje permutacija zaporedje optimizacijski problem NP-težkost Tuple distance sorting permutation sequence optimization problem NP-hardness true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2020-09-25 12:15:01 2020-09-25 12:15:04 2024-02-16 10:32:28 0000-00-00 00:00:00 2020 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 26146 32907267 Tanko_Anze_-_Urejanje_terk_glede_na_medsebojno_oddaljenost.pdf Tanko_Anze_-_Urejanje_terk_glede_na_medsebojno_oddaljenost.pdf 1 520295F45638DE18C3C2F694922070C4 2b7d423a313270d82ceb48afedf50b3cbcfd01452457004bd6e7d9fd6530bd12 2bc39b59-a1ba-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=135599 Fakulteta za računalništvo in informatiko 0 0 0