Kombinatoričko generiranje podskupova pomoću binarno reflektiranih Grayevih kodova

diplomski rad

• Naslov (engleski): Combinatorial Generation of Subsets Using the Binary Reflected Gray Codes
• Autor: Tomislav Zoričić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Ana Žgaljić Keko (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2015-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

35
Sažetak Sažetak Sažetak Sažetak
Kombinatoričko generiranje podskupova pomoću binarnog reflektiranih Grayevih kodova
Opisana su dva algoritma za pronalazak i generiranje svih podskupova nekog skupa. Prvi algoritam je leksikografski poredak, generalizacija abecednog poretka riječi baziranog na abecednom poretku slova. Drugi algoritam je metoda minimalne promjene, koja koristi Grayev kod, posebnu vrstu binarnog koda, u kojem se dvije susjedne vrijednosti razlikuju u samo jednom bitu, što omogućuje minimalnu promjenu u pronalasku sljedbenika ili prethodnika.
U ovom radu objašnjen je način rada oba algoritma, njihove prednosti te pseudokodovi za računalnu korištenje, kao i razvijena programska implementacija kojom se demonstrira rad navedenih algoritama.

Sažetak (engleski)

This thesis describes two algorithms for finding and generating all subsets of some set. First algorithm is called lexicographic order, and it is generalization of alphabetical order of words based on alphabetical order of letters. Second algorithm is minimal change algorithm, that uses Gray's code, special type of binary code, in which two successive elements vary in only one bit, which enables minimal change in finding successor or predecessor.
In this thesis both algorithms are described, with their and pseudocodes for computer usage. Also, a program implementation is developed to demonstrate a way both algorithms work.

• Ključne riječi: Kombinatoričko generiranje; Podskupovi; Leksikografski poredak; Poredak minimalne promjene; Grayev kod; Binarni reflektirani Grayev kod; Hiperkocka; Rangiranje; Odrangiranje; Pronalazak elemenata sljedbenika
• Ključne riječi (engleski): Combinatorial generation; Subsets; Lexicographical ordering; Minimal change ordering; Gray code; Binary reflected Gray code; Hypercube; Ranking; Unranking; Successor finding
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:365238
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 14:33:29