Search

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

Genetic algorithms (GA) are search and optimization heuristic population-based methods which are inspired by the natural evolution process. In this talk, we will present a method of constructing incidence matrices of block designs combining the method of construction with orbit matrices and a modified genetic algorithm.

In this talk, we present a method of constructing incidence matrices of block designs combining the method of construction with orbit matrices and a modified genetic algorithm. With this method we managed to find some new non-isomorphic S(2, 5, 45) designs.

Genetic algorithms (GA) are search and optimization heuristic population-based methods which are inspired by the natural evolution process. In this talk, we will present a method of constructing incidence matrices of block designs combining the method of construction with orbit matrices and a modified genetic algorithm. With this method we managed to find some new non-isomorphic S(2, 5, 45) designs.

U ovom diplomskom radu bavimo se konstrukcijom LDPC (eng. low-density parity-check) kodova iz matrice susjedstva μ−geodetskih grafova dobivenih pomoću (v, k, )−BIBD-ova. U uvodnom poglavlju definiraju se osnovni pojmovi, poput incidencijskih struktura, dizajna, BIBD-a, kodova i osnovni pojmovi teorije grafova koji se koriste u nastavku rada. Uvodi se pojam LDPC kodova, primjer za jednu metodu dekodiranja tih kodova te način zadavanja LDPC kodova pomoću Tannerovog grafa. U narednom poglavlju uvodi se pojam μ−geodetskog grafa te opisujemo način na koji iz nekog grafa možemo konstruirati geodetski graf te koji su potrebni uvjeti na takav graf. Iduće poglavlje opisuje konstrukciju μ− geodetskog grafa iz blokovnog dizajna, tj. modificiranu opću konstrukciju iz prethodnog poglavlja. Nadalje, na konkretnom primjeru (7, 3, 1)−BIBD-a konstruiran je geodetski graf te je u programskom paketu GAP iz matrice susjedstva tog grafa konstruiran LDPC kod. Navode se neka svojstva LDPC kodova dobivenih iz μ−geodetskih grafova te su konstruirani LDPC kodovi iz (17, 4, 3)−BIBD-ova.

Parcijalne diferencijalne jednadžbe (PDJ) opisuju razne fizikalne procese u prirodi, pri čemu funkcije koje se promatraju mogu zavisiti o dvije ili nekoliko nezavisnih varijabli. Jedna od varijabli može biti vrijeme t, odnosno, jedna ili više prostornih varijabli. Uobičajeno se pri rješavanju problema s PDJ koristi onaj koordinatni sustav u kojem će PDJ biti jednostavnija a time i lakše rješiva. Također, treba voditi računa da se pripadajući inicijalno-rubni uvjeti pojednostave. U prvom dijelu rada izvodimo matematički model koji opisuje oscilacije tanke elastične membrane u vremenu. Time dobivamo PDJ drugog reda u dvije dimenzije s inicijalnim i rubnim uvjetima. Rješenje problema je funkcija otklona = ( , , ). Problem prevodimo u polarne koordinate (r, Ө) te u sljedećem dijelu rada konstruiramo rješenje metodom separacije varijabli za zadane početne i rubne uvjete, te za radijalno simetrični slučaj vibracija membrane. U praktičnom dijelu zadatka korištenjem programa Wolfram Research, Inc., Mathematica, Version 9.0, Champaign, IL (2012), konstruirana su rješenja za dva slučaja radijalno simetričnog vibriranja kružne membrane, s homogenim rubnim i različitim početnim uvjetima.