Algoritmi obilaska mreža

undergraduate thesis

• Title (english): Network Traversal Algorithms
• Author: Matej Škoro
• Mentor: Mirjana Domazet-Lošo (mentor)
• Committee member: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Committee member: Marina Bagić Babac (član povjerenstva)
• Committee member: Boris Milašinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-09-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Mrežama se vrlo efikasno vizualno i matematički mogu prikazati odnosi između pojedinih čvorova (objekata) i stoga su trenutno u velikoj mjeri primjenjive u mnogim znanostima. Također su od velike važnosti algoritmi obilaska mreža koje možemo podijeliti na algoritme pretraživanja (koji se, primjerice, u velikoj mjeri koriste u umjetnoj inteligenciji) i algoritme pronalaska najkraćeg puta. U ovom radu objašnjeni su matematički pojmovi vezani uz obrade mreža (topologija, promjer, radijus, stupanj središnjosti) i prikazani najvažniji algoritmi obilaska mreža. Također je implementirano nekoliko algoritama te prikazana usporedba vremenskog izvršavanja istih.

Abstract (english)

Relations between given objects can be shown and represented very efficiently visually and mathematical using networks, so networks are currently applicable in many different sciences. Network traversal algorithms, which can be divided in shortest path problems and network search algorithms (which are commom used in artifficial inteligence), are also of big importance. In this thesis, basic mathematical terms of the network are explained (eg. topology, diameter, radius, grouping, centrality), so as network traversal algorithms. Furthermore, some of the explained algorithms are implemented and time efficiency is calculated, shown and compared.

• Keywords: graf; mreža; teorija mreža; kompleksna mreža; topologija; promjer; radijus; grupiranje; središnjost; algoritmi; najkraći put; cijena; heuristika; Dijkstrin algoritam; Bellman - Fordov algoritam; Floyd Warshallov algoritam; pretraživanje u širinu; pretraživanje u dubinu; pretraživanje jednolikom cijenom; heurističko pretraživanje
• Keywords (english): graph; network; complex network; topology; diameter; radius; grouping; centrality; algorithms; shortest path; cost; heuristic; Dijkstra's shortest path algorithm; Bellman - Ford algorithm; Floyd Warshall algorithm; breadth first search; depth first search; uniform cost search; heuristic search
• Language: croatian
• URN:NBN: urn:nbn:hr:168:910139
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2020-01-07 22:25:50