prikaz prve stranice dokumenta Algoritmi za određivanje najbližeg para
  Download
PDF 500.89 KB
master's thesis
Algoritmi za određivanje najbližeg para
Zagreb: University of Zagreb, Faculty of Science, 2014. urn:nbn:hr:217:881156
Doko, Ivo
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Doko, I. (2014). Algoritmi za određivanje najbližeg para (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:881156

Doko, Ivo. "Algoritmi za određivanje najbližeg para." Master's thesis, University of Zagreb, Faculty of Science, 2014. https://urn.nsk.hr/urn:nbn:hr:217:881156

Doko, Ivo. "Algoritmi za određivanje najbližeg para." Master's thesis, University of Zagreb, Faculty of Science, 2014. https://urn.nsk.hr/urn:nbn:hr:217:881156

Doko, I. (2014). 'Algoritmi za određivanje najbližeg para', Master's thesis, University of Zagreb, Faculty of Science, accessed 01 June 2024, https://urn.nsk.hr/urn:nbn:hr:217:881156

Doko I. Algoritmi za određivanje najbližeg para [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2014 [cited 2024 June 01] Available at: https://urn.nsk.hr/urn:nbn:hr:217:881156

I. Doko, "Algoritmi za određivanje najbližeg para", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2014. Available at: https://urn.nsk.hr/urn:nbn:hr:217:881156

Metadata
TitleAlgoritmi za određivanje najbližeg para
AuthorIvo Doko
MentorGoranka Nogo (mentor)
Committee memberGoranka Nogo (predsjednik povjerenstva)
Committee memberNela Bosner (član povjerenstva)
Committee memberVjeran Hari (član povjerenstva)
Committee memberMarko Vrdoljak (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2014-09-24, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:881156
Study programmeTitle: Computer Science and Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2019-01-08 12:17:20