Neue Strategien zur Lösung von Isomorphieproblemen

Titelangaben

Koch, Matthias:
Neue Strategien zur Lösung von Isomorphieproblemen.
Bayreuth , 2016 . - XIV, 178 S.
( Dissertation, 2016 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

	Format: PDF Name: Dissertation_Matthias_Koch.pdf Version: Veröffentlichte Version Verfügbar mit der Lizenz Creative Commons BY-NC 3.0: Namensnennung, nicht kommerziell
	Download (1MB)

Abstract

In this thesis a universal strategy to solve isomorphism problems is developed. Isomorphism problems appear in the context of many subfields of mathematics, as well as in computer science, pharmaceutics and others. The strategy is based on the homomorphism principle for group actions of Reinhard Laue and the "Snakes and Ladders" algorithm (Leiterspiel) of Bernd Schmalz. A complete mathematical basis for this strategy is given, with the so-called "Strong Ladders" at the center. In addition, three new algorithms (depthfirst StroLL, breadthfirst StroLL, Leiterspiel light) are presented on the basis of this strategy and described in pseudocode. The algorithms show the unique properties of this strategy: They are applicable for a majority of isomorphism problems, including the subgraph isomorphism problem, as well as some problems in group theory such as calculating the intersection of two subgroups; a canonical form for a single structure can be calculated; they are highly efficient and especially memory-saving; and can be executed in a distributed system. Both the mathematical strategy and the algorithms can be of interest for mathematicians as well as computer scientists and end users faced with difficult isomorphism problems.

Abstract in weiterer Sprache

In dieser Arbeit wird eine universelle Strategie zur Lösung von Isomorphieproblemen beschrieben. Isomorphieprobleme tauchen in vielen verschiedenen Kontexten in der Mathematik, der Informatik, der Pharmazie u.a. auf. Die Lösungsstrategie basiert auf dem Homorphieprinzip für Gruppenoperationen von Reinhard Laue und dem Leiterspielalgorithmus von Bernd Schmalz. Das mathematische Rückgrat dieser neuen Strategie wird ausführlich beschrieben, in deren Mittelpunkt die sogenannten „Starken Leitern“ stehen. Auf Basis dieser Starken Leitern werden drei neue Algorithmen (depthfirst StroLL, breadthfirst StroLL, Leiterspiel light) vorgestellt und in Pseudocode formuliert. Anhand dieser Algorithmen lassen sich die einzigartigen Eigenschaften dieser Strategie zeigen: eine Vielzahl von Isomorphieproblemen lassen sich auf diese Weise lösen wie z. B. das Teilgraphenisomorphieproblem, sowie einige Probleme der Gruppentheorie wie z.B. die Berechnung der Schnittmenge zweier Untergruppen; auch für einzelne Strukturen kann eine kanonische Form berechnet werden; sie sind sehr effizient und insbesondere speicherschonend und sind auch für die Ausführung in verteilten Systemen (distributed systems) geeignet. Sowohl die mathematische Basis als auch die Algorithmen eignen sich für Mathematiker, Informatiker und Anwender, die mit einem schwierigen Isomorphieproblem konfrontiert sind.