Modul

coursework in the tutorial plus oral examination of ca. 20 minutes

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.

none

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

Some basic understanding of group theory and programming are strongly recommended.

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