izpis_h1_title_alt

1-popolne kode v kockam podobnih grafih : magistrsko delo
ID Kompan, Ana (Avtor), ID Klavžar, Sandi (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (569,21 KB)
MD5: 835BDD89E11C62BC65F6C2E52EB53BEA

Izvleček
V magistrskem delu spoznamo kodiranje, kode in popolne kode, njihovo posplošitev na grafe ter povezavo med 1-popolnimi kodami in dominantno množico v grafih. Opišemo hiperkocke in dokažemo nekaj njihovih lastnosti. Spoznamo grafe dualnih kock, ki so sorodni hiperkockam. Pokažemo, katere lastnosti dualna kocka podeduje od ustrezne hiperkocke, in tiste, ki so pomembne za tvorjenje 1-popolne kode. Ugotovimo, da je dualna kocka $DQ_m$ sestavljena iz $2^{m+1}$ induciranih hiperkock. Le-te namreč vsebujejo Hammingove kode, ki so 1-popolne kode in to vzamemo kot osnovo za tvorjenje 1-popolne kode v dualni kocki. Nato Hammingove kode z nadaljnjimi algoritmi preoblikujemo tako, da res nastane 1-popolna koda v dualni kocki. S tem dokažemo izrek, da dualna kocka $DQ_m$ vsebuje 1-popolno kodo natanko tedaj, ko je $m=2^k-2$ za $k\ge 2$. Dobljeni rezultat uporabimo pri postavljanju meja za dominanto število v dualni kocki s poljubnim parametrom.

Jezik:Slovenski jezik
Ključne besede:hiperkocke, dualne kocke, Hammingove kode, 1-popolne kode
Vrsta gradiva:Magistrsko delo/naloga
Tipologija:2.09 - Magistrsko delo
Organizacija:FMF - Fakulteta za matematiko in fiziko
Leto izida:2018
PID:20.500.12556/RUL-101536 Povezava se odpre v novem oknu
UDK:519.1
COBISS.SI-ID:18388825 Povezava se odpre v novem oknu
Datum objave v RUL:14.06.2018
Število ogledov:1083
Število prenosov:379
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Sekundarni jezik

Jezik:Angleški jezik
Naslov:1-perfect codes over dual-cubes
Izvleček:
In this thesis we introduce coding, codes and perfect codes, their generalization to graphs, and a connection between 1-perfect codes and dominating sets in graphs. We describe hypercubes and prove some of their characteristics. Dual-cubes, which are similar to hypercubes, are introduced. We show the characteristics that are inherited from hypercubes and some that are important for generating 1-perfect codes. We prove that the dual-cube $DQ_m$ consists of $2^{m+1}$ induced hypercubes. Hypercubes contain Hamming codes which are 1-perfect codes, and this is taken as a basis of creating 1-perfect codes in dual-cubes. Hamming codes are further transformed with algorithms that eventually lead to 1-perfect codes. With this we show that the dual-cube $DQ_m$ admits a 1-perfect code if and only if $m=2^k-2$ for $k\ge 2$. This result is used for proving tight bounds on the domination number of dual-cube with an arbitrary parameter.

Ključne besede:hypercubes, dual-cubes, Hamming codes, 1-perfect codes

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj