prikaz prve stranice dokumenta Konstruiranje blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama korištenjem genetskih algoritama
  Preuzmi
PDF 675.82 KB
disertacija
Konstruiranje blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama korištenjem genetskih algoritama
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2022. urn:nbn:hr:217:934398
Zrinski, Tin
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Zrinski, T. (2022). Konstruiranje blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama korištenjem genetskih algoritama (Disertacija). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:934398

Zrinski, Tin. "Konstruiranje blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama korištenjem genetskih algoritama." Disertacija, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2022. https://urn.nsk.hr/urn:nbn:hr:217:934398

Zrinski, Tin. "Konstruiranje blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama korištenjem genetskih algoritama." Disertacija, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2022. https://urn.nsk.hr/urn:nbn:hr:217:934398

Zrinski, T. (2022). 'Konstruiranje blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama korištenjem genetskih algoritama', Disertacija, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 21.12.2024., https://urn.nsk.hr/urn:nbn:hr:217:934398

Zrinski T. Konstruiranje blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama korištenjem genetskih algoritama [Disertacija]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2022 [pristupljeno 21.12.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:934398

T. Zrinski, "Konstruiranje blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama korištenjem genetskih algoritama", Disertacija, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2022. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:934398

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:934398
Podaci o radu
NaslovKonstruiranje blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama korištenjem genetskih algoritama
Naslov (engleski)Constructing block designs and strongly regular graphs with prescribed automorphism group using genetic algorithms
AutorTin Zrinski
MentorDean Crnković (mentor)
Član povjerenstvaVedran Krčadinac (predsjednik povjerenstva)
Član povjerenstvaVedrana Mikulić Crnković (član povjerenstva)
Član povjerenstvaDean Crnković (član povjerenstva)
Član povjerenstvaAndrea Švob (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2022-10-21, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Univerzalna decimalna klasifikacija
(UDC)		51 - Matematika
Sažetak
Konstrukcija blokovnih dizajna s određenim dopustivim parametrima se često pokušava izvesti za određeni skup parametara uz pretpostavljanje nekih dodatnih ograničenja na strukturu dizajna kako bi pretraživanje bilo računalno izvedivo. Prirodno ograničenje je pretpostavka da određena grupa automorfizama djeluje na dizajn. Jedna od metoda konstruiranja blokovnih dizajna s pretpostavljenom grupom automorfizama je metoda koja koristi orbitne matrice, a sastoji se od dvaju koraka: konstrukcije orbitnih matrica za pretpostavljenu grupu automorfizma i konstrukcije blokovnih dizajna za orbitne matrice dobivene na ovaj način (ovaj korak se naziva indeksiranje orbitnih matrica). Indeksiranje orbitnih matrica obično se provodi metodom iscrpnog pretraživanja. Međutim, ponekad iscrpno pretraživanje nije izvedivo jer postoji previše slučajeva koje bi trebalo provjeriti. Slično, jako regularni grafovi s određenim dopustivim parametrima se mogu konstruirati korištenjem orbitnih matrica za pretpostavljenu grupu automorfizma. Genetski algoritam je metoda pretraživanja koja se koristi u računarstvu za pronalazak točnih ili približno točnih rješenja za probleme optimizacije i pretraživanja. Genetski algoritam oponaša prirodnu evoluciju, odnosno temelji se na optimizaciji populacije, podskupa cijelog prostora pretraživanja. Kao i u prirodi, populacija se sastoji od jedinki koje se mogu razmnožavati i nad kojima mogu djelovati određene mutacije te se na taj način stvaraju nove jedinke s boljim ili lošijim svojstvima od prethodnih. Cilj algoritma je usmjeriti populaciju ka stvaranju boljih jedinki što može rezultirati pronalaskom optimalnih rješenja zadanog problema. U ovoj doktorskoj disertaciji opisujemo korištenje genetskog algoritma u koraku indeksiranja orbitnih matrica za konstrukciju blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama. Korištenjem ovog pristupa konstruirali smo nove blokovne dizajne, točnije nove Steinerove sustave s parametrima S(2,5,45) i nove simetrične dizajne s parametrima (71,15,3) te nove jako regularne grafove s parametrima (96,19,2,4) i (96,20,4,4).
Sažetak (engleski)
Construction of block designs with certain admissible parameters is often attempted for a particular set of parameters with the assumption of some additional constraints on the design structure in order to make the search computationally feasible. A natural constraint is the assumption that a given group of automorphisms acts on the design. One of the methods for constructing block designs with a prescribed automorphism group is the method that uses so called orbit matrices. It consists of two steps: construction of orbit matrices for the given automorphism group and construction of block designs for the orbit matrices obtained in this way (this step is called "indexing of orbit matrices"). Indexing is usually performed by exhaustive search. However, sometimes exhaustive search is not feasible because there are too many cases to check. Similarly, strongly regular graphs with certain admissible parameters can be constructed using orbit matrices for the prescribed automorphism group. Genetic algorithms are search methods used in computing whose objective is to find exact or approximate solutions to optimization and search problems. A genetic algorithm mimics natural evolution, that is, it is based on optimizing a population (a subset of the entire search space). As in nature, the population consists of individuals that can reproduce and that can be affected by certain mutations, thus creating new individuals with better or worse properties than the previous ones. The goal of the algorithm is to direct the population towards creating better individuals, which can result in finding optimal solutions to a given problem. In this doctoral dissertation, we describe the use of a genetic algorithm in the step of indexing of orbit matrices for the construction of block designs and strongly regular graphs with a prescribed automorphism group. Using this approach, we have constructed new block designs, namely new Steiner systems with parameters S(2,5,45), new symmetric designs with parameters (71,15,3) and new strongly regular graphs with parameters (96,19,2,4) and (96,20,4,4).
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:934398
Studijski programNaziv: Matematika
Vrsta studija: sveučilišni
Stupanj studija: poslijediplomski doktorski
Akademski / stručni naziv: doktor/doktorica znanosti, područje prirodnih znanosti, polje matematika (dr. sc.)
Vrsta resursaTekst
Opsegix, 112 str.
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2023-03-01 13:08:43