Boltzmann Sampling Algorithmen zum Erzeugen zufälliger kombinatorischer Objekte

Abstract

In dieser Arbeit betrachten wir die sogenannten Boltzmann-Sampler. Hierbei handelt es sich um Generatoren von zufälligen kombinatorischen Objekten.Welcher Art diese Objekte sind, wird hierbei durch eine kombinatorische Spezifikation bestimmt, also ein Gleichungssystem, das Terme aus kombinatorischen Basisoperationen in Relation setzt. Die Boltzmann-Sampler wurden in einem Artikel von Duchon, Flajolet, Louchard und Schaeffer im Jahr 2002 eingeführt. Im Gegensatz zu früher entwickelten Methoden zur Erzeugung zufälliger Strukturen hat der Boltzmann-Sampler den Vorteil, dass bei Fallenlassen der Einschränkung, dass die Größe der Strukturen fest vorgegeben ist, sondern in einem Intervall liegt, in vielen Fällen eine sehr effiziente Erzeugung der Strukturen in O(n) möglich ist, wobei n die Strukturgröße bezeichnet. In dieser Arbeit formulieren wir das Boltzmann-Sampling im Kontext der sogenannten kombinatorischen Spezies, einer relativ neuen Theorie, die durch Joyal 1981 begründet wurde. In dieser Theorie ist es möglich, sowohl markierte, als auch unmarkierte kombinatorische Objekte in einem Zug zu betrachten. Weiters wurde die Frage, wann ein kombinatorisches Gleichungssystem sinnvoll ist und wie die Lösung zu konstruieren ist, befriedigend geklärt. Der erste Teil dieser Arbeit ist eine Einführung in die Theorie der kombinatorischen Spezies inklusive der entwickelten Sätze über die kombinatorischen Gleichungssysteme. Im zweiten Abschnitt werden die exponentiellen Boltzmann-Sampler im Kontext der Spezies- Theorie definiert und untersucht. Diese Sampler erzeugen markierte Objekte, deren Grundbausteine mit einer eindeutigen Marke versehen sind. Es werden Sampler für die wichtigsten Basisklassen von kombinatorischen Objekten und die wichtigsten kombinatorischen Basisoperationen angegeben, sowie deren Korrektheit bewiesen. Außerdem wird die kombinatorische Newton-Iteration vorgestellt, die eine effiziente Auswertung der erzeugenden Funktion, die für den Sampling-Prozess benötigt wird, ermöglicht. Im letzten Abschnitt wird die Implementierung eines exponentiellen Boltzmann-Samplers in der Programmiersprache Java beschrieben, die im Zuge dieser Arbeit erstellt wurde. Das Programm erhält dabei als Eingabedaten eine kombinatorische Spezifikation, die in einem XML-Format angegeben wird, sowie den gewünschten Größenbereich der zu erzeugenden Strukturen, und sampelt diese. Diese Implementierung wurde absichtlich so allgemein und erweiterbar wie möglich gehalten, damit sie für unterschiedlichste Anwendungsbereiche verwendbar ist. This thesis is about Boltzmann samplers, which are generators of random combinatorial objects. The structure of these objects is determined by a combinatorial specification, which is a system of equations consisting of terms of combinatorial base operations.

This thesis is about Boltzmann samplers, which are generators of random combinatorial objects. The structure of these objects is determined by a combinatorial specification, which is a system of equations consisting of terms of combinatorial base operations. The Boltzmann samplers were introduced in the year 2002 in an article by Duchon, Flajolet, Louchard and Schaeffer. In contrast to previously developed sampling methods, they have the advantage of a very efficient runtime behavior. If the size condition on the sampled objects is loosened to a size interval instead of an exact size, in many cases the runtime is O(n) with respect to structure size n. In this paper the Boltzmann sampling framework is formulated in the context of the theory of combinatorial species, which was introduced relatively recently by Joyal in 1981. Within this theory it is possible to treat labeled and unlabeled objects simultaneously, contrasting the older combinatorial frameworks. Furthermore it provides satisfying answers to questions concerning the meaning given to a combinatorial systems of equations. The first part of this paper gives an introduction to the theory of species including the answers to these questions. In the second part we define and examine exponential Boltzmann samplers using the theory of species. These samplers generate objects, whose basic building blocks are marked with unique labels. We state sampling algorithms for the most important base classes of objects and combinatorial base operations and prove their correctness. Finally we present a combinatorial version of Newton's iteration, enabling us to efficiently evaluate the generating functions used by the sampling process. The last section is dedicated to the implementation of an exponential Boltzmann sampler written in the Java programming language. The program's input data consist of a combinatorial specification written in the XML file format, as well as the desired range of size of the generated structures. The structures get sampled and can be saved to a file in a text format. The implementation is supposed to be as generic and expandable as possible in order to meet the requirements of many application areas.