Algoritmi za određivanje najbližeg para

diplomski rad

• Autor: Ivo Doko
• Mentor: Goranka Nogo (mentor)
• Član povjerenstva: Goranka Nogo (predsjednik povjerenstva)
• Član povjerenstva: Nela Bosner (član povjerenstva)
• Član povjerenstva: Vjeran Hari (član povjerenstva)
• Član povjerenstva: Marko Vrdoljak (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2014-09-24, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu smo proučili šest algoritama za rješavanje problema najbližeg para u \(\mathbb{R}^{2}\). Pokazali smo kako se problem može riješiti determinističkim algoritmom složenosti \(O(n\log n)\), a nedeterminističkim algoritmima složenost možemo spustiti do \(O(n)\). Ipak, testiranjem smo utvrdili da je na praktičnim veličinama ulaznih podataka od egzaktnih algoritama najefikasniji onaj koji je predstavljen u odjeljku 3.1 pod imenom Divide_and_Conquer, čija složenost je \(O(n\log^{2}n)\). Na kraju smo predstavili i jedan parametrizirani heuristički algoritam složenosti \(O(\frac{n}{\log n})\) koji pronalazi približno rješenje, čija točnost se može povećati nauštrb vremena izvođenja.

Sažetak (engleski)

In this paper we have examined six different algorithms for solving the closest pair of points problem in \(\mathbb{R}^{2}\). We have shown that the problem can be solved with deterministic algorithms in \(O(n\log n)\) time and in \(O(n)\) time with non-deterministic algorithms. However, testing these algorithms has revealed that, for practical input sizes, the most efficient exact algorithm is the one we have labelled Divide_and_Conquer which was presented in section 3.1 and which runs in \(O(n\log^{2}n)\)time. In the final chapter we have presented a parameterised simulated annealing algorithm which finds an approximate solution in \(O(\frac{n}{\log n})\) time, accuracy of which can be increased at the expense of speed.

• Ključne riječi: problem najbližeg para; deterministički algoritam složenosti; Divide and Conquer; parametrizirani heuristički algoritam
• Ključne riječi (engleski): closest pair of points problem; deterministic algorithm; Divide and Conquer; parameterised simulated annealing algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:881156
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-01-08 12:17:20