| dbpedia-owl:abstract
|
- Der Todd-Coxeter-Algorithmus ist ein Algorithmus in der Gruppentheorie, der nach den beiden britischen Mathematikern John Arthur Todd und Harold Scott MacDonald Coxeter benannt ist. Sei eine endliche Gruppe und eine Untergruppe von . Der Todd-Coxeter-Algorithmus ist eine Methode, um die Nebenklassen von in abzuzählen. Zusätzlich lässt sich durch den Algorithmus auch die Operation von auf der Menge der Nebenklassen bestimmen. Durch den Todd-Coxeter-Algorithmus gelangt man mit einer endlichen Zahl von Schritten ans Ziel, die Rechenzeit ist jedoch nicht vorhersagbar. Für eine Berechnung müssen sowohl die Gruppe wie die Untergruppe explizit angegeben sein. Daher nehme man an, sei durch die Erzeugenden und die Relationen konkret dargestellt: . Damit ist als Faktorgruppe realisiert, wobei die freie Gruppe auf der Menge und ein Normalteiler von ist, der enthält. Weiterhin sei vorausgesetzt, dass die Untergruppe durch eine Menge von Wörtern in der freien Gruppe gegeben sei:, deren Bilder in die Untergruppe erzeugen. Beispielhaft sei die Gruppe durch die drei Erzeugenden und die Relationen definiert und als Untergruppe die von erzeugte zyklische Untergruppe:, erzeugt von Da die Operationen auf Nebenklassen bestimmt werden sollen und sich diese als Permutationsdarstellung beschreiben lassen, muss festgesetzt werden, wie diese explizit angegeben werden sollen. Es sei festgelegt, dass von rechts operiert. Die Menge der Rechtsnebenklassen sei als bezeichnet. Um die Operation von auf explizit anzugeben, sei die durch die erzeugenden Elemente induzierte Permutation beschrieben. Für die Operationen auf gelten folgende Regeln: Jede Erzeugende (hier) operiert als Permutation. Die Relation (hier) operiert trivial. Die Erzeugenden von (hier) lassen die Nebenklasse fest. Die Operation auf der Menge der Nebenklassen ist transitiv. Die erste Regel ist eine allgemeine Eigenschaft von Gruppenoperationen, die aus der Invertierbarkeit von Gruppenelementen folgt. Die zweite Regel gilt, da die Relation in das Element repräsentiert, und eigentlich die Gruppe operiert. Die Regeln 3 und 4 sind spezielle Eigenschaften der Operation auf Nebenklassen.
- In group theory, the Todd–Coxeter algorithm, discovered by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group G by generators and relations and a subgroup H of G, the algorithm enumerates the cosets of H on G and describes the permutation representation of G on the space of the cosets. If the order of a group G is relatively small and the subgroup H is known to be uncomplicated (for example, a cyclic group), then the algorithm can be carried out by hand and gives a reasonable description of the group G. Using their algorithm, Coxeter and Todd showed that certain systems of relations between generators of known groups are complete, i.e. constitute systems of defining relations. The Todd–Coxeter algorithm can be applied to infinite groups and is known to terminate in a finite number of steps, provided that the index of H in G is finite. On the other hand, for a general pair consisting of a group presentation and a subgroup, its running time is not bounded by any computable function of the index of the subgroup and the size of the input data.
- En théorie des groupes, une branche des mathématiques, l'algorithme de Todd-Coxeter, découvert en 1936 par J. A. Todd (en) et H. S. M. Coxeter, permet, à partir d'une présentation d'un groupe G, d'énumérer les classes à gauches de G suivant un sous-groupe H et de décrire la représentation de G sur l'ensemble G/H de ces classes.
- В теории групп, алгоритм Тодда — Коксетера, найденный Тоддом и Коксетером в 1936 году, является алгоритмом для решения проблемы перечисления смежных классов. Для конкретных задания группы и подгруппы в, алгоритм перечисляет смежные классы по и описывает представление перестановками на пространстве смежных классов. Если порядок группы является относительно маленьким, и подгруппа является несложной (например, циклическая группа), то алгоритм может быть выполнен вручную и дает удобное описание группы . Используя свой алгоритм, Коксетер и Тодд показали, что конкретные системы соотношений между порождающими элементами некоторых известных групп полны, то есть составляют систему определяющих отношений. Алгоритм Тодда-Коксетера может быть применен к бесконечным группам и завершается после конечного числа шагов при условии, что индекс в конечен. С другой стороны, в общем случае для пары, состоящей из задания группы и подгруппы, количество его шагов не ограничено никакой вычислимой функцией индекса подгруппы и размера данных.
|
| rdfs:comment
|
- Der Todd-Coxeter-Algorithmus ist ein Algorithmus in der Gruppentheorie, der nach den beiden britischen Mathematikern John Arthur Todd und Harold Scott MacDonald Coxeter benannt ist. Sei eine endliche Gruppe und eine Untergruppe von . Der Todd-Coxeter-Algorithmus ist eine Methode, um die Nebenklassen von in abzuzählen. Zusätzlich lässt sich durch den Algorithmus auch die Operation von auf der Menge der Nebenklassen bestimmen.
- In group theory, the Todd–Coxeter algorithm, discovered by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group G by generators and relations and a subgroup H of G, the algorithm enumerates the cosets of H on G and describes the permutation representation of G on the space of the cosets.
- En théorie des groupes, une branche des mathématiques, l'algorithme de Todd-Coxeter, découvert en 1936 par J. A. Todd (en) et H. S. M. Coxeter, permet, à partir d'une présentation d'un groupe G, d'énumérer les classes à gauches de G suivant un sous-groupe H et de décrire la représentation de G sur l'ensemble G/H de ces classes.
- В теории групп, алгоритм Тодда — Коксетера, найденный Тоддом и Коксетером в 1936 году, является алгоритмом для решения проблемы перечисления смежных классов. Для конкретных задания группы и подгруппы в, алгоритм перечисляет смежные классы по и описывает представление перестановками на пространстве смежных классов.
|
