Косет санау – топтар теориясының маңызды мәселесі. Бұл топтың ішкі тобының косеттерін есептеу және топтың ретін анықтауға көмектеседі. Компьютерлік әдіс қолданылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Математикада косет санағы – берілген презентация бойынша G тобының H кіші тобының косеттерін санау мәселесі. Қосалқы нәтиже ретінде H косеттерінде G үшін пермутациялық бейнелеу алынады. Егер H белгілі бір шекті ретіне ие болса, косет санағы G тобының ретін де анықтайды. Шағын топтар үшін косет санауын қолмен жүргізу мүмкін. Дегенмен, үлкен топтар үшін бұл көп уақытты алады және қателерге бейім, сондықтан көбінесе компьютер арқылы орындалады. Косет санағы есептеулік топтар теориясының негізгі мәселелерінің бірі саналады. Косет санаудың бастапқы алгоритмін Джон Артур Тодд және Х. С. М. Коксетер ойлап тапқан. Түпнұсқа Тодд-Коксетер алгоритміне түрлі жақсартулар енгізілді, оның ішінде В. Фелш және HLT (Хасельгроув, Лич және Троттер) ұсынған классикалық стратегиялар бар. Осы стратегиялардың жетілдірілген нұсқалары ACE веб-сайтында қолжетімді. Кнут-Бендикс алгоритмі де косет санауын жүзеге асыра алады, ал Тодд-Коксетер алгоритмінен айырмашылығы, ол кейде шексіз топтар үшін сөз мәселесін шеше алады. Косет санаушын жасаудағы негізгі практикалық қиындық – процесті аяқтау үшін қанша жад немесе уақыт қажет болатынын болжаудың қиын немесе мүмкін еместігі. Егер топ шекті болса, онда оның косет санағы сөзсіз аяқталуы керек, бірақ бұл кез келген уақытқа созылуы мүмкін және топ тривиалды болса да, шексіз жадты қажет етуі мүмкін. Қолданылатын алгоритмге байланысты, топты өзгерте бермейтін презентацияға енгізілген шағын өзгерістер де санауды аяқтау үшін қажетті уақыт немесе жад көлеміне елеулі әсер етуі мүмкін. Мұндай мінез-құлық топтар үшін сөз мәселесінің шешілмейтінімен байланысты. Косет санауына кіріспе Ротманның топтар теориясы бойынша жазған кітабында келтірілген. Дұрыстығы, тиімділігі және практикалық іске асыруы туралы толыққанды ақпаратты Симс пен Холт және басқа авторлардың кітаптарынан табуға болады.
In mathematics, coset enumeration is the problem of counting the cosets of a subgroup H of a group G given in terms of a presentation. As a by product, one obtains a permutation representation for G on the cosets of H. If H has a known finite order, coset enumeration gives the order of G as well. For small groups it is sometimes possible to perform a coset enumeration by hand. However, for large groups it is time consuming and error prone, so it is usually carried out by computer. Coset enumeration is usually considered to be one of the fundamental problems in computational group theory. The original algorithm for coset enumeration was invented by John Arthur Todd and H. S. M. Coxeter. Various improvements to the original Todd–Coxeter algorithm have been suggested, notably the classical strategies of V. Felsch and HLT (Haselgrove, Leech and Trotter). A practical implementation of these strategies with refinements is available at the ACE website. The Knuth–Bendix algorithm also can perform coset enumeration, and unlike the Todd–Coxeter algorithm, it can sometimes solve the word problem for infinite groups. The main practical difficulties in producing a coset enumerator are that it is difficult or impossible to predict how much memory or time will be needed to complete the process. If a group is finite, then its coset enumeration must terminate eventually, although it may take arbitrarily long and use an arbitrary amount of memory, even if the group is trivial. Depending on the algorithm used, it may happen that making small changes to the presentation that do not change the group nevertheless have a large impact on the amount of time or memory needed to complete the enumeration. These behaviours are a consequence of the unsolvability of the word problem for groups. A gentle introduction to coset enumeration is given in Rotman's text on group theory. More detailed information on correctness, efficiency, and practical implementation can be found in the books by Sims and Holt et al.