Lehrinhalte
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.
Literature
Lecture Notes;
Köbler, J., Schöning, U., Toran, Jacobo: The Graph Isomorphism Problem Its Structural Complexity
Zusätzliche Informationen
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.
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.
Literature
Lecture Notes;
Köbler, J., Schöning, U., Toran, Jacobo: The Graph Isomorphism Problem Its Structural Complexity
Zusätzliche Informationen
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.
- Lehrende: Markus Anders
- Lehrende: Pascal Schweitzer
- Lehrende: Gelöschter User (TU-ID gelöscht)
Semester: Verão 2021