Urejanje terk glede na medsebojno oddaljenost
ID TANKO, ANŽE (Avtor), ID Mihelič, Jurij (Mentor) Več o mentorju...

 PDF - Predstavitvena datoteka, prenos (287,04 KB)MD5: 520295F45638DE18C3C2F694922070C4

Izvleček
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.

Jezik: Slovenski jezik Terka, razdalja, urejanje, permutacija, zaporedje, optimizacijski problem, NP-težkost Diplomsko delo/naloga 2.11 - Diplomsko delo FRI - Fakulteta za računalništvo in informatiko 2020 20.500.12556/RUL-120776 32907267 25.09.2020 852 171 Kopiraj citat

## Sekundarni jezik

Jezik: Angleški jezik Sorting tuples based on their distances 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. Tuple, distance, sorting, permutation, sequence, optimization problem, NP-hardness

Nazaj