Permutation Group Algorithms (Cambridge Tracts in Mathematics, Series Number 152) 🔍
Ákos Seress
Cambridge University Press (Virtual Publishing), Cambridge tracts in mathematics, 152, 1, 2003
英语 [en] · PDF · 1.3MB · 2003 · 📘 非小说类图书 · 🚀/duxiu/lgli/lgrs/nexusstc/upload/zlib · Save
描述
Permutation group algorithms are indispensable in the proofs of many deep results, including the construction and study of sporadic finite simple groups. This work describes the theory behind permutation group algorithms, up to the most recent developments based on the classification of finite simple groups. Rigorous complexity estimates, implementation hints, and advanced exercises are included throughout. The central theme is the description of nearly linear time algorithms, which are extremely fast both in terms of asymptotic analysis and of practical running time. The book fills a significant gap in the symbolic computation literature for readers interested in using computers in group theory.
备用文件名
lgli/M_Mathematics/MA_Algebra/MAco_Computational algebra/Seress A. Permutation group algorithms (CUP, 2003)(ISBN 052166103X)(274s)_MAco_.pdf
备用文件名
lgrsnf/M_Mathematics/MA_Algebra/MAco_Computational algebra/Seress A. Permutation group algorithms (CUP, 2003)(ISBN 052166103X)(274s)_MAco_.pdf
备用文件名
nexusstc/Permutation Group Algorithms/e1454b184bb1fd22f3e261d3779c3472.pdf
备用文件名
zlib/Mathematics/Ákos Seress/Permutation group algorithms_503469.pdf
备选作者
Seress, Ákos
备选作者
Akos Seress
备用出版商
Greenwich Medical Media Ltd
备用版本
Cambridge tracts in mathematics -- 152, Cambridge, UK, New York, England, 2003
备用版本
Cambridge University Press, New York, 2003
备用版本
United Kingdom and Ireland, United Kingdom
备用版本
1st edition, July 15, 2002
备用版本
1, FR, 2003
备用版本
2009
元数据中的注释
Kolxo3 -- 25
元数据中的注释
lg71605
元数据中的注释
producers:
Acrobat Distiller 4.0 for Windows
Acrobat Distiller 4.0 for Windows
元数据中的注释
{"edition":"1","isbns":["0511066473","0511546548","052166103X","9780511066474","9780511546549","9780521661034"],"last_page":264,"publisher":"Cambridge University Press","series":"Cambridge tracts in mathematics, 152"}
元数据中的注释
Includes bibliographical references (p. 254-261) and index
备用描述
Cover Page 1
Title 5
ISBN 052166103X 6
Contents (with page links) 7
1 Introduction 11
Acknowledgments 14
1.1. List of Algorithms 14
1.2. Notation and Terminology 16
1.2.1. Groups 17
1.2.2. Permutation Groups 19
1.2.3. Algorithmic Concepts 20
1.2.4. Graphs 21
1.3.Classification of Randomized Algorithms 22
2 Black-Box Groups 26
2.1. Closure Algorithms 28
2.1.1. Orbit Computations 28
2.1.2.Closure of Algebraic Structures 33
The Closure Algorithm 33
Algorithms Based on Normal Closure 33
2.2. Random Elements of Black-Box Groups 34
The Product Replacement Algorithm 37
2.3. Random Subproducts 40
2.3.1. Definition and Basic Properties 40
2.3.2. Reducing the Number of Generators 43
2.3.3. Closure Algorithms without Membership Testing 47
2.3.4. Derived and Lower Central Series 48
2.4. Random Prefixes 50
2.4.1. Definition and Basic Properties 50
2.4.2. Applications 54
Exercises 57
3 Permutation Groups A Complexity Overview 58
3.1. Polynomial-Time Algorithms 58
3.2. Nearly Linear-Time Algorithms 61
3.3. Non-Polynomial-Time Methods 62
4 Bases and Strong Generating Sets 65
4.1. Basic Definitions 65
The Sifting Procedure 66
4.2. The Schreier–Sims Algorithm 67
The Schreier–Sims Algorithm 69
4.3. The Power of Randomization 72
The Random Schreier–Sims Algorithm 74
4.4. Shallow Schreier Trees 74
4.5. Strong Generators in Nearly Linear Time 80
The SGS Construction 80
The Algorithm Solving (4.6) 82
4.5.1. Implementation 85
Exercises 87
5 Further Low-Level Algorithms 89
5.1. Consequences of the Schreier–Sims Method 89
5.1.1. Pointwise Stabilizers 89
5.1.2. Homomorphisms 90
5.1.3. Transitive Constituent and Block Homomorphisms 91
The Block Homomorphism Algorithm 92
5.1.4. Closures and Normal Closures 93
5.2. Working with Base Images 94
5.3. Permutation Groups as Black-Box Groups 103
Representation as a Black-Box Group 103
5.4. Base Change 107
The Exchange of Two Base Points (Deterministic Version) 107
The Exchange of Two Base Points (Las Vegas Version) 108
Base Change by Conjugation 108
5.5. Blocks of Imprimitivity 110
5.5.1. Blocks in Nearly Linear Time 111
5.5.2. The Smallest Block Containing a Given Subset 117
Computation of the Smallest Block Containing... 117
5.5.3. Structure Forests 121
Exercises 121
6 A Library of Nearly Linear-Time Algorithms 124
6.1. Special Case of Group Intersection and pplications 125
6.1.1. Intersection with a Normal Closure 125
6.1.2. Centralizer in the Symmetric Group 127
6.1.3. The Center 130
6.1.4. Centralizer of a Normal Subgroup 130
6.1.5. Core of a Subnormal Subgroup 134
6.2. Composition Series 135
6.2.1. Reduction to the Primitive Case 136
6.2.2. The O’Nan–Scott Theorem 139
6.2.3. Normal Subgroups with Nontrivial Centralizer 143
Computing the Socle of a Frobenius Group 143
Luks’s Algorithm 144
Neumann’s Algorithm (the EARNS Subroutine) 147
6.2.4. Groups with a Unique Nonabelian Minimal Normal Subgroup 149
The Algorithm for Case B of Theorem 6.2.7 150
The Algorithm for Case C(i) 152
The Algorithm for Case C(ii) 153
The Algorithm for Case C(iii) 155
6.2.5. Implementation 156
6.2.6. An Elementary Version 159
Beals’s Algorithm for Groups with Regular Normal Subgroups 160
Beals’s Algorithm for Groups with No Regular Normal Subgroups 160
6.2.7. Chief Series 165
6.3. Quotients with Small Permutation Degree 166
6.3.1. Solvable Radical and p-Core 167
The Algorithms 168
Exercises 169
7 Solvable Permutation Groups 172
7.1. Strong Generators in Solvable Groups 172
The Generalized Normal Closure Algorithm 174
7.2. Power-Conjugate Presentations 175
Conversion to a pcp 176
7.3. Working with Elementary Abelian Layers 176
7.3.1. Sylow Subgroups 177
7.3.2. Conjugacy Classes in Solvable Groups 182
Computation of the Class Representatives 183
Computation of the Centralizers 184
7.4. Two Algorithms for Nilpotent Groups 185
7.4.1. A Fast Nilpotency Test 186
7.4.2. The Upper Central Series in Nilpotent Groups 189
Exercises 191
8 Strong Generating Tests 193
8.1. The Schreier–Todd–Coxeter–Sims Procedure 194
8.1.1. Coset Enumeration 194
8.1.2. Leon’s Algorithm 196
The STCS Algorithm 196
8.2. Sims’s Verify Routine 198
The Verify Routine 200
8.3. Toward Strong Generators by a Las Vegas Algorithm 201
8.4. Short Presentation 207
9 Backtrack Methods 211
9.1. Traditional Backtrack 212
9.1.1. Pruning the Search Tree: Problem-Independent Methods 213
9.1.2. Pruning the Search Tree: Problem-Dependent Methods 215
9.2. The Partition Method 217
9.3. Normalizers 221
9.4. Conjugacy Classes 224
Class Representatives by Random Sampling 224
Representatives in Centralizers of p-Elements 226
Separation of the Solvable Radical 226
Exercises 227
10 Large-Base Groups 228
10.1. Labeled Branchings 228
10.1.1. Construction 232
10.2. Alternating and Symmetric Groups 235
10.2.1. Number Theoretic and Probabilistic Estimates 238
10.2.2. Constructive Recognition: Finding the New Generators 245
10.2.3. Constructive Recognition: The Homomorphism Lambda 249
Summary of the Proof of Theorem 10.2.4(a) 254
Proof of Theorem 10.2.4(b) 254
10.2.4. Constructive Recognition: The Case of Giants 254
10.3. A Randomized Strong Generator Construction 256
Bibliography 264
Index (with page links) 272
Title 5
ISBN 052166103X 6
Contents (with page links) 7
1 Introduction 11
Acknowledgments 14
1.1. List of Algorithms 14
1.2. Notation and Terminology 16
1.2.1. Groups 17
1.2.2. Permutation Groups 19
1.2.3. Algorithmic Concepts 20
1.2.4. Graphs 21
1.3.Classification of Randomized Algorithms 22
2 Black-Box Groups 26
2.1. Closure Algorithms 28
2.1.1. Orbit Computations 28
2.1.2.Closure of Algebraic Structures 33
The Closure Algorithm 33
Algorithms Based on Normal Closure 33
2.2. Random Elements of Black-Box Groups 34
The Product Replacement Algorithm 37
2.3. Random Subproducts 40
2.3.1. Definition and Basic Properties 40
2.3.2. Reducing the Number of Generators 43
2.3.3. Closure Algorithms without Membership Testing 47
2.3.4. Derived and Lower Central Series 48
2.4. Random Prefixes 50
2.4.1. Definition and Basic Properties 50
2.4.2. Applications 54
Exercises 57
3 Permutation Groups A Complexity Overview 58
3.1. Polynomial-Time Algorithms 58
3.2. Nearly Linear-Time Algorithms 61
3.3. Non-Polynomial-Time Methods 62
4 Bases and Strong Generating Sets 65
4.1. Basic Definitions 65
The Sifting Procedure 66
4.2. The Schreier–Sims Algorithm 67
The Schreier–Sims Algorithm 69
4.3. The Power of Randomization 72
The Random Schreier–Sims Algorithm 74
4.4. Shallow Schreier Trees 74
4.5. Strong Generators in Nearly Linear Time 80
The SGS Construction 80
The Algorithm Solving (4.6) 82
4.5.1. Implementation 85
Exercises 87
5 Further Low-Level Algorithms 89
5.1. Consequences of the Schreier–Sims Method 89
5.1.1. Pointwise Stabilizers 89
5.1.2. Homomorphisms 90
5.1.3. Transitive Constituent and Block Homomorphisms 91
The Block Homomorphism Algorithm 92
5.1.4. Closures and Normal Closures 93
5.2. Working with Base Images 94
5.3. Permutation Groups as Black-Box Groups 103
Representation as a Black-Box Group 103
5.4. Base Change 107
The Exchange of Two Base Points (Deterministic Version) 107
The Exchange of Two Base Points (Las Vegas Version) 108
Base Change by Conjugation 108
5.5. Blocks of Imprimitivity 110
5.5.1. Blocks in Nearly Linear Time 111
5.5.2. The Smallest Block Containing a Given Subset 117
Computation of the Smallest Block Containing... 117
5.5.3. Structure Forests 121
Exercises 121
6 A Library of Nearly Linear-Time Algorithms 124
6.1. Special Case of Group Intersection and pplications 125
6.1.1. Intersection with a Normal Closure 125
6.1.2. Centralizer in the Symmetric Group 127
6.1.3. The Center 130
6.1.4. Centralizer of a Normal Subgroup 130
6.1.5. Core of a Subnormal Subgroup 134
6.2. Composition Series 135
6.2.1. Reduction to the Primitive Case 136
6.2.2. The O’Nan–Scott Theorem 139
6.2.3. Normal Subgroups with Nontrivial Centralizer 143
Computing the Socle of a Frobenius Group 143
Luks’s Algorithm 144
Neumann’s Algorithm (the EARNS Subroutine) 147
6.2.4. Groups with a Unique Nonabelian Minimal Normal Subgroup 149
The Algorithm for Case B of Theorem 6.2.7 150
The Algorithm for Case C(i) 152
The Algorithm for Case C(ii) 153
The Algorithm for Case C(iii) 155
6.2.5. Implementation 156
6.2.6. An Elementary Version 159
Beals’s Algorithm for Groups with Regular Normal Subgroups 160
Beals’s Algorithm for Groups with No Regular Normal Subgroups 160
6.2.7. Chief Series 165
6.3. Quotients with Small Permutation Degree 166
6.3.1. Solvable Radical and p-Core 167
The Algorithms 168
Exercises 169
7 Solvable Permutation Groups 172
7.1. Strong Generators in Solvable Groups 172
The Generalized Normal Closure Algorithm 174
7.2. Power-Conjugate Presentations 175
Conversion to a pcp 176
7.3. Working with Elementary Abelian Layers 176
7.3.1. Sylow Subgroups 177
7.3.2. Conjugacy Classes in Solvable Groups 182
Computation of the Class Representatives 183
Computation of the Centralizers 184
7.4. Two Algorithms for Nilpotent Groups 185
7.4.1. A Fast Nilpotency Test 186
7.4.2. The Upper Central Series in Nilpotent Groups 189
Exercises 191
8 Strong Generating Tests 193
8.1. The Schreier–Todd–Coxeter–Sims Procedure 194
8.1.1. Coset Enumeration 194
8.1.2. Leon’s Algorithm 196
The STCS Algorithm 196
8.2. Sims’s Verify Routine 198
The Verify Routine 200
8.3. Toward Strong Generators by a Las Vegas Algorithm 201
8.4. Short Presentation 207
9 Backtrack Methods 211
9.1. Traditional Backtrack 212
9.1.1. Pruning the Search Tree: Problem-Independent Methods 213
9.1.2. Pruning the Search Tree: Problem-Dependent Methods 215
9.2. The Partition Method 217
9.3. Normalizers 221
9.4. Conjugacy Classes 224
Class Representatives by Random Sampling 224
Representatives in Centralizers of p-Elements 226
Separation of the Solvable Radical 226
Exercises 227
10 Large-Base Groups 228
10.1. Labeled Branchings 228
10.1.1. Construction 232
10.2. Alternating and Symmetric Groups 235
10.2.1. Number Theoretic and Probabilistic Estimates 238
10.2.2. Constructive Recognition: Finding the New Generators 245
10.2.3. Constructive Recognition: The Homomorphism Lambda 249
Summary of the Proof of Theorem 10.2.4(a) 254
Proof of Theorem 10.2.4(b) 254
10.2.4. Constructive Recognition: The Case of Giants 254
10.3. A Randomized Strong Generator Construction 256
Bibliography 264
Index (with page links) 272
备用描述
Cover Page......Page 1
Title......Page 5
ISBN 052166103X......Page 6
Contents (with page links)......Page 7
1 Introduction......Page 11
1.1. List of Algorithms......Page 14
1.2. Notation and Terminology......Page 16
1.2.1. Groups......Page 17
1.2.2. Permutation Groups......Page 19
1.2.3. Algorithmic Concepts......Page 20
1.2.4. Graphs......Page 21
1.3.Classification of Randomized Algorithms......Page 22
2 Black-Box Groups......Page 26
2.1.1. Orbit Computations......Page 28
Algorithms Based on Normal Closure......Page 33
2.2. Random Elements of Black-Box Groups......Page 34
The Product Replacement Algorithm......Page 37
2.3.1. Definition and Basic Properties......Page 40
2.3.2. Reducing the Number of Generators......Page 43
2.3.3. Closure Algorithms without Membership Testing......Page 47
2.3.4. Derived and Lower Central Series......Page 48
2.4.1. Definition and Basic Properties......Page 50
2.4.2. Applications......Page 54
Exercises......Page 57
3.1. Polynomial-Time Algorithms......Page 58
3.2. Nearly Linear-Time Algorithms......Page 61
3.3. Non-Polynomial-Time Methods......Page 62
4.1. Basic Definitions......Page 65
The Sifting Procedure......Page 66
4.2. The Schreier–Sims Algorithm......Page 67
The Schreier–Sims Algorithm......Page 69
4.3. The Power of Randomization......Page 72
4.4. Shallow Schreier Trees......Page 74
The SGS Construction......Page 80
The Algorithm Solving (4.6)......Page 82
4.5.1. Implementation......Page 85
Exercises......Page 87
5.1.1. Pointwise Stabilizers......Page 89
5.1.2. Homomorphisms......Page 90
5.1.3. Transitive Constituent and Block Homomorphisms......Page 91
The Block Homomorphism Algorithm......Page 92
5.1.4. Closures and Normal Closures......Page 93
5.2. Working with Base Images......Page 94
Representation as a Black-Box Group......Page 103
The Exchange of Two Base Points (Deterministic Version)......Page 107
Base Change by Conjugation......Page 108
5.5. Blocks of Imprimitivity......Page 110
5.5.1. Blocks in Nearly Linear Time......Page 111
Computation of the Smallest Block Containing.........Page 117
Exercises......Page 121
6 A Library of Nearly Linear-Time Algorithms......Page 124
6.1.1. Intersection with a Normal Closure......Page 125
6.1.2. Centralizer in the Symmetric Group......Page 127
6.1.4. Centralizer of a Normal Subgroup......Page 130
6.1.5. Core of a Subnormal Subgroup......Page 134
6.2. Composition Series......Page 135
6.2.1. Reduction to the Primitive Case......Page 136
6.2.2. The O’Nan–Scott Theorem......Page 139
Computing the Socle of a Frobenius Group......Page 143
Luks’s Algorithm......Page 144
Neumann’s Algorithm (the EARNS Subroutine)......Page 147
6.2.4. Groups with a Unique Nonabelian Minimal Normal Subgroup......Page 149
The Algorithm for Case B of Theorem 6.2.7......Page 150
The Algorithm for Case C(i)......Page 152
The Algorithm for Case C(ii)......Page 153
The Algorithm for Case C(iii)......Page 155
6.2.5. Implementation......Page 156
6.2.6. An Elementary Version......Page 159
Beals’s Algorithm for Groups with No Regular Normal Subgroups......Page 160
6.2.7. Chief Series......Page 165
6.3. Quotients with Small Permutation Degree......Page 166
6.3.1. Solvable Radical and p-Core......Page 167
The Algorithms......Page 168
Exercises......Page 169
7.1. Strong Generators in Solvable Groups......Page 172
The Generalized Normal Closure Algorithm......Page 174
7.2. Power-Conjugate Presentations......Page 175
7.3. Working with Elementary Abelian Layers......Page 176
7.3.1. Sylow Subgroups......Page 177
7.3.2. Conjugacy Classes in Solvable Groups......Page 182
Computation of the Class Representatives......Page 183
Computation of the Centralizers......Page 184
7.4. Two Algorithms for Nilpotent Groups......Page 185
7.4.1. A Fast Nilpotency Test......Page 186
7.4.2. The Upper Central Series in Nilpotent Groups......Page 189
Exercises......Page 191
8 Strong Generating Tests......Page 193
8.1.1. Coset Enumeration......Page 194
The STCS Algorithm......Page 196
8.2. Sims’s Verify Routine......Page 198
The Verify Routine......Page 200
8.3. Toward Strong Generators by a Las Vegas Algorithm......Page 201
8.4. Short Presentation......Page 207
9 Backtrack Methods......Page 211
9.1. Traditional Backtrack......Page 212
9.1.1. Pruning the Search Tree: Problem-Independent Methods......Page 213
9.1.2. Pruning the Search Tree: Problem-Dependent Methods......Page 215
9.2. The Partition Method......Page 217
9.3. Normalizers......Page 221
Class Representatives by Random Sampling......Page 224
Separation of the Solvable Radical......Page 226
Exercises......Page 227
10.1. Labeled Branchings......Page 228
10.1.1. Construction......Page 232
10.2. Alternating and Symmetric Groups......Page 235
10.2.1. Number Theoretic and Probabilistic Estimates......Page 238
10.2.2. Constructive Recognition: Finding the New Generators......Page 245
10.2.3. Constructive Recognition: The Homomorphism Lambda......Page 249
10.2.4. Constructive Recognition: The Case of Giants......Page 254
10.3. A Randomized Strong Generator Construction......Page 256
Bibliography......Page 264
Index (with page links)......Page 272
Title......Page 5
ISBN 052166103X......Page 6
Contents (with page links)......Page 7
1 Introduction......Page 11
1.1. List of Algorithms......Page 14
1.2. Notation and Terminology......Page 16
1.2.1. Groups......Page 17
1.2.2. Permutation Groups......Page 19
1.2.3. Algorithmic Concepts......Page 20
1.2.4. Graphs......Page 21
1.3.Classification of Randomized Algorithms......Page 22
2 Black-Box Groups......Page 26
2.1.1. Orbit Computations......Page 28
Algorithms Based on Normal Closure......Page 33
2.2. Random Elements of Black-Box Groups......Page 34
The Product Replacement Algorithm......Page 37
2.3.1. Definition and Basic Properties......Page 40
2.3.2. Reducing the Number of Generators......Page 43
2.3.3. Closure Algorithms without Membership Testing......Page 47
2.3.4. Derived and Lower Central Series......Page 48
2.4.1. Definition and Basic Properties......Page 50
2.4.2. Applications......Page 54
Exercises......Page 57
3.1. Polynomial-Time Algorithms......Page 58
3.2. Nearly Linear-Time Algorithms......Page 61
3.3. Non-Polynomial-Time Methods......Page 62
4.1. Basic Definitions......Page 65
The Sifting Procedure......Page 66
4.2. The Schreier–Sims Algorithm......Page 67
The Schreier–Sims Algorithm......Page 69
4.3. The Power of Randomization......Page 72
4.4. Shallow Schreier Trees......Page 74
The SGS Construction......Page 80
The Algorithm Solving (4.6)......Page 82
4.5.1. Implementation......Page 85
Exercises......Page 87
5.1.1. Pointwise Stabilizers......Page 89
5.1.2. Homomorphisms......Page 90
5.1.3. Transitive Constituent and Block Homomorphisms......Page 91
The Block Homomorphism Algorithm......Page 92
5.1.4. Closures and Normal Closures......Page 93
5.2. Working with Base Images......Page 94
Representation as a Black-Box Group......Page 103
The Exchange of Two Base Points (Deterministic Version)......Page 107
Base Change by Conjugation......Page 108
5.5. Blocks of Imprimitivity......Page 110
5.5.1. Blocks in Nearly Linear Time......Page 111
Computation of the Smallest Block Containing.........Page 117
Exercises......Page 121
6 A Library of Nearly Linear-Time Algorithms......Page 124
6.1.1. Intersection with a Normal Closure......Page 125
6.1.2. Centralizer in the Symmetric Group......Page 127
6.1.4. Centralizer of a Normal Subgroup......Page 130
6.1.5. Core of a Subnormal Subgroup......Page 134
6.2. Composition Series......Page 135
6.2.1. Reduction to the Primitive Case......Page 136
6.2.2. The O’Nan–Scott Theorem......Page 139
Computing the Socle of a Frobenius Group......Page 143
Luks’s Algorithm......Page 144
Neumann’s Algorithm (the EARNS Subroutine)......Page 147
6.2.4. Groups with a Unique Nonabelian Minimal Normal Subgroup......Page 149
The Algorithm for Case B of Theorem 6.2.7......Page 150
The Algorithm for Case C(i)......Page 152
The Algorithm for Case C(ii)......Page 153
The Algorithm for Case C(iii)......Page 155
6.2.5. Implementation......Page 156
6.2.6. An Elementary Version......Page 159
Beals’s Algorithm for Groups with No Regular Normal Subgroups......Page 160
6.2.7. Chief Series......Page 165
6.3. Quotients with Small Permutation Degree......Page 166
6.3.1. Solvable Radical and p-Core......Page 167
The Algorithms......Page 168
Exercises......Page 169
7.1. Strong Generators in Solvable Groups......Page 172
The Generalized Normal Closure Algorithm......Page 174
7.2. Power-Conjugate Presentations......Page 175
7.3. Working with Elementary Abelian Layers......Page 176
7.3.1. Sylow Subgroups......Page 177
7.3.2. Conjugacy Classes in Solvable Groups......Page 182
Computation of the Class Representatives......Page 183
Computation of the Centralizers......Page 184
7.4. Two Algorithms for Nilpotent Groups......Page 185
7.4.1. A Fast Nilpotency Test......Page 186
7.4.2. The Upper Central Series in Nilpotent Groups......Page 189
Exercises......Page 191
8 Strong Generating Tests......Page 193
8.1.1. Coset Enumeration......Page 194
The STCS Algorithm......Page 196
8.2. Sims’s Verify Routine......Page 198
The Verify Routine......Page 200
8.3. Toward Strong Generators by a Las Vegas Algorithm......Page 201
8.4. Short Presentation......Page 207
9 Backtrack Methods......Page 211
9.1. Traditional Backtrack......Page 212
9.1.1. Pruning the Search Tree: Problem-Independent Methods......Page 213
9.1.2. Pruning the Search Tree: Problem-Dependent Methods......Page 215
9.2. The Partition Method......Page 217
9.3. Normalizers......Page 221
Class Representatives by Random Sampling......Page 224
Separation of the Solvable Radical......Page 226
Exercises......Page 227
10.1. Labeled Branchings......Page 228
10.1.1. Construction......Page 232
10.2. Alternating and Symmetric Groups......Page 235
10.2.1. Number Theoretic and Probabilistic Estimates......Page 238
10.2.2. Constructive Recognition: Finding the New Generators......Page 245
10.2.3. Constructive Recognition: The Homomorphism Lambda......Page 249
10.2.4. Constructive Recognition: The Case of Giants......Page 254
10.3. A Randomized Strong Generator Construction......Page 256
Bibliography......Page 264
Index (with page links)......Page 272
备用描述
Permutation group algorithms are one of the workhorses of symbolic algebra systems computing with groups. They played an indispensable role in the proof of many deep results, including the construction and study of sporadic finite simple groups. This book describes the theory behind permutation group algorithms, including developments based on the classification of finite simple groups. Rigorous complexity estimates, implementation hints, and advanced exercises are included throughout. The central theme is the description of nearly linear time algorithms, which are extremely fast both in terms of asymptotic analysis and of practical running time. A significant part of the permutation group library of the computational group algebra system GAP is based on nearly linear time algorithms. The book fills a significant gap in the symbolic computation literature. It is recommended for everyone interested in using computers in group theory, and is suitable for advanced graduate courses.
备用描述
"The central theme is the description of nearly linear-time algorithms, which are extremely fast in terms of both asymptotic analysis and practical running time. A significant part of the permutation group library of the computational group algebra system GAP is based on nearly linear-time algorithms." "The book fills a significant gap in the symbolic computation literature. It is recommended for everyone interested in using computers in group theory and is suitable for advanced graduate courses."--BOOK JACKET
备用描述
Permutation group algorithms were instrumental in the proof of many deep results. This book describes the theory, up to the most recent developments, and includes hints for implementation and advanced exercises. It is recommended for everyone interested in using computers in group theory, and is suitable for advanced graduate courses
备用描述
Computational group theory (CGT) is a subfield of symbolic algebra; it deals with the design, analysis, and implementation of algorithms for manipulating groups.
开源日期
2009-07-20
🚀 快速下载
成为会员以支持书籍、论文等的长期保存。为了感谢您对我们的支持，您将获得高速下载权益。❤️
如果您在本月捐款，您将获得双倍的快速下载次数。
🐢 低速下载
由可信的合作方提供。 更多信息请参见常见问题解答。 （可能需要验证浏览器——无限次下载！）
- 低速服务器（合作方提供） #1 （稍快但需要排队）
- 低速服务器（合作方提供） #2 （稍快但需要排队）
- 低速服务器（合作方提供） #3 （稍快但需要排队）
- 低速服务器（合作方提供） #4 （稍快但需要排队）
- 低速服务器（合作方提供） #5 （无需排队，但可能非常慢）
- 低速服务器（合作方提供） #6 （无需排队，但可能非常慢）
- 低速服务器（合作方提供） #7 （无需排队，但可能非常慢）
- 低速服务器（合作方提供） #8 （无需排队，但可能非常慢）
- 低速服务器（合作方提供） #9 （无需排队，但可能非常慢）
- 下载后： 在我们的查看器中打开
所有选项下载的文件都相同，应该可以安全使用。即使这样，从互联网下载文件时始终要小心。例如，确保您的设备更新及时。
外部下载
-
对于大文件，我们建议使用下载管理器以防止中断。
推荐的下载管理器：JDownloader -
您将需要一个电子书或 PDF 阅读器来打开文件，具体取决于文件格式。
推荐的电子书阅读器：Anna的档案在线查看器、ReadEra和Calibre -
使用在线工具进行格式转换。
推荐的转换工具：CloudConvert和PrintFriendly -
您可以将 PDF 和 EPUB 文件发送到您的 Kindle 或 Kobo 电子阅读器。
推荐的工具：亚马逊的“发送到 Kindle”和djazz 的“发送到 Kobo/Kindle” -
支持作者和图书馆
✍️ 如果您喜欢这个并且能够负担得起，请考虑购买原版，或直接支持作者。
📚 如果您当地的图书馆有这本书，请考虑在那里免费借阅。
下面的文字仅以英文继续。
总下载量：
“文件的MD5”是根据文件内容计算出的哈希值，并且基于该内容具有相当的唯一性。我们这里索引的所有影子图书馆都主要使用MD5来标识文件。
一个文件可能会出现在多个影子图书馆中。有关我们编译的各种数据集的信息，请参见数据集页面。
有关此文件的详细信息，请查看其JSON 文件。 Live/debug JSON version. Live/debug page.