| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font
First page > Show document

Show document Help

Title:ADAPTIVNA IDENTIFIKACIJA V GRAFIH
Authors:ID Stanet, Peter (Author)
ID Kovše, Matjaž (Mentor) More about this mentor... New window
Files:.pdf UNI_Stanet_Peter_2011.pdf (544,53 KB)
MD5: A9004B241DAE21CF4C54A05076C41ADF
PID: 20.500.12556/dkum/99419c3f-8035-404e-be69-ab8e6367c221
 
Language:Slovenian
Work type:Undergraduate thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract:Diplomsko 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.
Keywords:identifikacijska koda, adaptivna identifikacija, popolna koda, pokrivna koda, linearno iskanje, drevesno iskanje
Place of publishing:Maribor
Publisher:[P. Stanet]
Year of publishing:2011
PID:20.500.12556/DKUM-17919 New window
UDC:51(043.2)
COBISS.SI-ID:18258440 New window
NUK URN:URN:SI:UM:DK:OZMAINM5
Publication date in DKUM:06.04.2011
Views:2279
Downloads:112
Metadata:XML DC-XML DC-RDF
Categories:FNM
:
STANET, Peter, 2011, ADAPTIVNA IDENTIFIKACIJA V GRAFIH [online]. Bachelor’s thesis. Maribor : P. Stanet. [Accessed 13 April 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=17919
Copy citation
  
Average score:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:English
Title:ADAPTIVE IDENTIFICATION IN GRAPHS
Abstract:In this thesis, we consider adaptive identification, which is closely connected with identifying codes in graphs. We are able to ask if there is a faulty vertex in the ball Br(x). The goal in adaptive identification is to minimize the maximum number of queries, which are necessary to discover the faulty vertex, if it exists. We denote by ar(G) this optimum number. In the initial section we give necessary definitions from graph theory and codes in graphs that we need later. In second section we show the lower and upper bound for the parameter ar(G) in regular graphs. In the subsections we limit the number ar(G) in square, king and triangular lattice. We also consider the cases, where there can be l faulty vertices, for l>1. In third section we present Renyi type of game, where we are looking for unknown point (x; y) in rectangle lattice by posing questions to subrectangles. Our goal here is also to minimize the number of queries. For this we use tree and linear search.
Keywords:identifying code, adaptive identification, perfect code, covering code, linear search, tree search


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica