Algoritam konstrukcije t-dizajna zasnovan na razvijanju matrica taktičke dekompozicije (CROSBI ID 364701)
Ocjenski rad | doktorska disertacija
Podaci o odgovornosti
Martinjak, Ivica
Pavčević, Mario-Osvin
hrvatski
Algoritam konstrukcije t-dizajna zasnovan na razvijanju matrica taktičke dekompozicije
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, l), 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.
t-dizajn; incidencijska matrica; simetrični dizajn; grupa automorfizama; taktička dekompozicija; deterministički algoritam; iscrpna pretraga; složenost algoritma; prostor rješenja
nije evidentirano
engleski
t-design construction algorithm based on expanding tactical decomposition matrices
nije evidentirano
t-design; incidence matrix; symmetric design; automorphism group; tactical decomposition; deterministic algorithm; exhaustive search; algorithm complexity; solution space
nije evidentirano
Podaci o izdanju
128
08.07.2010.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Fakultet elektrotehnike i računarstva
Zagreb