ADAPTIVNA IDENTIFIKACIJA V GRAFIH

Stanet, Peter

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	ADAPTIVNA IDENTIFIKACIJA V GRAFIH
Authors:	ID Stanet, Peter (Author) ID Kovše, Matjaž (Mentor) More about this mentor...
Files:	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
UDC:	51(043.2)
COBISS.SI-ID:	18258440
NUK URN:	URN:SI:UM:DK:OZMAINM5
Publication date in DKUM:	06.04.2011
Views:	2449
Downloads:	119
Metadata:
Categories:	FNM
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
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