Sinkroni mrežni algoritmi

diplomski rad

• Autor: Katarina Petrović
• Mentor: Robert Manger (mentor)
• Član povjerenstva: Robert Manger (predsjednik povjerenstva)
• Član povjerenstva: Mladen Vuković (član povjerenstva)
• Član povjerenstva: Goran Igaly (član povjerenstva)
• Član povjerenstva: Ivica Nakić (č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: 2020-02-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Ovaj rad opisuje model sinkrone mreže i obrađuje tri sinkrona algoritma u općenitoj mreži, algoritam za izbor vođe, problem najkraćeg puta i maksimalni nezavisni skup. Nabrojani algoritmi služe u rješavaju problema izbora "vođe" u mrežnom računanju, za izgradnju struktura pogodnih za podršku učinkovite komunikacije, rješavanje problema mrežne alokacije resursa i slično. Nakon opisa i analize algoritama, slijedi njihova implementacija u asinkronoj mreži sa sinkronizatorom. U tu svrhu, korišteni su jednostavni sinkronizator i sinkronizator alpha, koji su prethodno opisani. Na kraju je na primjerima demonstriran rad algoritama u odsustvu sinkronizatora.

Sažetak (engleski)

This thesis describes synchronous network model and addresses three algorithms in general synchronous network, leader election, shortest paths and maximal independent set. The above-mentioned algorithms are used to solve the problem of choosing a "leader" in network computing, to build a structure suitable for support communication, to solve the problem of network resource allocations, et cetera. After describing and analyzing the algorithms, they are implemented in asynchronous network model with synchronizer. For this purpose, simple synchronizer and alpha synchronizer were used and described previously. Finally, it is demonstrated on examples how algorithms work in the absence of a synchronizer.

• Ključne riječi: model sinkrone mreže; algoritam za izbor vođe; problem najkraćeg puta; maksimalni nezavisni skup; sinkronizator
• Ključne riječi (engleski): synchronous network model; leader election; shortest paths; maximal independent set; synchronizer
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:716523
• 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: 2020-10-07 09:18:41