Algoritmi obilaska mreža

završni rad

• Naslov (engleski): Network Traversal Algorithms
• Autor: Matej Škoro
• Mentor: Mirjana Domazet-Lošo (mentor)
• Član povjerenstva: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Član povjerenstva: Marina Bagić Babac (član povjerenstva)
• Član povjerenstva: Boris Milašinović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2019-09-12, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: 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
• Ključne riječi (engleski): 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
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:910139
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2020-01-07 22:25:50