Publication details
Abstracts and keywords
Teoria grup jest dziedziną matematyki mającą szerokie zastosowania w innych naukach jak np. w fizyce, chemii, biologii czy kryptografii. Jest też interesująca sama w sobie i stanowi obszar badań matematyków i algorytmików. Szereg problemów dotyczących teorii grup skończonych to zagadnienia czysto algorytmiczne. Problemy te towarzyszyły teorii grup od samych jej początków sięgających XVIII wieku, patrz [6, 8, 12, 18]. Celem tej monografii jest wprowadzenie do jednego z takich zagadnień, jakim jest obliczenie rzędu grupy permutacji określonej przez skończony układ generatorów. W latach 70. XX wieku matematyk Charles Sims stworzył podstawy metody, która nazywana jest obecnie algorytmem SchreieraSimsa i służy do rozwiązania tego zagadnienia. Algorytm ten oparty jest na twierdzeniu innego matematyka Otto Schreiera z jego pracy z 1927 roku, patrz np. [2, 15, 16]. W ostatnich dziesięcioleciach algorytm ten został włączony do standardowych bibliotek różnych środowisk obliczeniowych i programistycznych takich jak Mathematica. Ponieważ grupy permutacji są częścią ogólnej teorii grup, to w kilku pierwszych rozdziałach zostały przedstawione główne pojęcia i twierdzenia w niej występujące. Niektóre z nich omówione są szczegółowo np. grupy reszt modulo. Osobny rozdział poświęcony jest też samym grupom symetrycznym. Algorytm Schreiera-Simsa przedstawiony jest w rozdziale ostatnim.
Group theory is a branch of mathematics that has many applications in e.g. physics, chemistry, biology or cryptography. It is also an interesting research area for both mathematicians and computer scientists. For instance, computational group theory is a subfield of algebra dealing with analysis and implementation of algorithms about groups. It is an interdisciplinary area between mathematics and computer science. Algorithmic questions permeated group theory from its origins in the 18th century, see [6, 8, 12, 18]. The aim of this book is to introduce a reader to one of such problems. This problem is to find the order of a permutation group given by a set of its generators. In the 1970s Charles Sims created the foundations for what is today called the Schreier-Sims algorithm. It is based on Otto Schreier’s theorem from his 1927 paper. This algorithm is mostly used to calculate the order of a permutation group but the membership problem can be also solved by this method. So you can answer the question whether a particular permutation belongs to the group. In recent decades the algorithm has been implemented in many software systems like SAGE or Mathematica, see also [2, 15, 16]. Since the field of permutation groups is part of general group theory a number of topics are covered in the first three chapters. These include algebraic product of subgroups, Lagrange’s theorem, the construction of a quotient group, direct and semidirect products of groups. One chapter is devoted to permutations and one is about group actions on a set. The Schreier-Sims algorithm is discussed in the last chapter.
