Naslov
Konstrukcije dvoravnina pomoću kombinatoričkih algoritama
(Biplane construction by means of combinatorial algorithms)

Autori
Martinjak, Ivica

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, magistarski rad

Fakultet
Fakulet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
09.01

Godina
2007

Stranica
74

Mentor
Pavčević, Mario-Osvin

Ključne riječi
incidencijska struktura; kombinatorički dizajn; simetrični dizajn; dvoravnina; grupa automorfizama; iscrpna pretraga; heuristički algoritam; genetski algoritam; penjanje uzbrdo; složenost algoritma
(incidence structure; block design; biplane; automorphism group; exhaustive search; heuristic algorithm; genetic algorithm; hill climbing; complexity of algorithm)

Sažetak
Dvoravnine su simetrični dizajni s parametrima 2-(v, k, l). Do sada je poznato sedamnaest dvoravnina, sa sedam različitih trojki parametara. Pri tome, dvoravnine s 56 i 79 točaka nisu klasificirane, već su poznati samo pojedini primjeri. Dvoravnine su strukture visoke pravilnosti čija veličina prostora rješenja izrazito raste s brojem točaka (kombinatorička eksplozija). Dodatna poteškoća pri konstrukciji ovih struktura je vrlo mali broj struktura (rezultata) u prostoru pretraživanja. Determinističkim algoritmom (iscrpnom pretragom) klasificirane su dovravnine redova 2, 3, 4 i 7. Pretragom uz dodatno pretpostavljeni uvjet (jedinice na glavnoj dijagonali incidencijske matrice) konstruirane su dvije dvoravnine 2-(56, 11, 2). Prilikom pretrage uz taj uvjet, kod 2-(37, 9, 2) uočena je jednoznačna određenost broja incidencijskih matrica brojem odgovarajućih vektora iz (k+2)-og retka. Analogna se pravilnost javlja i na ispitanom uzorku 2-(56, 11, 2). U eksperimentima s heurističkim algoritmima, pokazalo se da konstrukcija pomoću Hussainovih grafova ima manji prostor rješenja nego konstrukcija pomoću matrica incidencije, uz određene pretpostavke. Najveći utjecaj na doseg imalo je matematičko pojednostavljenje problema, postavljanje dodatnog uvjeta na strukturu te filtriranje vektora.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA