Digitale Lehre
Hochgeladenes Video mit Sprechstunde
Lehrinhalte
Die Vorlesung beschäftigt sich mit Symmetrie im algorithmischen Kontext. Einerseits bedeutet dies die algorithmische Verwendung von Symmetrien zum Beschleunigen von kombinatorischen Algorithmen (etwa zur Reduktion von Suchräumen oder beim Aufzählen kombinatorischer Objekte). Andererseits werden Algorithmen zum Finden von Symmetrien kombinatorischer Objekte entwickelt. Hierfür zentral ist das Graphenisomorphieproblem, eines der wichtigsten offenen Probleme der theoretischen Informatik. Es ist aus praktischer und theoretischer Sicht äquivalent zum Problem der Berechnung aller Symmetrien eines kombinatorischen Objektes. Im Laufe der vergangenen 40 Jahre hat es eine Fülle von Teilergebnissen ganz unterschiedlicher Natur gegeben, die auf Techniken aus verschiedenen Teilgebieten der theoretischen Informatik und der diskreten Mathematik beruhen. Inhalt der Vorlesung sind die Höhepunkte dieser Forschung, angefangen mit frühen Ergebnissen aus den 1970er Jahren bis hin zu aktuellen Ergebnissen. Jedes dieser Ergebnisse wird eingebettet in eine Einführung in die verwendeten Techniken und den jeweiligen Kontext.
Literatur
Skript zur Vorlesung;
Köbler, J., Schöning, U., Toran, Jacobo: The Graph Isomorphism Problem Its Structural Complexity
Zusätzliche Informationen
Mit erfolgreichem Abschluss des Moduls werden die Studierenden in der Lage sein, wesentliche Erkenntnisse im Forschungsbereich Symmetrieerkennung und Symmetrieverwendung, inklusive gängiger Techniken und Ansätze zu erläutern,
fortgeschrittene Techniken aus verschiedenen Bereichen der theoretischen Informatik (Algorithmik, Logik, Komplexitätstheorie) anzuwenden,
fortgeschrittene Techniken aus angrenzenden Bereichen der Mathematik (Graphentheorie, algorithmische Gruppentheorie) anzuwenden,
diese Techniken im Kontext eines aktuellen Forschungsthemas zu kombinieren und anzuwenden,
Symmetrien in algorithmischen Kontexten zu nutzen.
Online-Angebote
moodle
Hochgeladenes Video mit Sprechstunde
Lehrinhalte
Die Vorlesung beschäftigt sich mit Symmetrie im algorithmischen Kontext. Einerseits bedeutet dies die algorithmische Verwendung von Symmetrien zum Beschleunigen von kombinatorischen Algorithmen (etwa zur Reduktion von Suchräumen oder beim Aufzählen kombinatorischer Objekte). Andererseits werden Algorithmen zum Finden von Symmetrien kombinatorischer Objekte entwickelt. Hierfür zentral ist das Graphenisomorphieproblem, eines der wichtigsten offenen Probleme der theoretischen Informatik. Es ist aus praktischer und theoretischer Sicht äquivalent zum Problem der Berechnung aller Symmetrien eines kombinatorischen Objektes. Im Laufe der vergangenen 40 Jahre hat es eine Fülle von Teilergebnissen ganz unterschiedlicher Natur gegeben, die auf Techniken aus verschiedenen Teilgebieten der theoretischen Informatik und der diskreten Mathematik beruhen. Inhalt der Vorlesung sind die Höhepunkte dieser Forschung, angefangen mit frühen Ergebnissen aus den 1970er Jahren bis hin zu aktuellen Ergebnissen. Jedes dieser Ergebnisse wird eingebettet in eine Einführung in die verwendeten Techniken und den jeweiligen Kontext.
Literatur
Skript zur Vorlesung;
Köbler, J., Schöning, U., Toran, Jacobo: The Graph Isomorphism Problem Its Structural Complexity
Zusätzliche Informationen
Mit erfolgreichem Abschluss des Moduls werden die Studierenden in der Lage sein, wesentliche Erkenntnisse im Forschungsbereich Symmetrieerkennung und Symmetrieverwendung, inklusive gängiger Techniken und Ansätze zu erläutern,
fortgeschrittene Techniken aus verschiedenen Bereichen der theoretischen Informatik (Algorithmik, Logik, Komplexitätstheorie) anzuwenden,
fortgeschrittene Techniken aus angrenzenden Bereichen der Mathematik (Graphentheorie, algorithmische Gruppentheorie) anzuwenden,
diese Techniken im Kontext eines aktuellen Forschungsthemas zu kombinieren und anzuwenden,
Symmetrien in algorithmischen Kontexten zu nutzen.
Online-Angebote
moodle
- Lehrende: Markus Anders
- Lehrende: Jendrik Brachter
- Lehrende: Pascal Schweitzer
Semester: SoSe 2021