CRZP - detail kniha

DZB - Zverejnená bakalárska práca

r-regular sets of permutations

Autor: Kerák, Filip
Školiteľ: Jajcayová, Tatiana
Oponent: Jajcay, Róbert
Škola: Univerzita Komenského v Bratislave FMFI FMFI.KAI
Rok odovzdania: 2020
Počet strán: 49s.
Trvalý odkaz - CRZP: https://opac.crzp.sk/?fn=detailBiblioForm&sid=69B07E5EF4F2B22F0D86B0C7FD1B

Primárny jazyk: angličtina

Typ práce: Bakalárska práca

Študijný odbor: 2511 | aplikovaná informatika

Dátum zaslania práce do CRZP: 01.06.2020

Dátum vytvorenia protokolu: 01.06.2020

Dátum doručenia informácií o licenčnej zmluve: 01.07.2020

Práca je zverejniteľná od: 01.07.2020

Elektronická verzia
: Prehliadať

Abstrakt v primárnom jazyku

In our work we studied the problem of generating r-regular families of permutations. At the beginning we described those families and their relations with different fields in mathematics. Then we showed connection to tripartite graphs and their triangulation. After that we introduced different approaches for generating those families. Since this problem is NP-complete, we used backtracking with different optimizations. Then we designed a system for generating and analyzing of r-regular families. Because the amount of the data and the high time complexity of the algorithm we decided to use concurrency to boost the speed of computations. We implemented parallel processing by using GPU. We also prepared tools for the data analysis. Those tools are completely implemented in python, therefore anyone can use them without the need to have GPU. In the end, we analyzed generated data and stated theorems about impossibility of generating r-regular families just by combining 1-regular families. Keywords: r-regularity, Latin square, concurrency, backtracking, permutations

Abstrakt v sekundárnom jazyku

V našej práci sme študovali problém generovania r-regulárnych rodín permutácií. Na začiatok sme popísali tieto rodiny a ich prepojenie s rôznymi oblasťami matematiky. Ukázali sme prepojenie s tripartitnými grafmi a ich trianguláciou. Následne sme uviedli možné spôsoby generovania. Pretože sa jedná o NP-úplný problém, tak používame backtracking s rôznymi optimalizáciami. Následne sme navrhli systém na generovanie a anlýzu týchto rodín. Jedná sa o veľké množstvo dát a algoritmus má veľkú časovú zložitosť, preto sme sa rozhodli využiť paralelizmus pre urýchlenie výpočtov. Viacvláknové spracovanie sme implementovali s pomocou GPU. Pripravili sme aj nástroje na anlýzu dát. Tieto nástroje sú kompletne implementované v pythone a preto ich môže použiť ktokoľvek aj bez potreby GPU. Nakoniec sme dáta ešte analyzovali a sformulovali sme tvrdenia o nemožnosti generovania všetkých r-regulárnych rodín iba skladaním 1-regulárnych rodín. Kľúčové slová: r-regularita, Latinské štvorce, paralelizmus, backtracking, permutácie