ADAPTIVNA IDENTIFIKACIJA V GRAFIHStanet, Peter (Avtor) Kovše, Matjaž (Mentor) identifikacijska kodaadaptivna identifikacijapopolna kodapokrivna kodalinearno iskanjedrevesno iskanjeDiplomsko delo obravnava adaptivne identifikacijske kode v grafih, ki so povezane z identi- fikacijskimi kodami. Pri tem obravnavamo problem, kjer fizelimo odkriti okvarjeno vozlišče v grafu tako, da postavljamo vprašanja ali neka krogla vsebuje okvarjeno vozlišče. Cilj adaptivnih identifikacijskih kod je minimizirati število vprašanj, ki so potrebna za odkritje okvarjenega vozlišča, če slednje obstaja. To število označimo z ar(G). V uvodnem poglavju definiramo osnovne pojme iz teorije grafov in kod v grafih, ki jih uporabljamo v nadaljevanju. V drugem poglavju določimo zgornjo in spodnjo mejo za število ar(G) v regularnih grafih. V podpoglavjih omejimo število ar(G) v kvadratni, kral- jevi in trikotni mreži. Ob tem obravnavamo tudi primere, ko je okvarjenih več vozlišč. V tretjem poglavju predstavimo igro Renyijevega tipa, kjer iščemo neznano točko (x; y) v pravokotni mreži s postavljanjem vprašanj glede na podpravokotnike. Pri tem je cilj minimizirati število vprašanj. Pri tem uporabimo drevesno in linearno iskanje.[P. Stanet]20112011-03-30 12:07:36Diplomsko delo17919UDK: 51(043.2)COBISS_ID: 18258440NUK URN: URN:SI:UM:DK:OZMAINM5sl