Contents of the lecture are the highlights of this research, starting with early results from the 1970s up to current results. Each of these results is embedded in an introduction to the techniques used and their context.
Algorithms and Symmetry (M, 8.0 LP, AUSL)
|Module Number||Module Name||CP (Effort)|
|INF-58-51-M-6||Algorithms and Symmetry||8.0 CP (240 h)|
|CP, Effort||8.0 CP = 240 h|
|Position of the semester||1 Sem. in SuSe|
|Level|| Master (General)|
|Area of study||[INF-ALG] Algorithmics and Deduction|
|Reference course of study||[INF-88.79-SG] M.Sc. Computer Science|
|Livecycle-State||[AUSL] Phase-out period|
|Type/SWS||Course Number||Title||Choice in |
|SL||SL is |
required for exa.
Algorithms and Symmetry
|P||84 h||156 h||
Examination achievement PL1
- Form of examination: oral examination (20-60 Min.)
- Examination Frequency: Examination only within the course
- Examination number: 65851 ("Algorithms and Symmetry")
Evaluation of grades
The grade of the module examination is also the module grade.
The lecture deals with symmetry in the algorithmic context. On the one hand, this implies the algorithmic use of symmetries to accelerate combinatorial algorithms (such as to reduce search spaces or to enumerate combinatorial objects). On the other hand, algorithms are developed for detecting symmetries of combinatorial objects. Central to this is the graph isomorphism problem, one of the most important open problems of theoretical computer science. From a practical and theoretical point of view, it is equivalent to the problem of calculating all the symmetries of a combinatorial object. Over the past 40 years, there has been a huge variety of results, based on techniques from various areas of theoretical computer science and discrete mathematics.
Competencies / intended learning achievements
After successfully completing the module, students will be able to
- explain essential knowledge in the field of symmetry detection and symmetry usage, including common techniques and approaches,
- apply advanced techniques from different areas of theoretical computer science (algorithmics, logic, complexity theory),
- apply advanced techniques from related fields of mathematics (graph theory, algorithmic group theory),
- combine and apply these techniques in the context of a current research topic,
- use symmetries in algorithmic contexts.
Lecture slides and original literatur
Requirements for attendance of the module (informal)None
Requirements for attendance of the module (formal)None
References to Module / Module Number [INF-58-51-M-6]
|Course of Study||Section||Choice/Obligation|
|[INF-88.79-SG] M.Sc. Computer Science||[Specialisation] Specialization 1||[WP] Compulsory Elective|