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

doctoral thesis

• Title (english): t-design construciton algorithm based on expanding tactical decomposition matrices
• Author: Ivica Martinjak
• Mentor: Mario-Osvin Pavčević (mentor)
• Committee member: Damir Kalpić (predsjednik povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Committee member: Marin Golub (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2010-07-08, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

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.

Abstract (english)

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.

• Keywords: t-dizajn; incidencijska matrica; simetrični dizajn; grupa automorfizama; taktička dekompozicija; deterministički algoritam; iscrpna pretraga; složenost algoritma; prostor rješenja
• Keywords (english): t-design; incidence matrix; symmetric design; automorphism group; tactical decomposition; deterministic algorithm; exhaustive search; algorithm complexity; solution space
• Language: croatian
• URN:NBN: urn:nbn:hr:168:843281
• Promotion: 2010
• Study programme: Title: Computer Science; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti (Doktor znanosti)
• Type of resource: Text
• Extent: 128 str. : graf. prikazi : tablice
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-03-20 14:02:35