Efikasne implementacije prioritetnog reda

diplomski rad

• Naslov (engleski): Efficient implementation of the priority order
• Autor: Mislav Žanić
• Mentor: Goranka Nogo (mentor)
• Član povjerenstva: Goranka Nogo (predsjednik povjerenstva)
• Član povjerenstva: Ivica Nakić (član povjerenstva)
• Član povjerenstva: Vanja Wagner (član povjerenstva)
• Član povjerenstva: Vedran Čačić (č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: 2022-07-20, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom smo radu prezentirali dvije asimptotski efikasne implementacije prioritetnog reda. U prvom smo poglavlju dali definiciju prioritetnog reda. Također, naveli smo i neke dodatne definicije koje smo koristili kroz ovaj rad. U drugom poglavlju bavili smo se analizom i opisom implementacije Fibonaccijeve hrpe. Dali smo intuitivan opis implementacije operacija prioritetnog reda i dokazali smo tvrdnje potrebne za analizu složenosti te opisali metodu kojom analiziramo složenost. Također smo dali pseudokodove kompleksnijih operacija. Na kraju smo poglavlja analizirali složenost metodom opisanom u istom poglavlju. U trećem smo poglavlju opisali i analizirali Brodalov red. Prvo smo opisali strogu strukturu Brodalovog reda. Potom smo dali opis pomoćne strukture podataka vodilje. Nakon toga opisali smo osnovne operacije nad stablima Brodalovog reda i implementaciju operacija prioirtetnog reda, kao i pseudokod. Na kraju smo napravili analizu složenosti operacija. U zadnjem smo poglavlju uspoređivali performanse Fibonaccijeve hrpe i Brodalovog reda pomoću sortiranja niza nasumice generiranih brojeva.

Sažetak (engleski)

We have presented two asymptotically effcient implementation of a priority queue in this thesis. In the first chapter we have given the definition of priority queue. We have, also, given some additional definitions which we used throughout this thesis. In the second chapter we have analysed and described the implementation of Fibonacci heap. We gave a intuitive description of the implementation of priority queue operations and proved claims needed for the complexity analysis. We, also, briefly describe the complexity analysis method and gave pseudocodes of some operations. We ended the chapter by analysing complexity using the method described in this chapter. In the third chapter we have described and analysed Brodal queue. Firstly, we have described the strict structure of Brodal queue. Then we described a helper data structure called guide. After that, we have described simple tree operations link and delink and implementation of priority queue operations. Finally, we analysed the worst case complexity of implemented operations. In the last chapter, we have compared performance of Fibonacci heap and Brodal queue. We did this by sorting an array of randomly generated numbers using priority queues.

• Ključne riječi: Fibonaccijeva hrpa; pseudokodovi kompleksnijih operacija; Brodalov red
• Ključne riječi (engleski): Fibonacci heap; pseudocodes; Brodal's queue
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:715602
• 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: 2022-09-16 09:38:15