In large and complex systems, failures can have dramatic consequences, such as black-outs, pandemics or the loss of entire classes of an ecosystem. Nevertheless, it is a centuries-old intuition that by using networks to capture the core of the complexity of such systems, one might understand in which part of a system a phenomenon originates. I investigate this intuition using spectral methods to decouple the dynamics of complex systems near stationary states into independent dynamical modes. In this description, phenomena are tied to a specific part of a system through localized eigenvectors which have large amplitudes only on a few nodes of the system's network. Studying the occurrence of localized eigenvectors, I find that such localization occurs exactly for a few small network structures, and approximately for the dynamical modes associated with the most prominent failures in complex systems. My findings confirm that understanding the functioning of complex systems generally requires to treat them as complex entities, rather than collections of interwoven small parts. Exceptions to this are only few structures carrying exact localization, whose functioning is tied to the meso-scale, between the size of individual elements and the size of the global network. However, while understanding the functioning of a complex system is hampered by the necessary global analysis, the prominent failures, due to their localization, allow an understanding on a manageable local scale. Intriguingly, food webs might exploit this localization of failures to stabilize by causing the break-off of small problematic parts, whereas typical attempts to optimize technological systems for stability lead to delocalization and large-scale failures. Thus, this thesis provides insights into the interplay of complexity and localization, which is paramount to ascertain the functioning of the ever-growing networks on which we humans depend.:1 Introduction 2 Concepts and Tools 2.1 Networks 2.2 Food webs 2.3 Dynamics on networks 2.4 Steady state operating modes 2.5 Bifurcations affecting operating modes 2.6 Dynamical modes 2.7 Generalized models for food webs 3 Perturbation Impact 3.1 Impact of perturbations on food webs 3.2 Examples 3.3 Impact formulation with dynamical modes 3.4 Influence and sensitivity of species 3.5 Localized dynamical modes 3.6 Iterative parameter estimation 3.7 Most important parameters and species 3.8 Discussion 4 Exact Localization 4.1 Graph symmetries 4.2 Localized dynamics on symmetries 4.3 Exactly localized dynamics 4.4 Symmetry reduction in networks 4.5 Application to food webs 4.6 Localization on asymmetric structures 4.7 Nearly-exact localization 4.8 Other systems 4.9 Discussion 5 Approximate Localization 5.1 Spread of a dynamical mode 5.2 Examples for localized instabilities 5.3 Localization of extreme eigenvalues 5.4 Dependence on the system size 5.5 Localization in the model of R. May 5.6 Finding motifs that carry localization 5.7 (Self-)stabilization of food webs 5.8 Repairing localized instabilities 5.9 Discussion 6 Conclusions Acknowledgments Appendix A Parametrization of the Gatun Lake food web B The Master Stability Function approach C Approximate localization on larger structures Bibliography

This thesis describes the development and setup of hybrid index structures. They are access methods for retrieval techniques in hybrid data spaces which are formed by one or more relational or normalised columns in conjunction with one non-relational or non-normalised column. Examples for these hybrid data spaces are, among others, textual data combined with geographical ones or data from enterprise content management systems. However, all non-relational data types may be stored as well as image feature vectors or comparable types. Hybrid index structures are known to function efficiently regarding retrieval operations. Unfortunately, little information is available about reorganisation operations which insert or update the row tuples. The fundamental research is mainly executed in simulation based environments. This work is written ensuing from a previous thesis that implements hybrid access structures in realistic database surroundings. During this implementation it has become obvious that retrieval works efficiently. Yet, the restructuring approaches require too much effort to be set up, e.g., in web search engine environments where several thousands of documents are inserted or modified every day. These search engines rely on relational database systems as storage backends. Hence, the setup of these access methods for hybrid data spaces is required in real world database management systems. This thesis tries to apply a systematic approach for the optimisation of the rearrangement algorithms inside realistic scenarios. Thus, a measurement and evaluation scheme is created which is repeatedly deployed to an evolving state and a model of hybrid index structures in order to optimise the regrouping algorithms to make a setup of hybrid index structures in real world information systems possible. Thus, a set of input corpora is selected which is applied to the test suite as well as an evaluation scheme. To sum up, it can be said that this thesis describes input sets, a test suite including an evaluation scheme as well as optimisation iterations on reorganisation algorithms reflecting a theoretical model framework to provide efficient reorganisations of hybrid index structures supporting multimedia search criteria.

Many complexity measures are defined as the size of a minimal representation in a specific model class. One such complexity measure, which is important because it is widely applied, is statistical complexity. It is defined for discrete-time, stationary stochastic processes within a theory called computational mechanics. Here, a mathematically rigorous, more general version of this theory is presented, and abstract properties of statistical complexity as a function on the space of processes are investigated. In particular, weak-* lower semi-continuity and concavity are shown, and it is argued that these properties should be shared by all sensible complexity measures. Furthermore, a formula for the ergodic decomposition is obtained. The same results are also proven for two other complexity measures that are defined by different model classes, namely process dimension and generative complexity. These two quantities, and also the information theoretic complexity measure called excess entropy, are related to statistical complexity, and this relation is discussed here. It is also shown that computational mechanics can be reformulated in terms of Frank Knight''s prediction process, which is of both conceptual and technical interest. In particular, it allows for a unified treatment of different processes and facilitates topological considerations. Continuity of the Markov transition kernel of a discrete version of the prediction process is obtained as a new result.

We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack, while the follower chooses a feasible packing maximizing his own profit. The leader’s aim is to optimize a linear objective function in the capacity and in the follower’s solution, but with respect to different item values. We address a stochastic version of this problem where the follower’s profits are uncertain from the leader’s perspective, and only a probability distribution is known. Assuming that the leader aims at optimizing the expected value of her objective function, we first observe that the stochastic problem is tractable as long as the possible scenarios are given explicitly as part of the input,which also allows to deal with general distributions using a sample average approximation. For the case of independently and uniformly distributed item values, we show that the problem is #P-hard in general, and the same is true even for evaluating the leader’s objective function. Nevertheless, we present pseudo-polynomial time algorithms for this case, running in time linear in the total size of the items.Based on this,we derive an additive approximation scheme for the general case of independently distributed item values, which runs in pseudo-polynomial time.

Diese Arbeit leistet Beiträge im Bereich der deskriptiven Komplexitätstheorie. Zunächst beschäftigen wir uns mit der ungelösten Frage, ob es eine Logik gibt, welche die Klasse der Polynomialzeit-Eigenschaften (PTIME) charakterisiert. Wir betrachten Graphklassen, die unter induzierten Teilgraphen abgeschlossen sind. Auf solchen Graphklassen lässt sich die 1976 von Gallai eingeführte modulare Zerlegung anwenden. Graphen, die durch modulare Zerlegung nicht zerlegbar sind, heißen prim. Wir stellen ein neues Werkzeug vor: das Modulare Zerlegungstheorem. Es reduziert (definierbare) Kanonisierung einer Graphklasse C auf (definierbare) Kanonisierung der Klasse aller primen Graphen aus C, die mit binären Relationen auf einer linear geordneten Menge gefärbt sind. Mit Hilfe des Modularen Zerlegungstheorems zeigen wir, dass Fixpunktlogik mit Zählen (FP+C) PTIME auf der Klasse aller Permutationsgraphen und auf der Klasse aller chordalen Komparabilitätsgraphen charakterisiert. Wir beweisen zudem, dass modulare Zerlegungsbäume in Symmetrisch-Transitive-Hüllen-Logik mit Zählen (STC+C) definierbar und damit in logarithmischem Platz berechenbar sind. Weiterhin definieren wir eine neue Logik für die Komplexitätsklasse Logarithmischer Platz (LOGSPACE). Wir erweitern die Logik erster Stufe mit Zählen um einen Operator, der eine in logarithmischem Platz berechenbare Form der Rekursion erlaubt. Die resultierende Logik LREC ist ausdrucksstärker als die Deterministisch-Transitive-Hüllen-Logik mit Zählen (DTC+C) und echt in FP+C enthalten. Wir zeigen, dass LREC LOGSPACE auf gerichteten Bäumen charakterisiert. Zudem betrachten wir eine Erweiterung LREC= von LREC, die sich gegenüber LREC durch bessere Abschlusseigenschaften auszeichnet und im Gegensatz zu LREC ausdrucksstärker als die Symmetrisch-Transitive-Hüllen-Logik (STC) ist. Wir beweisen, dass LREC= LOGSPACE sowohl auf der Klasse der Intervallgraphen als auch auf der Klasse der chordalen klauenfreien Graphen charakterisiert. / This theses is making contributions to the field of descriptive complexity theory. First, we look at the main open problem in this area: the question of whether there exists a logic that captures polynomial time (PTIME). We consider classes of graphs that are closed under taking induced subgraphs. For such graph classes, an effective graph decomposition, called modular decomposition, was introduced by Gallai in 1976. The graphs that are non-decomposable with respect to modular decomposition are called prime. We present a tool, the Modular Decomposition Theorem, that reduces (definable) canonization of a graph class C to (definable) canonization of the class of prime graphs of C that are colored with binary relations on a linearly ordered set. By an application of the Modular Decomposition Theorem, we show that fixed-point logic with counting (FP+C) captures PTIME on the class of permutation graphs and the class of chordal comparability graphs. We also prove that the modular decomposition tree is definable in symmetric transitive closure logic with counting (STC+C), and therefore, computable in logarithmic space. Further, we introduce a new logic for the complexity class logarithmic space (LOGSPACE). We extend first-order logic with counting by a new operator that allows it to formalize a limited form of recursion which can be evaluated in logarithmic space. We prove that the resulting logic LREC is strictly more expressive than deterministic transitive closure logic with counting (DTC+C) and that it is strictly contained in FP+C. We show that LREC captures LOGSPACE on the class of directed trees. We also study an extension LREC= of LREC that has nicer closure properties and that, unlike LREC, is more expressive than symmetric transitive closure logic (STC). We prove that LREC= captures LOGSPACE on the class of interval graphs and on the class of chordal claw-free graphs.

Wird der Äquator-Pol-Energietransfer als Wärmediffusion berücksichtigt, so gehen Energiebilanzmodelle in Reaktions-Diffusionsgleichungen über, deren Modellfall die (deterministische) Chafee-Infante-Gleichung darstellt. Ihre Lösung besitzt zwei stabile Zustände und mehrere instabile auf der separierenden Mannigfaltigkeit (Separatrix) der stabilen Anziehungsgebiete. Es wird bewiesen, dass die Lösung auf geeignet verkleinerten Anziehungsgebieten mit Minimalabstand zur Separatrix innerhalb von Zeitskalen relaxiert, die höchstens logarithmisch darin anwachsen. Motiviert durch statistische Belege aus grönländischen Zeitreihen wird diese partielle Differentialgleichung unter Störung mit unendlichdimensionalem, Hilbertraum-wertigen, regulär variierenden Lévy''schen reinen Sprungrauschen mit index alpha und Intensität epsilon untersucht. Ein kanonisches Beispiel dieses Rauschens ist alpha-stabiles Rauschen im Hilbertraum. Durch Erweiterung einer Methode von Imkeller und Pavlyukevich auf stochastische partielle Differentialgleichungen wird unter milden Bedingungen bewiesen, dass im Gegensatz zu Gauß''schem Rauschen die erwarteten Austritts- und übertrittszeiten zwischen Anziehungsgebieten polynomiell mit Ordnung in der inversen Intensität für kleine Rauschintensität anwachsen. In Kapitel 6 wird eine zusätzliche natürliche “Separatrixhypothese” über das Sprungmaß, eingeführt, die eine obere Schranke für die Austrittszeiten aus einer Umgebung der Separatrix impliziert. Dies ermöglicht den Nachweis einer oberen Schranke für die Austrittszeiten, welche gleichmäßig für Anfangsbedingungen in dem ganzen Anziehungsgebiet gilt. Es folgen zwei Lokalisierungsergebnisse. Schließlich wird gezeigt, dass die Lösung metastabiles Verhalten aufweist. Unter der “Separatrixhypothese” wird dies auf ein Ergebnis erweitert, welches gleichmäßig im Raum gilt. / If equator-to-pole energy transfer by heat diffusion is taken into account, Energy Balance Models turn into reaction-diffusion equations, whose prototype is the (deterministic) Chafee-Infante equation. Its solution has two stable states and several unstable ones on the separating manifold (separatrix) of the stable domains of attraction. We show, that on appropriately reduced domains of attraction of a minimal distance to the separatrix the solution relaxes in time scales increasing only logarithmically in it. Motivated by the statistical evidence from Greenland ice core time series, we consider this partial differential equation perturbed by an infinite-dimensional Hilbert space-valued regularly varying (pure jump) Lévy noise of index alpha and intensity epsilon. A proto-type of this noise is alpha-stable noise in the Hilbert space. Extending a method developed by Imkeller and Pavlyukevich to the SPDE setting we prove under mild conditions that in contrast to Gaussian perturbations the expected exit and transition times between the domains of attraction increase polynomially in the inverse intensity. In Chapter 6 we introduce an additional natural separatrix hypothesis on the jump measure that implies an upper bound on the exit time of a neighborhood of the separatrix. This allows to obtain an upper bound for the asymptotic exit time uniform for the initial positions inside the entire domain of attraction. It is followed by two localization results. Finally we prove that the solution exhibits metastable behavior. Under the separatrix hypothesis we can extend this to a result that holds uniformly in space.

Zahlungen für Ökosystemdienstleistungen (Payments for EcosystemServices, PES) sind in den letzten Jahren zum Aushängeschild von Umweltorganisation geworden. Der Gedanke, die Bereitstellung von Ökosystemdienstleistungen durch PES abzusichern, ist in praktischen Diskursen von Vermittlern zu finden, die an potentiell Zahlende gerichtet sind. Praktikern ist bisher jedoch schwer gefallen, zu zeigen, dass PES tatsächlich zu den vorgesehenen Zielen führen können. Forscher haben darauf hingewiesen, dass zahlreiche PES-Schemata, insbesondere diejenigen mit Bezug auf Wasser, auf unsicheren Annahmen beruhen und außerdem gewichtige Kausalzusammenhänge zwischen Eingriffen in die Landnutzung und Ökosystemdienstleistungen vermissen lassen. Diese Unsicherheit in PES-Schemata geht nicht nur aus praktischen Schwierigkeiten hervor, sondern aus der Komplexität von Mensch-Umwelt-Systemen (human-environment systems) und aus der Begrenztheit des Wissens über diese Systeme. Forscher sind zwar in derLage, diese wesentlichen Herausforderungen zu beschreiben und zu diskutieren. In der Fachliteratur mangelt es jedoch an empirischen Studien,die die zusätzliche Wirksamkeitvon PES-Schemata untersuchen, d.h. ob diese Schemata zusätzliche Wirkungen zeigen, die anderen Faktoren nicht zurechenbar sind, bzw. Studien, die die Bedeutung von Nachweisen für ihre Wirksamkeit für die Interessengruppen (stakeholders) untersuchen. Die Dissertation trägt dazu bei, diese empirische Lücke zu schließen: Dazu untersucht sie vier wasserbezogene Zahlungsschemata, hier auch Zahlungen für Wassereinzugsgebietsleistungen genannt, in Kolumbien. Sie vergleicht die vier Fälle hinsichtlich der Bestrebungen, durch Beobachtung (monitoring) und Evaluation Nachweise für die Wirksamkeit zu erbringen, sowie hinsichtlich der damit verbundenen Herausforderungen. Eines der Kapitel enthält auch drei Fallstudien aus Brasilien, die als Vergleich zu den Fällen aus Kolumbien und der Darstellung von Unterschieden und Gemeinsamkeiten dienen. / Payments for Ecosystem Services (PES) have become the flagship of conservation organizations in recent years. The idea of securing ecosystem service (ES) provision through PES has been present in practical discourses of intermediaries directed at potential payers. However, demonstrating that PES can actually achieve the intended goals has been difficult for practitioners. Researchers have pointed out that many PES schemes, particularly water-related ones, are based on unreliable assumptions and lack strong causal links between land use interventions and ecosystem services. This uncertainty in PES schemes arises not only from practical difficulties, but from the complexity of human-environment systems (HES), and the limits of knowledge about them. Researchers have been able to describe and discuss these major challenges. However, the literature is still poor on empirical studies exploring the additionality of PES schemes, that is, if those schemes produce additional effects not attributable to other factors, as well as studies exploring the importance of impact evidence for stakeholders involved. This dissertation contributes to filling this empirical gap by exploring four water-related payments schemes (here also called payments for watershed services, PWS) in Colombia, comparing the cases in terms of their efforts to produce impact evidence through monitoring and evaluation, and their associated challenges. Three cases from Brazil are also included in one of the chapters and compared with the Colombian cases by illustrating differences and similarities.

Diese Arbeit wird einer Weiterentwicklung der Dichtematrixtheorie und ihrer Anwendung zum Studium ultraschneller laserpulsinduzierter Dynamik in Molekularsystemen in Wechselwirkung mit einem thermischen Bad gewidmet. Zwei grosse Themenkomplexe werden behandelt. Zuerst werden die sogenannten Gedächtniseffekte diskutiert. Diese folgen aus einer reduzierten Beschreibung des Molekularsystems, in der die Umgebungsfreiheitsgrade eliminiert werden. Im zweiten Teil wird die Laserpulssteuerung der dissipativen Molekulardynamik untersucht. Die theoretische Beschreibung von offenen Quantensystemen führt zu einer zeitlich nicht-lokalen Bewegungsgleichung: Die Zeitentwicklung des Molekularsystems hängt von seiner Vergangenheit ab. In dieser Arbeit wird eine numerische Methode zur Lösung der zeitlich nicht-lokalen Bewegungsgleichung entwickelt und mit einem minimalen Modell eines polyatomaren Moleküls unter dissipativem Einfluss der Umgebung getestet. Eine analytische Lösung der Bewegungsgleichung für den speziellen Fall einer sehr langen Gedächtniszeit wurde hergeleitet. Zur Identifizierung solcher Gedächtniseffekte vergleichen wir diese analytische Lösung mit numerischen Rechnungen inklusive Gedächtnis und mit approximativen Rechnungen, die die zeitliche Nicht-Lokalität vernachlässigen. Für eine Anregung mit einem Laserpuls, der kürzer als die Gedächtniszeit des Systems ist, zeigt das Molekularsystem eine erkennbar unterschiedliche Dynamik als ohne Gedächtniss. Die Gedächtniseffekte werden mit abfallender Laserpulslänge deutlich ausgeprägter. Der zweite Teil der Arbeit konzentriert sich auf die Anwendung der Theorie der Optimalen Kontrolle, um die molekulare Dynamik zu steuern. Aus der Theorie der Optimalen Kontrolle erhält man Laserpulse, die bestimmte Aufgaben erfüllen, z.B. die Besetzung gewünschter vibronischer Niveaus des Molekularsystems oder die Platzierung eines Wellenpakets auf einer vorgegebenen Position auf der molekularen Potentialfläche. Als erstes Beispiel haben wir die Kontrolle des dissipativen fotoinduzierten Elektronentransfers in einem Donator-Brückenmolekül-Akzeptor System betrachtet, wobei wir das Gedächtniss vernachlässigt haben. Die Steuerbarkeit des Elektronentransfers wird diskutiert und der Mechanismus, mit dem sie möglich wird, wird identifiziert. Wir haben festgestellt, dass die Steuerung der Elektronentransferreaktionen selbst unter dem Einfluss von Dissipation möglich ist, obwohl die Kontrollausbeute mit steigender Dissipation drastisch abfällt. In Anwesenheit von Dissipation verändert sich auch der Mechanismus der Steuerung. Die experimentelle Ausführbarkeit der Herstellung des aus der Theorie der Optimalen Kontrolle resultierenden Kontrollpulses wird diskutiert und Methoden werden präsentiert, die die Abschätzung der Effizienz ermöglichen, mit der ein Flussigkristall--Laserpulsformer, wie er heute in Experimenten verwendet wird, den gewünschten Puls erzeugen kann. Um zwischen verschiedenen Kontrollaufgaben zu unterscheiden, wird ein quantitatives Mass eingeführt, das die Komplexität der Kontrollaufgabe charakterisiert. Die Theorie der Optimalen Kontrolle wird auch für Molekularsysteme formuliert, die statische Unordnung zeigen, und wird auf ein Ensemble von Molekülen mit zufälligen Orientierungen angewendet. Zum Schluss wird die Bedeutung der Gedächtnisseffekte für die Steuerung der dissipativen Dynamik diskutiert und die Theorie der Optimalen Kontrolle neu formuliert um eine zeitliche Nicht-Lokalität in der Bewegungsgleichung des Molekularsystems zu berücksichtigen. / This work is dedicated to a further development of the density matrix theory and its application to the study of ultrafast laser pulse induced dynamics in molecular systems interacting with a thermal environment. Two topics are considered, first the so-called memory effects are analyzed which result from a reduced description of the molecular system excluding the environmental degrees of freedom. And secondly, the laser pulse control of dissipative molecular dynamics is examined. The theoretical description of open quantum systems results in a time non-local equation of motion so that the evolution of the molecular system depends on its past. In this work a numerical method to solve the time non-local equations of motion has been developed and tested for a minimal model of a polyatomic molecule subject to the dissipative influence of an environment. An analytical solution of the equation of motion for the special case of very long standing memory is also achieved. To identify signatures of such memory effects in general case we compare this analytical solution with numerical calculations involving memory and with approximative computations ignoring time non-locality. For the excitation by a laser pulse shorter than the duration of the memory the molecular systems exhibit noticeably different dynamics than for the absence of the memory. The effects become significantly more pronounced with decreasing laser pulse durations. The second part of the work concentrates on the application of the optimal control theory to guide molecular dynamics. Optimal control theory provides laser pulses which are designed in such a manner to fulfill certain control tasks, e.g. the population of a desired vibrational level of the molecular system or the placement of a wavepacket on a prescribed position on the molecular potential energy surface. As a first example the control of the dissipative photo-induced electron transfer in a donor--bridge--acceptor systems has been particularly considered ignoring the memory. The controllability of the electron transfer has been discussed and the mechanism by which it becomes possible has been identified. We have found the control of electron transfer reactions feasible even under the influence of dissipation although the yield of the control decreases drastically with increasing dissipation. In the presence of dissipation mechanism of the control has been found to change. The feasibility of the reproduction of the control pulses resulting for the optimal control theory in the experiment has been discussed and methods have been presented how to check the efficiency of the reproduction of optimal control pulses by liquid crystal pulse shapers, prevailingly used in modern control experiments. To distinguish different control tasks a quantitative measure has been introduced characterizing complexity of the control task. The optimal control theory has also been formulated for molecular systems showing static disorder and applied on an ensemble of molecules exhibiting random orientations. Finally, the importance of memory effects for the control of dissipative dynamics has been discussed and the optimal control theory has been formulated to account for a time non-locality in the equation of motion for molecular systems.

No description available.

Normalformen drücken semantische Eigenschaften einer Logik durch syntaktische Restriktionen aus. Sie ermöglichen es Algorithmen, Grenzen der Ausdrucksstärke einer Logik auszunutzen. Ein Beispiel ist die Lokalität der Logik erster Stufe (FO), die impliziert, dass Graph-Eigenschaften wie Erreichbarkeit oder Zusammenhang nicht FO-definierbar sind. Gaifman-Normalformen drücken die Bedeutung einer FO-Formel als Boolesche Kombination lokaler Eigenschaften aus. Sie haben eine wichtige Rolle in Model-Checking Algorithmen für Klassen dünn besetzter Graphen, deren Laufzeit durch die Größe der auszuwertenden Formel parametrisiert ist. Es ist jedoch bekannt, dass Gaifman-Normalformen im Allgemeinen nur mit nicht-elementarem Aufwand konstruiert werden können. Dies führt zu einer enormen Parameterabhängigkeit der genannten Algorithmen. Ähnliche nicht-elementare untere Schranken sind auch für Feferman-Vaught-Zerlegungen und für die Erhaltungssätze von Lyndon, Łoś und Tarski bekannt. Diese Arbeit untersucht die Komplexität der genannten Normalformen auf Klassen von Strukturen beschränkten Grades, für welche die nicht-elementaren unteren Schranken nicht gelten. Für diese Einschränkung werden Algorithmen mit elementarer Laufzeit für die Konstruktion von Gaifman-Normalformen, Feferman-Vaught-Zerlegungen, und für die Erhaltungssätze von Lyndon, Łoś und Tarski entwickelt, die in den ersten beiden Fällen worst-case optimal sind. Wichtig hierfür sind Hanf-Normalformen. Es wird gezeigt, dass eine Erweiterung von FO durch unäre Zählquantoren genau dann Hanf-Normalformen erlaubt, wenn alle Zählquantoren ultimativ periodisch sind, und wie Hanf-Normalformen in diesen Fällen in elementarer und worst-case optimaler Zeit konstruiert werden können. Dies führt zu Model-Checking Algorithmen für solche Erweiterungen von FO sowie zu Verallgemeinerungen der Algorithmen für Feferman-Vaught-Zerlegungen und die Erhaltungssätze von Lyndon, Łoś und Tarski. / Normal forms express semantic properties of logics by means of syntactical restrictions. They allow algorithms to benefit from restrictions of the expressive power of a logic. An example is the locality of first-order logic (FO), which implies that properties like reachability or connectivity cannot be defined in FO. Gaifman's local normal form expresses the satisfaction conditions of an FO-formula by a Boolean combination of local statements. Gaifman normal form serves as a first step in fixed-parameter model-checking algorithms, parameterised by the size of the formula, on sparse graph classes. However, it is known that in general, there are non-elementary lower bounds for the costs involved in transforming a formula into Gaifman normal form. This leads to an enormous parameter-dependency of the aforementioned algorithms. Similar non-elementary lower bounds also hold for Feferman-Vaught decompositions and for the preservation theorems by Lyndon, Łoś, and Tarski. This thesis investigates the complexity of these normal forms when restricting attention to classes of structures of bounded degree, for which the non-elementary lower bounds are known to fail. Under this restriction, the thesis provides algorithms with elementary and even worst-case optimal running time for the construction of Gaifman normal form and Feferman-Vaught decompositions. For the preservation theorems, algorithmic versions with elementary running time and non-matching lower bounds are provided. Crucial for these results is the notion of Hanf normal form. It is shown that an extension of FO by unary counting quantifiers allows Hanf normal forms if, and only if, all quantifiers are ultimately periodic, and furthermore, how Hanf normal form can be computed in elementary and worst-case optimal time in these cases. This leads to model-checking algorithms for such extensions of FO and also allows generalisations of the constructions for Feferman-Vaught decompositions and preservation theorems.