Original title: Algoritmy pro permutační grupy
Translated title: Permutation group algorithms
Authors: Plšková, Petra ; Bulín, Jakub (advisor) ; Růžička, Pavel (referee)
Document type: Bachelor's theses
Year: 2020
Language: slo
Abstract: [eng] [cze]
The Schreier Sims algorithm is a fundamental algorithm for permutation groups. Its purpose is to find a base and a strong generating set. Representation of a group using a base and a strong generating set is the core of many other algorithms. The aim of the thesis is to give the reader a detailed description of the algorithm. We present its pseudocode together with the pseudocode of its subroutines. We analyze the complexity with respect to the given pseudocode. Similarly, we describe an efficient, Monte Carlo version of the Schreier Sims algorithm whose time complexity is nearly linear. We give a detailed description of two improved algorithms for subroutines on which this version is based. We introduce the theoretical framework needed to support the correctness of both the deterministic and the probabilistic version of the algorithm. 1 Schreier Simsov algoritmus je základným algoritmom pre permutačné grupy. Jeho úlohou je nájsť bázu a silne generujúcu množinu. Reprezentácia grupy pomocou bázy a silne generujúcej množiny je základom pre veľa ďalších algoritmov. Cieľom tejto práce je poskytnúť čitateľovi detailnejší popis tohto algoritmu. V práci uvedieme jeho pseudo- kód, vrátane pseudokódov algoritmov riešiacich čiastkové problémy. Časovú a priestorovú zložitosť spočítame vzhľadom k uvedeným pseudokódom. Obdobne popíšeme efektívnu Monte Carlo verziu Schreier Simsovho algoritmu, ktorej časová zložitosť je skoro line- árna. Detailne popíšeme dve vylepšenia algoritmov pre čiastkové problémy, na ktorých je táto verzia založená. Korektnosť deterministickej aj Monte Carlo verzie je podložená teoretickými poznatkami. 1
Keywords: base; Monte Carlo algorithm; permutation group; Schreier Sims algorithm; strong generating set; báza; Monte Carlo algoritmus; permutačná grupa; Schreier Simsov algortimus; silne generujúca množina

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/121707

Permalink: http://www.nusl.cz/ntk/nusl-435609


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses