Naslov
Algoritam konstrukcije t-dizajna zasnovan na razvijanju matrica taktičke dekompozicije
(T-design construction algorithm based on expanding tactical decomposition matrices)

Autori
Martinjak, Ivica

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
08.07

Godina
2010

Stranica
128

Mentor
Pavčević, Mario-Osvin

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
(t-design; incidence matrix; symmetric design; automorphism group; tactical decomposition; deterministic algorithm; exhaustive search; algorithm complexity; solution space)

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, 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.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA