Fakultät für Mathematik, Informatik und Statistik - Digitale Hochschulschriften der LMU - Teil 01/02

We consider two-player games of perfect information of length some cardinal $\kappa$.

It is well-known that for $\kappa \geq \omega_1$ the full axiom of determinacy for these games fails, thus

we investigate three weaker forms of it. We obtain the measurability of $\kappa^{+}$ under $DC_{\kappa}$-the

axiom of dependent choices generalized to $\kappa$. We generalize the notions of perfect and meager sets and

provide characterizations with some special kinds of games. We show that under an additional assumption one of

our three axioms follows from the other two.

Im vorliegenden Band werden Erkenntnisse sowohl der psychologischen als auch der mathematikdidaktischen Forschung zusammengetragen. Eine eigene Untersuchung, die im Kern aus einer Interviewstudie besteht, ergänzt die Ergebnisse zum Wissen von Schülerinnen und Schülern zu den Begriffen der Analysis.

Die Bedeutung multimedialer Dienste hat in den letzten Jahren beträchtlich zugenommen. Ihre Nutzung ist heutzutage nicht mehr nur auf stationäre Geräte beschränkt: durch bessere mobile Endgeräte und leistungsfähigere Netze können diese Dienste immer mehr auch unterwegs eingesetzt werden. Gerade im mobilen Umfeld kämpfen sie aber mit zwei grundlegenden Problemen: zum einen ist es für den Nutzer schwierig, aus der riesigen Menge der Inhalte diejenigen zu finden, die für ihn wirklich relevant sind. Dieses Problem tritt auch bei stationärer Nutzung auf, die schlechteren Eingabemöglichkeiten und die geringere Bandbreite mobiler Endgeräte schränken aber gerade hier die Nutzung massiv ein. Zum anderen zeichnen sich mobile Geräte durch eine starke Heterogenität aus. Um multimediale Inhalte komfortabel nutzen zu können, muss deren optimale Darstellung für die unterschiedlichen Charakteristika dieser heterogenen Endgeräte gefunden werden. Eine Lösung für diese beiden Probleme ist die Personalisierung multimedialer Inhalte.

Im mobilen Bereich findet die Nutzung multimedialer Inhalte in einem wesentlich dynamischeren Kontext statt. Der Nutzer kann sich räumlich bewegen, die Umgebungslautstärke und die Lichtverhältnisse ändern sich häufig, und er ist der Witterung ausgesetzt. Wie diese Informationen genutzt werden, um die Personalisierung multimedialer Inhalte zu unterstützen, soll im Rahmen dieser Arbeit näher untersucht werden. Dafür wurde die Multimedia Adaptation and Selection Language (MASL) zur Beschreibung von Inhalten und Nutzern entwickelt. Die Informationen, die mit dieser Sprache erfasst werden, werden durch Nutzereingabe (explizit) oder automatisch (implizit) gewonnen. Exemplarisch wird dies in der vorliegenden Arbeit mit der expliziten und impliziten Gewinnung von Schlüsselwörtern zu Inhalten und Nutzerbewertungen gezeigt. Die Beschreibungen in MASL werden verwendet, um multimediale Inhalte Kontext-abhängig auszuwählen und die gewählten Inhalte in der Darstellung an den aktuellen Nutzungskontext anzupassen. Für die Auswahl werden Empfehlungssysteme eingesetzt, die Inhalte gemäß den aktuellen Kontextinformationen des Nutzers selektieren. Die entwickelten Ansätze werden in ein einheitliches Framework integriert, das flexibel konfigurierbar ist. Für die Anpassung der Darstellung wird eine Middleware entwickelt, die verteilt arbeitet: der Server-seitige Teil führt eine Voranpassung der Inhalte durch, der Client beendet den Anpassungsprozess.

This dissertation describes an exploration of digital tabletop interaction styles, with the ultimate goal of informing the design of a new model for tabletop interaction. In the context of this thesis the term digital tabletop refers to an emerging class of devices that afford many novel ways of interaction with the digital. Allowing users to directly touch information presented on large,

horizontal displays. Being a relatively young field, many developments are in flux; hardware and software change at a fast pace and many interesting alternative approaches are available at the same time. In our research we are especially interested in systems that are capable of sensing multiple contacts (e.g., fingers) and richer information such as the outline of whole hands or other physical objects. New sensor hardware enable new ways to interact with the digital. When embarking into the research for this thesis, the question which interaction styles could

be appropriate for this new class of devices was a open question, with many equally promising answers.

Many everyday activities rely on our hands ability to skillfully control and manipulate physical objects. We seek to open up different possibilities to exploit our manual dexterity and provide users with richer interaction possibilities. This could be achieved through the use of physical objects as input mediators or through virtual interfaces that behave in a more realistic fashion.

In order to gain a better understanding of the underlying design space we choose an approach organized into two phases. First, two different prototypes, each representing a specific interaction style – namely gesture-based interaction and tangible interaction – have been implemented. The flexibility of use afforded by the interface and the level of physicality afforded by the interface elements are introduced as criteria for evaluation. Each approaches’ suitability to support the

highly dynamic and often unstructured interactions typical for digital tabletops is analyzed based

on these criteria.

In a second stage the learnings from these initial explorations are applied to inform the design of a novel model for digital tabletop interaction. This model is based on the combination of rich multi-touch sensing and a three dimensional environment enriched by a gaming physics simulation. The proposed approach enables users to interact with the virtual through richer quantities such as collision and friction. Enabling a variety of fine-grained interactions using multiple fingers, whole hands and physical objects.

Our model makes digital tabletop interaction even more “natural”. However, because the interaction – the sensed input and the displayed output – is still bound to the surface, there is a fundamental limitation in manipulating objects using the third dimension. To address this issue,

we present a technique that allows users to – conceptually – pick objects off the surface and control their position in 3D. Our goal has been to define a technique that completes our model for on-surface interaction and allows for “as-direct-as possible” interactions. We also present

two hardware prototypes capable of sensing the users’ interactions beyond the table’s surface.

Finally, we present visual feedback mechanisms to give the users the sense that they are actually lifting the objects off the surface.

This thesis contributes on various levels. We present several novel prototypes that we built and evaluated. We use these prototypes to systematically explore the design space of digital tabletop interaction. The flexibility of use afforded by the interaction style is introduced as criterion alongside the user interface elements’ physicality. Each approaches’ suitability to support the

highly dynamic and often unstructured interactions typical for digital tabletops are analyzed. We present a new model for tabletop interaction that increases the fidelity of interaction possible in

such settings. Finally, we extend t

Game theory is a branch of applied mathematics studying the interaction of self-interested entities, so-called agents. Its central objects of study are games, mathematical models of real-world interaction, and solution concepts that single out certain outcomes of a game that are meaningful in some way. The solutions thus produced can then be viewed both from a descriptive and from a normative perspective. The rise of the Internet as a computational platform where a substantial part of today's strategic interaction takes place has spurred additional interest in game theory as an analytical tool, and has brought it to the attention of a wider audience in computer science.

An important aspect of real-world decision-making, and one that has received only little attention in the early days of game theory, is that agents may be subject to resource constraints. The young field of algorithmic game theory has set out to address this shortcoming using techniques from computer science, and in particular from computational complexity theory. One of the defining problems of algorithmic game theory concerns the computation of solution concepts. Finding a Nash equilibrium, for example, i.e., an outcome where no single agent can gain by changing his strategy, was considered one of the most important problems on the boundary of P, the complexity class commonly associated with efficient computation, until it was recently shown complete for the class PPAD. This rather negative result for general games has not settled the question, however, but immediately raises several new ones: First, can Nash equilibria be approximated, i.e., is it possible to efficiently find a solution such that the potential gain from a unilateral deviation is small? Second, are there interesting classes of games that do allow for an exact solution to be computed efficiently? Third, are there alternative solution concepts that are computationally tractable, and how does the value of solutions selected by these concepts compare to those selected by established solution concepts?

The work reported in this thesis is part of the effort to answer the latter two questions. We study the complexity of well-known solution concepts, like Nash equilibrium and iterated dominance, in various classes of games that are both natural and practically relevant: ranking games, where outcomes are rankings of the players; anonymous games, where players do not distinguish between the other players in the game; and graphical games, where the well-being of any particular player depends only on the actions of a small group other players. In ranking games, we further compare the payoffs obtainable in Nash equilibrium outcomes with those of alternative solution concepts that are easy to compute. We finally study, in general games, solution concepts that try to remedy some of the shortcomings associated with Nash equilibrium, like the need for randomization to achieve a stable outcome.

In this thesis, a novel sequential genes selection and classification (k-SS) method is proposed. The method is analogous to the classical non-linear stepwise variable selection (SVS) methods but unlike any of the SVS methods, this new method uses the misclassification error rates (MERs) as its search criteria for informative marker genes in any given microarray data. Here, the importance of any selected gene is determined based on its marginal contribution at improving the prediction accuracy of the classification rule. This method ensures continuous selection of more genes in as much as the improvements brought into the decision models by the selected genes are considered to be significant enough by some established test criteria. However, further gene selection terminates when none of the remaining genes is capable at improving the prediction accuracy (lowering the MER) of the current model. Therefore, our approach only seeks to select the best combination of k marker genes that are most predictive of the biological samples in any given microarray data sets.

An important feature of our new k-SS method is that the size α used by its test is not arbitrarily fixed by the user as common to some of the classical SVS methods. Rather, the value of α at which the best prediction accuracy is achieved (or the best combination of genes is selected) is determined by cross-validation.

The new k-SS classifier competes favourably with selected eight existing classification methods using eleven published microarray data sets. The k-SS classifier is very simple to apply and does not require any rigid assumption for its implementation. Another merit of this method lies in its ability to select only those genes that are of biological relevance to the existing cancer sub-groups in microarray data sets.

Lastly, we proposed a new preliminary feature selection procedure that employs the cross-validated area under the ROC curve (CVAUC) for gene selection. This method is capable at removing all the irrelevant genes at the preliminary selection stage before any standard classifier like the k-SS method is employed on the remaining data set for final optimum gene selection and classification of mRNA samples. Unlike some other data pruning methods, the new method employs the sub-sampling technique of the v-fold cross-validation to ensure consistency and efficiency of selections made at the preliminary selection stage.

Die steigende Komplexität von IT-Diensten führt zu neuen Herausforderungen im IT-Service-Management(ITSM). Aufgrund von neuartigen SourcingModellen, Trends wie eBusiness oder auch regulatorischen Vorgaben wächst zunehmend die Notwendigkeit, aber auch die Gelegenheit für eine partnerschaftliche Kollaboration zwischen IT Providern.

Jenseits des hierarchischen Modells in der Zusammenarbeit von IT Providern, bei dem ein fokaler Provider eine Reihe von weiteren Dienstleistern mit der Erbringung von Basisdiensten beauftragt, gewinnen alternative Formen der Kooperation an Bedeutung. Die Gewährleistung einer definierten Ende-zu-Ende Dienstqualität ist dabei eine der wichtigsten Herausforderungen. Die Zusammenarbeit von IT Providern erfordert die Spezifikation von interorganisationalen Betriebsprozessen. Die etablierten

ITSM Frameworks adressieren jedoch alternative Formen der Diensterbringung nicht; so bleiben kooperierende IT Provider bei der Definition von interorganisationalen

ITSMProzessen als Basis ihrer Zusammenarbeit weitgehend auf sich alleine gestellt.

Um auf die spezifischen Herausforderungen von Szenarien eingehen zu können, die von den etablierten ITSM Frameworks nicht abgedeckt werden, fokussiert diese Arbeit auf die Dienstklasse der Verketteten Dienste, das sind providerübergreifende, horizontale Dienstketten auf der gleichen funktionalen Schicht. Im Unterschied zu klassischen

Szenarien der kooperativen Erbringung von ITDiensten, wie z.B. IP Peering im Internet, wird für Verkettete Dienste eine definierte Dienstqualität und ein serviceorientiertes

Management gefordert.

Der erste Teil der Arbeit leistet auf der Basis einer Untersuchung realer Szenarien eine eingehende Analyse der ManagementHerausforderungen und der spezifischen Anforderungen für die Prozessdefinition Verketteter Dienste. Zur Kategorisierung der vielfältigen Formen der Zusammenarbeit von Providern wird ein Raster von Koordinationsmustern definiert. Die Betrachtung des Status Quo zeigt, dass, obwohl eine Reihe von Vorarbeiten in den Disziplinen des IT-Service-Managements sowie der Informations- und Prozessmodellierung vorliegt, die Anwendung von universellen Modellierungssprachen auf interorganisationale ITSMProzesse derzeit kaum abgedeckt wird. Im Hauptteil der Arbeit wird dazu die neue Methode ITSMCooP (ITSM Processes for Cooperating Providers) eingeführt. Aufbauend auf der Prozessmodellierungssprache

BPMN und dem Shared Information/Data Model (SDI) des TeleManagement-Forums, besteht die Methode aus einer Sammlung von Modellierungskonventionen und Empfehlungen, die alle relevanten Aspekte der Modellierung von interorganisationalen Prozessen abdecken. Die Erstellung von Informations- und Prozessmodellen

wird geleitet von einer Vorgehensweise zur Prozessdefinition, die sowohl Referenzprozesse der ITSM Frameworks als auch die spezifischen Koordinationsmuster Verketteter Dienste berücksichtigt. Die Arbeit wird abgerundet durch die Anwendung der Methode ITSMCooP auf ein reales, komplexes Szenario.

The concept of self-organized criticality was proposed as an explanation for the occurrence of fractal structures in diverse natural phenomena. Roughly speaking the idea behind self-organized criticality is that a dynamic drives a system towards a stationary state that is characterized by power law correlations in space and time. We study two of the most famous models that were introduced as models exhibiting self-organized criticality.

The first of them is the forest fire model. In a forest fire model each site (vertex) of a graph is either vacant or occupied by a tree. Vacant sites get occupied according to independent rate 1 Poisson processes. Independently, at each sites ignition (by lightning) occurs according to independent Poisson processes that have rate Lambda>0. When a site is ignited its whole cluster of occupied sites becomes vacant instantaneously.

It is known that infinite volume forest fire processes exist for all ignition rates Lambda>0. The proof of existence is rather abstract, and does not imply uniqueness. Nor does the construction answer the question whether infinite volume forest fire processes are measurable with respect to their driving Poisson processes. Motivated by these questions, we show the almost sure infinite volume convergence for forest fire models with respect to their driving Poisson processes. Our proof is quite general and covers all graphs with bounded vertex, all positive ignition rates Lambda>0, and a quite large set of initial configurations. One of the main ingredients of the proof is an estimate for the decay of the cluster size distribution in a forest fire model. For Gamma>0, we study the probability that the cluster at site x and time t>=Gamma is larger than m, conditioned on the configuration of some further clusters at time t. We show that as m tends to infinity, this conditional probability decays to zero. The convergence is uniform in the choice of the site x, the time t, and the configuration of the further clusters we condition on. Being a consequence of almost sure infinite volume convergence, we obtain uniqueness and measurability with respect to the driving Poisson processes, and the Markov property.

The second model in focus is the Abelian sandpile model. Let Lambda be a finite subset of the two-dimensional integer lattice. We consider the following sandpile model on Lambda: each vertex in Lambda contains a sandpile with a height between one and four sand grains. At discrete times, we choose a site v in Lambda randomly and add a sand grain at the site v. If after adding the sand grain the height at the site v is strictly larger than four, then the site topples. That is, four sand grains leave the site v, and each distance-one-neighbour of v gets one of these grains. If after toppling the site v there are other sites with a height strictly larger than four, we continue by toppling these sites until we obtain a configuration where all sites have a height between one and four.

We study the scaling limit for the height one field in such a sandpile model. More precisely, we identify the scaling limit for the covariance of having height one at two macroscopically distant sites. We show that this scaling limit is conformally covariant. Furthermore, we show a central limit theorem for the sandpile height one field. Our results are based on a representation of the height one joint intensities that is close to a block-determinantal structure.

In this thesis, hierarchical graphs are investigated from two different angles – as a general modelling principle for (geo)spatial networks and as a practical means to enhance navigation in buildings. The topics addressed are of interest from a multi-disciplinary point of view, ranging from Computer Science in general over Artificial Intelligence

and Computational Geometry in particular to other fields such as Geographic Information Science.

Some hierarchical graph models have been previously proposed by the research community, e.g. to cope with the massive size of road networks, or as a conceptual model for human wayfinding. However, there has not yet been a comprehensive, systematic approach for modelling spatial networks with hierarchical graphs. One particular

problem is the gap between conceptual models and models which can be readily used in practice. Geospatial data is commonly modelled - if at all - only as a flat graph. Therefore, from a practical point of view, it is important to address the automatic construction of a graph hierarchy based on the predominant data models. The work presented deals with this problem: an automated method for construction is introduced and explained. A particular contribution of my thesis is the proposition to use hierarchical graphs as the basis for an extensible, flexible architecture for modelling various (geo)spatial networks. The proposed approach complements classical graph models very well in the sense that their expressiveness is extended: various graphs originating from different

sources can be integrated into a comprehensive, multi-level model.

This more sophisticated kind of architecture allows for extending navigation services beyond the borders of one single spatial network to a collection of heterogeneous networks, thus establishing a meta-navigation service. Another point of discussion is the impact of the hierarchy and distribution on graph algorithms. They have to be

adapted to properly operate on multi-level hierarchies.

By investigating indoor navigation problems in particular, the guiding principles are demonstrated for modelling networks at multiple levels of detail. Complex environments like large public buildings are ideally suited to demonstrate the versatile use of hierarchical

graphs and thus to highlight the benefits of the hierarchical approach.

Starting from a collection of floor plans, I have developed a systematic method for constructing a multi-level graph hierarchy. The nature of indoor environments, especially their inherent diversity, poses an additional challenge: among others, one must deal with complex, irregular, and/or three-dimensional features. The proposed method is also motivated by practical considerations, such as not only finding shortest/fastest paths across rooms and floors, but also by providing descriptions for these paths which are easily understood by people.

Beyond this, two novel aspects of using a hierarchy are discussed: one as an informed heuristic exploiting the specific characteristics of indoor environments in order to enhance classical, general-purpose graph search techniques. At the same time, as a convenient by-

product of this method, clusters such as sections and wings can be detected. The other reason is to better deal with irregular, complex-shaped regions in a way that instructions can also be provided for these spaces. Previous approaches have not considered this problem.

In summary, the main results of this work are:

• hierarchical graphs are introduced as a general spatial data infrastructure. In particular, this architecture allows us to integrate different spatial networks originating from different sources. A small but useful set of operations is proposed for integrating these networks. In order to work in a hierarchical model, classical graph algorithms are generalised. This finding also has implications on the possible integration of separate

navigation services and systems;

• a novel set of core data struc