Naslov
Konstrukcija i klasifikacija konačnih struktura pomoću računala
(Construction and classification of finite structures by computer)

Autori
Krčadinac, Vedran

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
PMF-Matematički odjel

Mjesto
Zagreb

Datum
17.05

Godina
2004

Stranica
117

Mentor
Šiftar, Juraj

Ključne riječi
konstrukcija; klasifikacija; konačni linearni prostor; konfiguracija; frekvencijski kvadrat; blok dizajn
(construction; classification; finite linear space; configuration; frequency square; block design)

Sažetak
<p>U ovoj disertaciji proučavaju se algoritamske tehnike konstrukcije i klasifikacije konačnih matematičkih struktura kao što su blok dizajni, konačni linearni prostori, konfiguracije, latinski i frekvencijski kvadrati te orbitne matrice. Disertacija je podijeljena u tri poglavlja i dodatak.</p> <p>U prvom poglavlju cilj je potpuno klasificirati promatrane strukture obzirom na neku relaciju ekvivalencije. Dan je općenit opis četiri klasifikacijska algoritma i dokazana je njihova valjanost. Najvažniji rezultati ovog poglavlja su klasifikacija nekih konačnih linearnih prostora, prebrojavanje i klasifikacija frekvencijskih kvadrata reda 7 i 8 i klasifikacija niza orbitnih matrica koje se kasnije koriste za konstrukciju Steinerovih 2-dizajna.</p> <p>U drugom poglavlju primjenjuje se poznata tehnika konstrukcije blok dizajna sa zadanim grupama automorfizama na Steinerove 2-dizajne. Tehnika se prilagođava jednoj novoj klasi incidencijskih struktura, TSC prostorima (konačnim linearnim prostorima sastavljenim od dvije simetrične konfiguracije). Rezultati o Steinerovim 2-dizajnima su konstrukcija svih S(2, 4, 28) dizajna s netrivijalnim automorfizmima, konstrukcija velikog broja novih S(2, 4, 37) dizajna s automorfizmima reda 2, 3 i 11 i još neki rezultati o grupama automorfizama dizajna S(2, 5, 45), S(2, 6, 61), S(2, 6, 66) i S(2, 7, 85). Pomoću diferencijskih familija konstruirani su linearni prostori TSC(3, k) za k=5, 6, 7, 8, a spomenutom tehnikom TSC(4, 5) prostori s automorfizmima reda 3. Za nekoliko drugih parametara dokazano je nepostojanje TSC prostora s određenim automorfizmima. Osim toga dokazana je jedna općenita konstrukcija TSC prostora, zasnovana na konačnim projektivnim ravninama.</p> <p>U trećem poglavlju pitanje egzistencije blok dizajna i drugih incidencijskih struktura postavlja se kao problem kombinatorne optimizacije i koristi se tabu search algoritam za njegovo rješavanje. Usporedbom s nekoliko sličnih algoritama iz literature pokazuje se da algoritam efikasnije nalazi blok dizajne s v, b<= 1000. Rezultati dobiveni pomoću algoritma su poboljšanje 36 donjih ocjena za broj neizomorfnih blok dizajna i konstrukcija simetrične (34_6) konfiguracije, čija je egzistencija bila nepoznata. Slična tehnika primjenjuje se na jedan drugi kombinatorni problem, pitanje je li svaki S(2, k, v) dizajn s dvostruko više pravaca nego točaka ujedno TSC(k, k) prostor. Dokazano je da tvrdnja vrijedi za sve poznate primjere S(2, k, v) dizajna s b=2v. Pronađeni su primjeri srodnih kombinatornih struktura za koje analogna tvrdnja ne vrijedi.</p> <p>U dodatku su navedene distribucije klasa izotopije frekvencijskih kvadrata s obzirom na red pune grupe autotopija. Podaci omogućuju usporedbu rezultata klasifikacije s rezultatima prebrojavanja frekvencijskih kvadrata, dobivenih pomoću nezavisnih programa. Rezultati se u cijelosti slažu.</p>

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA