No description available.

Die Universität Leipzig verändert ihr Antlitz. Sichtbar wird dies nicht nur auf dem Campus am Augustusplatz, sondern auch am Jahresbericht. Nach der durchweg günstigen Aufnahme der inhaltlich und gestalterisch neuen Form der Ausgabe für das Jahr 2006/2007, freue ich mich, Ihnen mit diesem Bericht auch die Arbeitsergebnisse der Universität für das Akademische Jahr 2007/2008 in Wort und Bild präsentieren zu können. Es war wieder ein sehr spannendes und aufregendes Jahr für uns. Zum einen sind es die Probleme und Herausforderungen, die sich aus der Umsetzung der komplexen Studienreform und ihrer Überlagerung mit dem Hochschulpakt 2020 ergeben, und zum anderen die rasch aufeinander folgenden Exzellenzinitiativen in der Forschung von Bund und Ländern sowie des Freistaates. Hinzu kommen die Vorbereitung des 600. Jubiläums unserer Universität im Jahr 2009 und das Neu- und Umbauvorhaben am Augustusplatz.

Das zurückliegende Jahr 2009 war für die Universität Leipzig ein ganz besonderes, seit langem geplant und sorgfältig vorbereitet: Die Universität Leipzig erinnerte an ihre Gründung vor 600 Jahren. Parallel zu den zentralen Veranstaltungen wurden rund 300 Ausstellungen, Tagungen, Fachkongresse, studentische Projekte der Initiative „Studierende 2009“ und Konzerte durchgeführt. Lehre und Forschung ruhten im Jubiläumsjahr 2009 jedoch nicht. Diskussionspunkte der Studienreform waren die Beseitigung der Überlastsituation und die Reform des Wahlbereiches in den geistes- und sozialwissenschaftlichen Studiengängen, die Reduzierung der Prüfungslast und die Akkreditierung neuer Studiengänge.

Der in diesem Jahr erstmals erscheinende „Jahresspiegel“ ersetzt den Statistikteil des bisherigen Jahresberichts der Universität Leipzig. Mit diesem neuen Berichtsformat soll in kompakter Form gegenüber den Mitgliedern und Angehörigen der Universität, ihren Förderern und Freunden sowie einer breiten Öffentlichkeit Rechenschaft über die im Jahr 2011 erreichten Ziele und Ergebnisse der Universität abgelegt werden. Aus der Vielzahl der Aufgaben, Ergebnisse und Ereignisse sollen hier nur schlaglichtartig einige wesentliche und prägende genannt werden.

Nach 2011 erscheint nun die 2. Ausgabe des "Jahresspiegels". Damit soll – wie es das Sächsische Hochschulgesetz vorsieht – insbesondere über wesentliche Daten der entwicklung der Universität und ergebnisse der leistungsprozesse in Forschung und Lehre informiert werden.

Mit dem nun im dritten Jahr erscheinenden "Jahresspiegel" informiert die Universitätsleitung über Eckdaten der Entwicklung der Universität und Ergebnisse der Leistungsprozesse in Forschung, Lehre und Verwaltung des abgelaufenen Jahres 2013.

Mathematical logic and automata theory are two scientific disciplines with a close relationship that is not only fundamental for many theoretical results but also forms the basis of a coherent methodology for the verification and synthesis of computing systems. This connection goes back to a much longer history in the 1960s, through the fundamental work of Büchi-Elgot-Trakhtenbrot, which shows the expressive equivalence of automata and logical systems such as monadic second-order logic on finite and infinite words. This allowed the handling of specifications (where global system properties are stated), and implementations (which involve the definition of the local steps in order to satisfy the global goals laid out in the specifications) in a single framework. This connection has been extended to and well-investigated for many other structures such as trees, finite pictures, timed words and data words. For many computer science applications, however, quantitative phenomena need to be modelled, as well. Examples are vagueness and uncertainty of a statement, length of time periods, spatial information, and resource consumption. Weighted automata, introduced by Schützenberger, are prominent models for quantitative aspects of systems. The framework of weighted monadic second-order logic over words was first introduced by Droste and Gastin. They gave a characterization of quantitative behavior of weighted finite automata, as semantics of monadic second-order sentences within their logic. Meanwhile, the idea of weighted logics was also applied to devices recognizing more general structures such as weighted tree automata, weighted automata on infinite words or traces. The main goal of this thesis is to give logical characterizations for weighted automata models on pictures and data words as well as for Büchi-tiling systems in the spirit of the classical Büchi-Elgot theorem. As the second goal, we deal with synchronizing problem for data words. Below, we briefly summarize the contents of this thesis. Informally, a two-dimensional string is called a picture and is defined as a rectangular array of symbols taken from a finite alphabet. A two-dimensional language (or picture language) is a set of pictures. Picture languages have been intensively investigated by several research groups. In Chapter 1, we define weighted two-dimensional on-line tessellation automata (W2OTA) taking weights from a new weight structure called picture valuation monoid. This new weighted picture automaton model can be used to model several applications, e.g. the average density of a picture. Such aspects could not be modelled by semiring weighted picture automaton model. The behavior of this automaton model is a picture series mapping pictures over an alphabet to elements of a picture valuation monoid. As one of our main results, we prove a Nivat theorem for W2OTA. It shows that recognizable picture series can be obtained precisely as projections of particularly simple unambiguously recognizable series restricted to unambiguous recognizable picture languages. In addition, we introduce a weighted monadic second-order logic (WMSO) which can model average density of pictures. As the other main result, we show that W2OTA and a suitable fragment of our weighted MSO logic are expressively equivalent. In Chapter 2, we generalize the notion of finite pictures to +ω-pictures, i.e., pictures which have finite number of rows and infinite number of columns. We extend conventional tiling systems with a Büchi acceptance condition in order to define the class of Büchi-tiling recognizable +ω-picture languages. The class of recognizable +ω-picture languages is indeed, a natural generalization of ω-regular languages. We show that the class of all Büchi-tiling recognizable +ω-picture languages has the similar closure properties as the class of tiling recognizable languages of finite pictures: it is closed under projection, union, and intersection, but not under complementation. While for languages of finite pictures, tiling recognizability and EMSO-definability coincide, the situation is quite different for languages of +ω-pictures. In this setting, the notion of tiling recognizability does not even cover the language of all +ω -pictures over Σ = {a, b} in which the letter a occurs at least once – a picture language that can easily be defined in first-order logic. As a consequence, EMSO is too strong for being captured by the class of tiling recognizable +ω-picture languages. On the other hand, EMSO is too weak for being captured by the class of all Büchi-tiling recognizable +ω-picture languages. To obtain a logical characterization of this class, we introduce the logic EMSO∞, which extends EMSO with existential quantification of infinite sets. Additionally, using combinatorial arguments, we show that the Büchi characterization theorem for ω-regular languges does not carry over to the Büchi-tiling recognizable +ω-picture languages. In Chapter 3, we consider the connection between weighted register automata and weighted logic on data words. Data words are sequences of pairs where the first element is taken from a finite alphabet (as in classical words) and the second element is taken from an infinite data domain. Register automata, introduced by Francez and Kaminski, provide a widely studied model for reasoning on data words. These automata can be considered as classical nondeterministic finite automata equipped with a finite set of registers which are used to store data in order to compare them with some data in the future. In this chapter, for quantitative reasoning on data words, we introduce weighted register automata over commutative data semirings equipped with a collection of binary data functions in the spirit of the classical theory of weighted automata. Whereas in the models of register automata known from the literature data are usually compared with respect to equality or a linear order, here we allow data comparison by means of an arbitrary collection of binary data relations. This approach permits easily to incorporate timed automata and weighted timed automata into our framework. Motivated by the seminal Büchi-Elgot-Trakhtenbrot theorem about the expressive equivalence of finite automata and monadic second-order (MSO) logic and by the weighted MSO logic of Droste and Gastin, we introduce weighted MSO logic on data words and give a logical characterization of weighted register automata. In Chapter 4, we study the concept of synchronizing data words in register automata. The synchronizing problem for data words asks whether there exists a data word that sends all states of the register automaton to a single state. The class of register automata that we consider here has a decidable non-emptiness problem, and the subclass of nondeterministic register automata with a single register has a decidable non-universality problem. We provide the complexity bounds of the synchronizing problem in the family of deterministic register automata with k registers (k-DRA), and in the family of nondeterministic register automata with single register (1-NRA), and in general undecidability of the problem in the family of k-NRA. To this end, we prove that, for k-DRA, inputting data words with only 2k + 1 distinct data values, from the infinite data domain, is sufficient to synchronize. Then, we show that the synchronizing problem for k-DRA is in general PSPACE-complete, and it is in NLOGSPACE for 1-DRA. For nondeterministic register automata (NRA), we show that Ackermann(n) distinct data, where n is the number of states of the register automaton, might be necessary to synchronize. Then, by means of a construction, proving that the synchronizing problem and the non-universality problem in 1-NRA are interreducible, we show the Ackermann-completeness of the problem for 1-NRA. However, for k-NRA, in general, we prove that this problem is undecidable due to the unbounded length of synchronizing data words.

Bei Lernprozessen spielt das Anwenden der zu erlernenden Tätigkeit eine wichtige Rolle. Im Kontext der Ausbildung an Schulen und Hochschulen bedeutet dies, dass es wichtig ist, Schülern und Studierenden ausreichend viele Übungsmöglichkeiten anzubieten. Die von Lehrpersonal bei einer "Korrektur" erstellte Rückmeldung, auch Feedback genannt, ist jedoch teuer, da der zeitliche Aufwand je nach Art der Aufgabe beträchtlich ist. Eine Lösung dieser Problematik stellen E-Learning-Systeme dar. Geeignete Systeme können nicht nur Lernstoff präsentieren, sondern auch Übungsaufgaben anbieten und nach deren Bearbeitung quasi unmittelbar entsprechendes Feedback generieren. Es ist jedoch im Allgemeinen nicht einfach, maschinelle Verfahren zu implementieren, die Bearbeitungen von Übungsaufgaben korrigieren und entsprechendes Feedback erstellen. Für einige Aufgabentypen, wie beispielsweise Multiple-Choice-Aufgaben, ist dies zwar trivial, doch sind diese vor allem dazu gut geeignet, sogenanntes Faktenwissen abzuprüfen. Das Einüben von Lernzielen im Bereich der Anwendung ist damit kaum möglich. Die Behandlung dieser nach gängigen Taxonomien höheren kognitiven Lernziele erlauben sogenannte offene Aufgabentypen, deren Bearbeitung meist durch die Erstellung eines Freitexts in natürlicher Sprache erfolgt. Die Information bzw. das Wissen, das Lernende eingeben, liegt hier also in sogenannter „unstrukturierter“ Form vor. Dieses unstrukturierte Wissen ist maschinell nur schwer verwertbar, sodass sich Trainingssysteme, die Aufgaben dieser Art stellen und entsprechende Rückmeldung geben, bisher nicht durchgesetzt haben. Es existieren jedoch auch offene Aufgabentypen, bei denen Lernende das Wissen in strukturierter Form eingeben, so dass es maschinell leichter zu verwerten ist. Für Aufgaben dieser Art lassen sich somit Trainingssysteme erstellen, die eine gute Möglichkeit darstellen, Schülern und Studierenden auch für praxisnahe Anwendungen viele Übungsmöglichkeiten zur Verfügung zu stellen, ohne das Lehrpersonal zusätzlich zu belasten. In dieser Arbeit wird beschrieben, wie bestimmte Eigenschaften von Aufgaben ausgenutzt werden, um entsprechende Trainingssysteme konzipieren und implementieren zu können. Es handelt sich dabei um Aufgaben, deren Lösungen strukturiert und maschinell interpretierbar sind. Im Hauptteil der Arbeit werden vier Trainingssysteme bzw. deren Komponenten beschrieben und es wird von den Erfahrungen mit deren Einsatz in der Praxis berichtet: Eine Komponente des Trainingssystems „CaseTrain“ kann Feedback zu UML Klassendiagrammen erzeugen. Das neuartige Trainingssystem „WARP“ generiert zu UML Aktivitätsdiagrammen Feedback in mehreren Ebenen, u.a. indem es das durch Aktivitätsdiagramme definierte Verhalten von Robotern in virtuellen Umgebungen visualisiert. Mit „ÜPS“ steht ein Trainingssystem zur Verfügung, mit welchem die Eingabe von SQL-Anfragen eingeübt werden kann. Eine weitere in „CaseTrain“ implementierte Komponente für Bildmarkierungsaufgaben ermöglicht eine unmittelbare, automatische Bewertung entsprechender Aufgaben. Die Systeme wurden im Zeitraum zwischen 2011 und 2014 an der Universität Würzburg in Vorlesungen mit bis zu 300 Studierenden eingesetzt und evaluiert. Die Evaluierung ergab eine hohe Nutzung und eine gute Bewertung der Studierenden der eingesetzten Konzepte, womit belegt wurde, dass elektronische Trainingssysteme für offene Aufgaben in der Praxis eingesetzt werden können. / In learning processes, the application of skills plays a central role. In the context of education at schools and universities, this means that it is important to offer a sufficient number of practice opportunities to pupils and students. However, the feedback created by teachers at an assessment is expensive because of the amount of time involved. A solution of this problem are e-learning systems. Suitable systems can not only present learning content, but also offer exercises and generate immediate, appropriate feedback. However, it is not straightforward in general to design automatic methods that help to assess exercises and generate appropriate feedback. For or some task types, such as multiple-choice questions, this is indeed trivial. However, these are especially well suited for assessing factual knowledge. The practicing of learning objectives in the field of application is therefore hardly possible. So-called open-ended tasks allow the treatment of these (according to standard taxonomies) higher cognitive learning objectives. These tasks are usually processed by creating a free text in natural language. The information and knowledge that learners hereby show, is presented in so-called “unstructured” form. This unstructured knowledge is hardly machine-recognizable, so training systems being able to give appropriate feedback to open-ended tasks are not established. However, there are also open-ended task types in which learners present the knowledge in a structured form, which is more likely to be machine-recognizable in a sufficient way. Therefore, training systems for these tasks can be implemented, which are a great way to provide exercises to pupils and students without burdening the teaching staff. This work describes how certain properties of tasks are used to design and implement appropriate training systems. In the main part of the work, four training systems and their components are described and it is reported on the experience of their use in practice: A component of the training system "Case Train" is able to generate feedback on UML class diagrams. The novel training system "WARP" generates feedback for UML activity diagrams on several levels, including the visualization of the behavior of robots in virtual environments which before is defined by activity diagrams. "ÜPS" is a training system, with which the input of SQL queries can be practiced. Another "Case Train" component for image labeling tasks allows an immediate, automatic valuation of such tasks. The systems were used and evaluated in lectures at the University of Würzburg with up to 300 students in the period 2011-2014. The evaluation showed that students indeed use and value the systems, which is an evidence that electronic training systems for open tasks can be used in practice.

Die Dissertation „Ontologiebasiertes Cloud Computing“ im Fachbereich Wirtschaftsinformatik behandelt das Thema Cloud Computing und veranschaulicht die Möglichkeiten der theoretischen und praktischen Nutzung einer Ontologie für das Cloud Computing. Neben den Private und Public Clouds sowie Hybrid-Lösungen wird vor allem eine ausgefeilte Virtualisierungstechnologie die Zukunft im IT-Bereich mitgestalten. Die Vielfalt und Anzahl der angebotenen Services nimmt besonders auf dem Sektor der Public Clouds weiterhin stark zu, während im Hybrid-Bereich ansprechende Lösungen noch ausstehen. Das Nutzen eines Cloud-Services ist in der Regel einfach und wird mit den fallenden Preisen zunehmend interessanter. Eine Reihe von Punkten, die im Vorfeld genau betrachtet und festgelegt werden müssen, wie Aspekte der IT-Sicherheit, des Datenschutzes und der Kosten, ermöglichen eine wirtschaftliche und rechtssichere Inanspruchnahme eines Cloud-Services. Vor der Nutzung eines Services müssen zudem der Wert, die Nutzungshäufigkeit und die Geheimhaltungsstufe der eigenen Daten bekannt sein, um sicher bestimmen zu können, ob alle Informationen oder nur ein Teil zum Auslagern geeignet sind. Dazu bedarf es einer klaren Festlegung der vertraglichen Rahmenbedingungen und einer Regelung bezüglich des Schadensersatzes bei einem Ausfall. Ein aktives Change Management sollte schon vor der Einführung eines Services Akzeptanz für die sich im IT-Umfeld ändernden Aufgabengebiete schaffen. Vergleichbare Alternativen zu finden, dies war die Zielvorgabe der durchgeführten, breiten Untersuchung von 15 Serviceanbietern, verbunden mit dem Aufbau einer Ontologie. Auf einem sehr dynamischen Cloud Computing Markt können diese Untersuchungen natürlich nur eine Momentaufnahme abbilden, denn neue Provider etablieren sich, schon länger bestehende verändern und verbessern ihre Angebote. Damit diese Momentaufnahme nicht in einem statischen Endzustand verbleibt, wurde eine Ontologie aufgebaut, die die konsistente Einpflege veränderter Sachverhalte zulässt. Die Idealvorstellung ist es, dass beim Bekanntwerden einer neuen Information diese auch immer in die Ontologie einfließt. Die Anbieteruntersuchung zeigt, dass Cloud-Services heute schon ein hohes Potential haben. Um sich einen Gesamtüberblick über die unterschiedlichen Services und ihre Angebote zu verschaffen, ist eine Ontologie besonders geeignet. Die aufgebaute Cloud-Ontologie beinhaltet eine Service-Auswahl, die auf die Literatur- und Anbieteruntersuchung aufbaut. Ähnlich einer Suchmaschine hilft sie, sich über bestehende Angebote auf dem Markt zu informieren. Und sie vereinfacht die Selektion, definiert klar bekannte technische Details, erleichtert die Suche z. B. nach benötigten Zusatzdienstleistungen über standardisierte Schnittstellen, versucht Transparenz und Nachvollziehbarkeit bei den Abrechnungsmodellen herzustellen, um eine Vergleichbarkeit überhaupt erst zu ermöglichen. Der größte Vorteil liegt in der Zeitersparnis: Die Recherche nach passenden Cloud-Services wird durch formalisierte und somit vergleichbare Kriterien verkürzt. Bei mehreren passenden Anbietern lässt sich über weitere Abfragen oder Kostenvergleiche der jeweils für den Nutzer beste Anbieter gezielt finden. Ebenso können Services mit signifikanten Ausschlusskriterien frühzeitig aus der Auswahl entfernt werden. Durch das Verbot bestimmter Zuweisungen oder durch die Forderung von Mindestbedingungen innerhalb der Ontologie wird die Einpflege falscher Sachverhalte verhindert und sie erweist sich damit wesentlich unempfindlicher als viele Programme. Die Aufgabenstellung bei der Modellerstellung lag darin, zu einer allgemeinen Aussagekraft der modellierten Abhängigkeiten zu kommen. Außerdem erfüllt die Cloud-Ontologie die vier typischen Anforderungen an eine Ontologie: Sie ist ausschließlich durch die standardisierte Sprache OWL beschrieben, kann durch einen Inferenzalgorithmus (z. B. Pellet) ausgewertet werden, unterscheidet eindeutig zwischen 80 Klassen und 342 Individuals und bildet zahlreiche Informationen über 2657 Verknüpfungen ab. Die Ontologie kann mit geringem Aufwand auch in ein Programm mit einer ansprechenden Oberfläche überführt werden, wie der programmierte Prototyp beweist. In der Praxis müssen für Unternehmen verstärkt Hilfsmittel angeboten werden oder in den Vordergrund rücken, wie Cloud-Ontologien, die die Auswahl von Services erleichtern, Vergleiche erst ermöglichen, die Suche verkürzen und zum Schluss zu Ergebnissen führen, die den Vorstellungen des künftigen Nutzers entsprechen. / The thesis "Ontology-based cloud computing" in the subject Information Systems Research discusses Cloud Computing and illustrates the possibilities of theoretical and practical use of an ontology for cloud computing. In addition to private, public and hybrid clouds especially sophisticated virtualization technologies will shape the future of the IT sector. The variety and number of services offered will dramatically grow within the public cloud sector, while attractive hybrid solutions are yet to come. Using cloud services is usually simple and the interest in them will increase with falling prices. A number of issues need to be considered and determined precisely in advance: aspects of IT security, data protection and costs. Taken together this will enable economic use of cloud services with legal certainty. Prior to the use of a service an association has to evaluate the value, the frequency of use and the confidentiality level of their proprietary data in order to decide whether all information or only parts are suitable for outsourcing. This requires a clear definition of the contractual framework and regulations of damages in case of service inavailabilities. An active management should create acceptance for the changes in the IT environment before the introduction of a service. The objective of the presented broad survey was to find comparable alternatives among 15 service providers in combination with the construction of an ontology. In a highly dynamic cloud computing market, such a study obviously represents only a snapshot - new providers emerge, long established ones change and/or improve their offerings. In order not to remain in static, the ontology was constructed to allow for a consistent incorporation of changing circumstances. Ideally new information is fed continuously into the ontology. The provider survey shows that cloud services have a high potential already today. The ontology is especially useful to gain an overview over the different service providers and their offerings. The structured cloud ontology includes a selection of services that builds on the literature supplier research. Similar to a search engine, it helps to inform about existing offers on the market. Additionally it simplifies the selection, defines known technical details, facilitates the search for supplemental services via standardized interfaces and tries to establish transparency and accountability in the billing models to allow actual comparisons. The biggest advantage is time saving: The search for a suitable cloud services is shortened by formalized and thus comparable criteria. When several suitable providers exist, it offers the possibility to refine the results via further queries or cost comparisons to find the best match. Likewise, services can be excluded based on significant exclusion criteria early on during the selection. By prohibiting certain assignments or the requirement of minimum conditions within the ontology, the addition of false facts is prevented and it was therefore much more indulgent than many other programs. The definition of the project was to build a model with general validity of the conclusions drawn from the modeled dependencies. In addition, the cloud ontology satisfies the four typical requirements for an ontology: it is described solely by the standardized language OWL, can be evaluated by an inference algorithm (e.g. pellet), clearly distinguishes between 80 classes and 342 individuals and maps a lot of information to 2657 properties. The ontology can be loaded in to a program with an appealing user interface with only little effort, as demonstrated by the programmed prototype. In practice companies require more possibilities for searching matching cloud services. This can be reached by cloud ontologies, which facilitate the selection of services. They enable comparisons, shorten the search and eventually lead to results that meet the needs of a future user.

The general map-labeling problem is as follows: given a set of geometric objects to be labeled, or features, in the plane, and for each feature a set of label positions, maximize the number of placed labels such that there is at most one label per feature and no two labels overlap. There are three types of features in a map: point, line, and area features. Unfortunately, one cannot expect to find efficient algorithms that solve the labeling problem optimally. Interactive maps are digital maps that only show a small part of the entire map whereas the user can manipulate the shown part, the view, by continuously panning, zooming, rotating, and tilting (that is, changing the perspective between a top and a bird view). An example for the application of interactive maps is in navigational devices. Interactive maps are challenging in that the labeling must be updated whenever labels leave the view and, while zooming, the label size must be constant on the screen (which either makes space for further labels or makes labels overlap when zooming in or out, respectively). These updates must be computed in real time, that is, the computation must be so fast that the user does not notice that we spend time on the computation. Additionally, labels must not jump or flicker, that is, labels must not suddenly change their positions or, while zooming out, a vanished label must not appear again. In this thesis, we present efficient algorithms that dynamically label point and line features in interactive maps. We try to label as many features as possible while we prohibit labels that overlap, jump, and flicker. We have implemented all our approaches and tested them on real-world data. We conclude that our algorithms are indeed real-time capable. / Das allgemeine Beschriftungsproblem lautet wie folgt: Gegeben sei eine Menge von zu beschriftenden geometrischen Objekten (Referenzobjekte) in der Ebene und für jedes Referenzobjekt eine Menge von Beschriftungspositionen. Maximiere die Anzahl von gesetzten Beschriftungen, sodass jedes Referenzobjekt höchstens eine Beschriftung besitzt und keine zwei Beschriftungen überlappen. In Karten gibt es drei Arten von Referenzobjekten: Punkte, Linien und Gebiete. Leider können wir nicht davon ausgehen, dass es Algorithmen gibt, die das Beschriftungsproblem optimal und effizient, das heißt, mit kurzer Rechenzeit, lösen. Interaktive Karten sind digitale Karten wie sie zum Beispiel in Navigationsgeräten verwendet werden. Interaktive Karten zeigen nur einen Ausschnitt der gesamten Karte, wobei der Benutzer diesen Ausschnitt, den Sichtbereich, verändern kann: Der Benutzer kann den Sichtbereich verschieben, verkleinern und vergrößern (das heißt, heraus- und hineinzoomen), ihn rotieren und die Ansicht kippen, also zwischen Draufsicht und Vogelperspektive variieren. Diese spontanen Änderungen machen das Platzieren von Beschriftungen noch schwieriger. Sobald eine Beschriftung den Sichtbereich verlässt, sollte diese innerhalb des Sichtbereichs neu gesetzt werden. Beim Zoomen soll sich die Größe einer Beschriftung auf dem Bildschirm nicht ändern. Beim Herauszoomen müssen wir daher Beschriftungen löschen um Überlappungen zu verhindern. Beim Hineinzoomen entsteht Platz um weitere Beschriftungen zu platzieren. Diese Aktualisierungen müssen in Echtzeit durchgeführt werden, das heißt, sie müssen so schnell durchgeführt werden, dass der Benutzer nicht bemerkt, dass im Hintergrund neue Positionen berechnet werden. Eine weitere Anforderung interaktiver Karten ist, dass eine Beschriftung nicht springen oder flackern darf, das heißt, wenn eine Beschriftung ihre Position ändern muss, so soll sie sich kontinuierlich zu ihrer neuen Position bewegen, und, während der Benutzer hinauszoomt, darf eine gelöschte Beschriftung nicht wieder eingeblendet werden. In dieser Dissertation stellen wir effiziente Algorithmen vor, die Punkte und Linien dynamisch beschriften. Wir versuchen stets so viele Referenzobjekte wie möglich zu beschriften, wobei wir gleichzeitig fordern, dass die platzierten Beschriftungen weder springen, flackern, noch sich überlappen. Wir haben unsere Algorithmen implementiert und mit Hilfe von echten Kartendaten getestet. Tatsächlich sind unsere Algorithmen echtzeitfähig.