Toggle navigation
Hlavná stránka
Zoznam záznamov
Rozšírené hľadanie
Hľadať
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
1664130