Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Module INF-58-51-M-6

Algorithms and Symmetry (M, 8.0 LP, AUSL)

Module Identification

Module Number Module Name CP (Effort)
INF-58-51-M-6 Algorithms and Symmetry 8.0 CP (240 h)

Basedata

CP, Effort 8.0 CP = 240 h
Position of the semester 1 Sem. in SuSe
Level [6] Master (General)
Language [EN] English
Module Manager
Lecturers
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

Courses

Type/SWS Course Number Title Choice in
Module-Part
Presence-Time /
Self-Study
SL SL is
required for exa.
PL CP Sem.
4V+2U INF-58-51-K-6
Algorithms and Symmetry
P 84 h 156 h
U-Schein
ja PL1 8.0 SuSe
  • About [INF-58-51-K-6]: Title: "Algorithms and Symmetry"; Presence-Time: 84 h; Self-Study: 156 h
  • About [INF-58-51-K-6]: The study achievement "[U-Schein] proof of successful participation in the exercise classes (ungraded)" must be obtained.
    • It is a prerequisite for the examination for PL1.

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.


Contents

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.

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.

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.

Literature

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