Constraint Satisfaction Problems (CSPs) are NP-complete in general, however, there are many tractable subclasses that rely on the restriction of the structure of their underlying hypergraphs. It is a well-known fact, for instance, that CSPs whose underlying hypergraph is acyclic are tractable. Trying to define “nearly acyclic” hypergraphs led to the definition of various hypergraph decomposition methods. An important member in this class is the hypertree decomposition method, introduced by Gottlob et al. It possesses the property that CSPs falling into this class can be solved efficiently, and that hypergraphs in this class can be recognized efficiently as well. Apart from polynomial tractability, complexity analysis has shown, that both afore-mentioned problems lie in the low complexity class LOGCFL and are thus moreover efficiently parallelizable. A parallel algorithm has been proposed for the “evaluation problem”, however all algorithms for the “recognition problem” presented to date are sequential. The main contribution of this dissertation is the creation of an object oriented programming library including a task scheduler which allows the parallelization of a whole range of computational problems, fulfilling certain complexity-theoretic restrictions. This library merely requires the programmer to provide the implementation of several classes and methods, representing a general alternating algorithm, while the mechanics of the task scheduler remain hidden. In particular, we use this library to create an efficient parallel algorithm, which computes hypertree decompositions of a fixed width. Another result of a more theoretical nature is the definition of a new type of decomposition method, called Balanced Decompositions. Solving CSPs of bounded balanced width and recognizing such hypergraphs is only quasi-polynomial, however still parallelizable to a certain extent. A complexity-theoretic analysis leads to the definition of a new complexity class hierarchy, called the DC-hierarchy, with the first class in this hierarchy, DC1 , precisely capturing the complexity of solving CSPs of bounded balanced width.

Cette thèse est consacrée à l’étude combinatoire, algébrique et homologique des hyperarbres et des partitions semi-pointées. Nous étudions plus précisément des structures algébriques et homologiques construites à partir des hyperarbres, puis des partitions semi-pointées.Après un bref rappel des notions utilisées, nous utilisons la théorie des espèces de structure afin de déterminer l’action du groupe symétrique sur l’homologie du poset des hyperarbres. Cette action s’identifie à l’action du groupe symétrique liée à la structure anti-cyclique de l’opérade PreLie. Nous raffinons ensuite nos calculs sur une graduation de l’homologie, appelée homologie de Whitney. Cette étude motive l'introduction de la notion d’hyperarbre aux arêtes décorées par une espèce. Une bijection des hyperarbres décorés avec des arbres en boîtes et des partitions décorées permet d’obtenir une formule close pour leur cardinal, à l’aide d’un codage de Prüfer. Nous adaptons ensuite les méthodes de calcul de caractères sur les algèbres de Hopf d’incidence, introduites par W. Schmitt dans le cas de familles de posets bornés, à des familles de posets non bornés vérifiant certaines propriétés. Nous appliquons ensuite cette adaptation aux posets des hyperarbres. Enfin, au cours de notre étude une généralisation des posets des partitions et des posets des partitions pointées apparaît : les poset des partitions semi-pointées. Nous montrons que ces posets sont aussi Cohen-Macaulay, avant de déterminer à l’aide de la théorie des espèces une formule close pour la dimension de l’unique groupe d’homologie non trivial de ces posets / This thesis is dedicated to the combinatorial, algebraic and homological study of hypertrees and semi-pointed partitions. More precisely, we study algebraic and homological structures built from hypertrees and semi-pointed partitions. After recalling briefly the notions needed, we use the theory of species of structures to compute the action of the symmetric group on the homology of the hypertree posets. This action is the same as the action of the symmetric group linked with the anticyclic structure of the PreLie operad. We refine our computations on a grading of the homology : Whitney homology. This study is a motivation for the introduction of the notion of edge-decorated hypertrees. A one-to-one correspondence of decorated hypertrees with box trees and decorated partitions enables us to compute a close formula for the cardinality of decorated hypertrees, thanks to a Prüfer code. Moreover, we adapt computation methods of characters on incidence Hopf algebras, introduced by W. Schmitt for families of bounded posets, to families of unbounded posets satisfying some additional properties, called triangle and diamond posets. We apply these results to the hypertree posets. Finally, we unveil a new family of posets : the semi-pointed partition posets, which generalize both partition posets and pointed partition posets. We show the Cohen-Macaulayness of these posets and obtain, thanks to species theory, a closed formula for the dimension of its unique homology group, which extend the ones established for partition posets and pointed partition posets

Diese Arbeit untersucht verschiedene Fragen hinsichtlich der birationalen Geometrie der Modulräume $\Mbar_g$ und $\Mbar_{g,n}$, mit besonderem Augenmerk auf der Berechnung effektiver Divisorklassen. In Kapitel 2 definieren wir für jedes $n$-Tupel ganzer Zahlen $\d$, die sich zu $g-1$ summieren, einen geometrisch bedeutsamen Divisor auf $\Mbar_{g,n}$, der durch Zurückziehen des Thetadivisors einer universellen Jacobi-Varietät mittels einer Abel-Jacobi-Abbildung erhalten wird. Er ist eine Verallgemeinerung verschiedener in der Literatur verwendeten Arten von Divisoren. Wir berechnen die Klasse dieses Divisors und zeigen, dass er für bestimmte $\d$ irreduzibel und extremal im effektiven Kegel von $\Mbar_{g,n}$ ist. Kapitel 3 beschäftigt sich mit einem birationalen Modell $X_6$ von $\Mbar_6$, das durch quadrische Hyperebenenschnitte auf der del-Pezzo-Fläche vom Grad $5$ erhalten wird. Wir berechnen die Klasse des großen Divisors, der die birationale Abbildung $\Mbar_6 \dashrightarrow X_6$ induziert, und erhalten so eine obere Schranke an die bewegliche Steigung von $\Mbar_6$. Wir zeigen, dass $X_6$ der letzte nicht-triviale Raum im log-minimalen Modellprogramm für $\Mbar_6$ ist. Weiterhin geben wir einige Resultate bezüglich der Unirationalität der Weierstraßorte auf $\Mbar_{g,1}$. Für $g = 6$ hängen diese mit der del-Pezzo-Konstruktion zusammen, die benutzt wurde, um das Modell $X_6$ zu konstruieren. Kapitel 4 konzentriert sich auf den Fall $g = 0$. Castravet and Tevelev führten auf $\Mbar_{0,n}$ kombinatorisch definierte Hyperbaumdivisoren ein, die für $n = 6$ zusammen mit den Randdivisoren den effektiven Kegel erzeugen. Wir berechnen die Klasse des Hyperbaumdivisors auf $\Mbar_{0,7}$, der bis auf Permutation der markierten Punkte eindeutig ist. Wir geben eine geometrische Charakterisierung für ihn an, die zu der von Keel und Vermeire für den Fall $n = 6$ gegebenen analog ist. / This thesis investigates various questions concerning the birational geometry of the moduli spaces $\Mbar_g$ and $\Mbar_{g,n}$, with a focus on the computation of effective divisor classes. In Chapter 2 we define, for any $n$-tuple $\d$ of integers summing up to $g-1$, a geometrically meaningful divisor on $\Mbar_{g,n}$ that is essentially the pullback of the theta divisor on a universal Jacobian variety under an Abel-Jacobi map. It is a generalization of various kinds of divisors used in the literature, for example by Logan to show that $\Mbar_{g,n}$ is of general type for all $g \geq 4$ as soon as $n$ is big enough. We compute the class of this divisor and show that for certain choices of $\d$ it is irreducible and extremal in the effective cone of $\Mbar_{g,n}$. Chapter 3 deals with a birational model $X_6$ of $\Mbar_6$ that is obtained by taking quadric hyperplane sections of the degree $5$ del Pezzo surface. We compute the class of the big divisor inducing the birational map $\Mbar_6 \dashrightarrow X_6$ and use it to derive an upper bound on the moving slope of $\Mbar_6$. Furthermore we show that $X_6$ is the final non-trivial space in the log minimal model program for $\Mbar_6$. We also give a few results on the unirationality of Weierstraß loci on $\Mbar_{g,1}$, which for $g = 6$ are related to the del Pezzo construction used to construct the model $X_6$. Finally, Chapter 4 focuses on the case $g = 0$. Castravet and Tevelev introduced combinatorially defined hypertree divisors on $\Mbar_{0,n}$ that for $n = 6$ generate the effective cone together with boundary divisors. We compute the class of the hypertree divisor on $\Mbar_{0,7}$, which is unique up to permutation of the marked points. We also give a geometric characterization of it that is analogous to the one given by Keel and Vermeire in the $n = 6$ case.

Tento projekt se věnuje problematice zobrazení velkých hierarchických struktur, zejména možnostem vizualizace stromových grafů. Cílem je implementace hyperbolického prohlížeče ve webovém prostředí, který využívá potenciálu neeukleidovské geometrie k promítnutí stromu na hyperbolickou rovinu. Velký důraz je kladen na uživatelsky přívětivou manipulaci se zobrazovaným modelem a snadnou orientaci.