hrvatski

Konstrukcija i klasifikacija konačnih struktura pomoću računala

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

konstrukcija; klasifikacija; konačni linearni prostor; konfiguracija; frekvencijski kvadrat; blok dizajn

nije evidentirano