Laskennallinen ryhmäteoria

Laskennallinen ryhmäteoria on matematiikan ja tietojenkäsittelytieteen  risteyksessä oleva tieteenala [1] , joka tutkii ryhmiä tietokoneiden avulla . Se liittyy (useimmiten äärellisten) ryhmien erilaisten ominaisuuksien laskemiseen käytettävien algoritmien ja tietorakenteiden suunnitteluun, analysointiin . Alue on mielenkiintoinen eri näkökulmista tärkeiden ryhmien tutkimiselle, joista ei käsin laskennallisesti saada tietoa.

Tutkimussuunnat

Tärkeimmät tutkimusalueet liittyvät algoritmeihin [1] :

• äärelliset ryhmät [2] ,
• polysykliset ja äärelliset liukenevat ryhmät ,
• permutaatioryhmät [3] ,
• matriisiryhmät,
• esitysteoria .

Tärkeitä algoritmeja

Laskennallisen ryhmäteorian tärkeitä algoritmeja ovat:

• Schreier-Sims-algoritmi permutaatioryhmän järjestyksen löytämiseksi ,
• Todd-Coxeter- algoritmi ja Knuth-Bendix-algoritmi coset-luokkien laskemiseen ,
• kerto-korvausalgoritmi ryhmän satunnaisen elementin löytämiseksi.

Laskennallisten ryhmäteoriaalgoritmien toteutuksia on saatavilla muun muassa kahdessa merkittävässä tietokonealgebrajärjestelmässä , GAP :ssa ja MAGMAssa .

Saavutukset

Jotkut edistysaskeleet liittyvät suoraan laskennalliseen ryhmäteoriaan:

• täydellinen luettelo kaikista äärellisistä ryhmistä, joiden luokka on alle 2000 ,
• kaikkien satunnaisten ryhmien esityksen laskeminen .

Muistiinpanot

1. ↑ 1 2 Seress, s. yksi.
2. ↑ Simit.
3. ↑ Seress.

Kirjallisuus

• Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O'Brien, "Handbook of computational group theory", Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005. ISBN 1-58488-372-3
• Charles C. Sims, "Computation with Finitely-presented Groups", Encyclopedia of Mathematics and its Applications, osa 48, Cambridge University Press, Cambridge, 1994. ISBN 0-521-43213-8
• Ákos Seress, "Permutaatioryhmäalgoritmit", Cambridge Tracts in Mathematics, voi. 152, Cambridge University Press, Cambridge, 2003. ISBN 0-521-66103-X .
• Ohio State Universityn Ákos Seressin alan yleiskatsaus (englanniksi) , joka on laajennettu versio American Mathematical Society Notes -julkaisun artikkelista . Siellä on myös Charles Simsin arvostelu (englanniksi) Rutgersin yliopistosta ja vanhempi (englanniksi) Joachim Neubüser RWTH Aachenista.