izpis_h1_title_alt

Urejanje terk glede na medsebojno oddaljenost
ID TANKO, ANŽE (Avtor), ID Mihelič, Jurij (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - 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
Ključne besede:Terka, razdalja, urejanje, permutacija, zaporedje, optimizacijski problem, NP-težkost
Vrsta gradiva:Diplomsko delo/naloga
Tipologija:2.11 - Diplomsko delo
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2020
PID:20.500.12556/RUL-120776 Povezava se odpre v novem oknu
COBISS.SI-ID:32907267 Povezava se odpre v novem oknu
Datum objave v RUL:25.09.2020
Število ogledov:852
Število prenosov:171
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Sorting tuples based on their distances
Izvleček:
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.

Ključne besede:Tuple, distance, sorting, permutation, sequence, optimization problem, NP-hardness

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj