Modul
Computational Group Theory [M-MATH-106240]
Credits
8Recurrence
UnregelmäßigDuration
1 SemesterLanguage
EnglishLevel
4Version
1Responsible
Organisation
- KIT-Fakultät für Mathematik
Part of
Bricks
Identifier | Name | LP |
---|---|---|
T-MATH-112669 | Computational Group Theory exam | 6 |
T-MATH-112670 | Computational Group Theory Tutorial | 2 |
Competence Certificate
coursework in the tutorial plus oral examination of ca. 20 minutes
Competence Goal
The aim of the course is to give a gentle introduction to group theory from a computational point of view. The students will learn not only the mathematical theory, but also how to think in terms of the computational feasibility. As a result students will develop computational understanding for questions within group theory.
After successful participation students can
- understand the difference between construction and definition by property
- understand how scaling of the computational problems influences the choice of algorithms and data structures
- choose the correct algorithms and data structures balancing speed and storage to obtain computational feasibilty
- exploit the structure of permutation groups to quickly find (some or all) elements satisfying requested properties.
- understand the basics of the theory of automata and their role for computation in finitely presented groups
- use string-rewriting algorithms to potentially solve the word problem in (some) finitely presented groups.
Prerequisites
none
Content
1. Group actions, orbits, stabilizers, Schreier vectors
2. Permutation groups, bases, Stabilizer chains, Schreier-Sims algorithm.
3. Broad overview of transitive groups, primitive groups
4. Finitely presented groups, their homomorphisms, quotients
5. Formal languages, and rewriting systems
6. Knuth-Bendix completion
7. Automata for problems in finitely presented groups
8. Coset enumeration, subgroups and their presentation
Recommendation
Some basic understanding of group theory and programming are strongly recommended.
Workload
total workload: 240 hours
Attendance: 90 h
- lectures and tutorials including the examination
Self studies: 150 h
- follow-up and deepening of the course content,
- work on problem sheets and programming tasks
- literature study and internet research on the course content,
- preparation for the module examination