Algoritam konstrukcije t-dizajna zasnovan na razvijanju matrica taktičke dekompozicije

disertacija

• Naslov (engleski): t-design construciton algorithm based on expanding tactical decomposition matrices
• Autor: Ivica Martinjak
• Mentor: Mario-Osvin Pavčević (mentor)
• Član povjerenstva: Damir Kalpić (predsjednik povjerenstva)
• Član povjerenstva: Vedran Krčadinac (član povjerenstva)
• Član povjerenstva: Robert Manger (član povjerenstva)
• Član povjerenstva: Marin Golub (č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: 2010-07-08, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo
• Univerzalna decimalna klasifikacija (UDC): 004 - Računalna znanost i tehnologija. Računalstvo. Obrada podataka

Sažetak

Kombinatorički dizajn je vrlo pravilna konačna struktura sastavljena od dvije vrste objekata, točaka i blokova. Prostor rješenja kombinatoričkih struktura izrazito raste s brojem točaka, te se redovito govori o kombinatoričkoj eksploziji. Budući da potpuna klasifikacija takvih struktura općenito nije moguća, konstrukciji se pristupa pretpostavljanjem dodatnih pravilnosti koje bi struktura mogla sadržavati, a koje se često formuliraju u obliku neke grupe automorfizama. S druge strane, od posebnog su pak interesa dizajni s trivijalnom grupom djelovanja automorfizama, kakvih je najviše, a vrlo malo poznatih, zbog otežane konstrukcije. Ovaj se rad bavi razvojem efikasnog algoritma za konstrukciju t-dizajna, zasnovan na razvijanju matrica taktičkih dekompozicija koje bi mogle nastati djelovanjem automorfizma prim reda, uz mogućnost da se u ovom koraku konstrukcije djelovanje grupe iskoristi ili zaboravi. Kod simetričnih dizajna ostvarene su parcijalne klasifikacije dizajna s parametrima (36, 15, 6) i (41, 16, 6), uz uvjet djelovanja automorfizma reda 3. Ista parcijalna klasifikacija izvedena je za nesimetrični dizajn s parametrima (13, 5, 5). Konstruirano je mnoštvo novih nesimetričnih dizajna s trojkama parametara (16, 6, 5) i (21, 6, 4). Općenitost algoritma pokazana je na malim parametrima t-(v, k, λ), za t > 2. Broj novih dizajna konstruiranih u radu brojiv je u stotinama milijuna, pri čemu je dobiveno preko milijun dizajna s trivijalnom grupom automorfizama.

Sažetak (engleski)

A combinatorial design can be described as a very regular finite structure consisting of two kinds
of objects, points and blocks. The solution space of a combinatorial structure grows enormously
with the number of points, which is known as the combinatorial explosion. Since a complete classification
of such a structure is generally not possible, a construction is attempted by assuming additional
constraints, which the structure could contain and which are often formulated as some automorphism group
action. Designs having the trivial order of automorphism groups are of special interest since most of
designs are of such kind, but only few are known, because of the particularly complex construction.
This work deals with development of efficient algorithms for t-designs construction, based on tactical
decomposition which could be achieved from an action of a prim order automorphism, with the possibility
to use or to forget the group action in this construction step.

Among the symmetric designs, partial classification for parameters (36, 15, 6) and (41, 16, 6),
assuming an action of an automorphism of order 3, was realized. The same partial classification was done
for non-symmetric design with parameters (13, 5, 5). Very many new non-symmetric designs were constructed
for parameter triples (16, 6, 5) and (21, 6, 4). The generality of the algorithm was shown for small
parameters t-(v, k, ?), t > 2. The number of new designs constructed here can be counted in hundreds of
millions, and also over a million of designs having no non-trivial automorphisms was achieved.

• Ključne riječi: t-dizajn; incidencijska matrica; simetrični dizajn; grupa automorfizama; taktička dekompozicija; deterministički algoritam; iscrpna pretraga; složenost algoritma; prostor rješenja
• Ključne riječi (engleski): t-design; incidence matrix; symmetric design; automorphism group; tactical decomposition; deterministic algorithm; exhaustive search; algorithm complexity; solution space
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:843281
• Datum promocije: 2010
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: poslijediplomski znanstveni (doktorski); Akademski / stručni naziv: Doktor znanosti (dr. sc.)
• Vrsta resursa: Tekst
• Opseg: 128 str. : graf. prikazi : tablice
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-03-20 14:02:35