TY - THES A1 - Gerber, Stefan T1 - Using software for fault detection in arithmetical circuits Y1 - 1995 ER - TY - THES A1 - Tarnick, Steffen T1 - Data compression techniques for concurrent error detection and built-in self test Y1 - 1995 ER - TY - THES A1 - Kunz, Wolfgang T1 - Testing techniques in logic synthesis Y1 - 1996 ER - TY - THES A1 - Wildner, Uwe T1 - CASC : compiler assisted self-checking of structural integrity Y1 - 1997 ER - TY - THES A1 - Seuring, Markus T1 - Output space compaction for testing and concurrent checking N2 - In der Dissertation werden neue Entwurfsmethoden für Kompaktoren für die Ausgänge von digitalen Schaltungen beschrieben, die die Anzahl der zu testenden Ausgänge drastisch verkleinern und dabei die Testbarkeit der Schaltungen nur wenig oder gar nicht verschlechtern. Der erste Teil der Arbeit behandelt für kombinatorische Schaltungen Methoden, die die Struktur der Schaltungen beim Entwurf der Kompaktoren berücksichtigen. Verschiedene Algorithmen zur Analyse von Schaltungsstrukturen werden zum ersten Mal vorgestellt und untersucht. Die Komplexität der vorgestellten Verfahren zur Erzeugung von Kompaktoren ist linear bezüglich der Anzahl der Gatter in der Schaltung und ist damit auf sehr große Schaltungen anwendbar. Im zweiten Teil wird erstmals ein solches Verfahren für sequentielle Schaltkreise beschrieben. Dieses Verfahren baut im wesentlichen auf das erste auf. Der dritte Teil beschreibt eine Entwurfsmethode, die keine Informationen über die interne Struktur der Schaltung oder über das zugrundeliegende Fehlermodell benötigt. Der Entwurf basiert alleine auf einem vorgegebenen Satz von Testvektoren und die dazugehörenden Testantworten der fehlerfreien Schaltung. Ein nach diesem Verfahren erzeugter Kompaktor maskiert keinen der Fehler, die durch das Testen mit den vorgegebenen Vektoren an den Ausgängen der Schaltung beobachtbar sind. N2 - The objective of this thesis is to provide new space compaction techniques for testing or concurrent checking of digital circuits. In particular, the work focuses on the design of space compactors that achieve high compaction ratio and minimal loss of testability of the circuits. In the first part, the compactors are designed for combinational circuits based on the knowledge of the circuit structure. Several algorithms for analyzing circuit structures are introduced and discussed for the first time. The complexity of each design procedure is linear with respect to the number of gates of the circuit. Thus, the procedures are applicable to large circuits. In the second part, the first structural approach for output compaction for sequential circuits is introduced. Essentially, it enhances the first part. For the approach introduced in the third part it is assumed that the structure of the circuit and the underlying fault model are unknown. The space compaction approach requires only the knowledge of the fault-free test responses for a precomputed test set. The proposed compactor design guarantees zero-aliasing with respect to the precomputed test set. KW - digital circuit KW - output space compaction KW - zero-aliasing KW - test KW - concurrent checking KW - propagation probability KW - IP core Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-0000165 ER - TY - THES A1 - Rätsch, Gunnar T1 - Robust boosting via convex optimization N2 - In dieser Arbeit werden statistische Lernprobleme betrachtet. Lernmaschinen extrahieren Informationen aus einer gegebenen Menge von Trainingsmustern, so daß sie in der Lage sind, Eigenschaften von bisher ungesehenen Mustern - z.B. eine Klassenzugehörigkeit - vorherzusagen. Wir betrachten den Fall, bei dem die resultierende Klassifikations- oder Regressionsregel aus einfachen Regeln - den Basishypothesen - zusammengesetzt ist. Die sogenannten Boosting Algorithmen erzeugen iterativ eine gewichtete Summe von Basishypothesen, die gut auf ungesehenen Mustern vorhersagen. Die Arbeit behandelt folgende Sachverhalte: o Die zur Analyse von Boosting-Methoden geeignete Statistische Lerntheorie. Wir studieren lerntheoretische Garantien zur Abschätzung der Vorhersagequalität auf ungesehenen Mustern. Kürzlich haben sich sogenannte Klassifikationstechniken mit großem Margin als ein praktisches Ergebnis dieser Theorie herausgestellt - insbesondere Boosting und Support-Vektor-Maschinen. Ein großer Margin impliziert eine hohe Vorhersagequalität der Entscheidungsregel. Deshalb wird analysiert, wie groß der Margin bei Boosting ist und ein verbesserter Algorithmus vorgeschlagen, der effizient Regeln mit maximalem Margin erzeugt. o Was ist der Zusammenhang von Boosting und Techniken der konvexen Optimierung? Um die Eigenschaften der entstehenden Klassifikations- oder Regressionsregeln zu analysieren, ist es sehr wichtig zu verstehen, ob und unter welchen Bedingungen iterative Algorithmen wie Boosting konvergieren. Wir zeigen, daß solche Algorithmen benutzt werden koennen, um sehr große Optimierungsprobleme mit Nebenbedingungen zu lösen, deren Lösung sich gut charakterisieren laesst. Dazu werden Verbindungen zum Wissenschaftsgebiet der konvexen Optimierung aufgezeigt und ausgenutzt, um Konvergenzgarantien für eine große Familie von Boosting-ähnlichen Algorithmen zu geben. o Kann man Boosting robust gegenüber Meßfehlern und Ausreissern in den Daten machen? Ein Problem bisheriger Boosting-Methoden ist die relativ hohe Sensitivität gegenüber Messungenauigkeiten und Meßfehlern in der Trainingsdatenmenge. Um dieses Problem zu beheben, wird die sogenannte 'Soft-Margin' Idee, die beim Support-Vector Lernen schon benutzt wird, auf Boosting übertragen. Das führt zu theoretisch gut motivierten, regularisierten Algorithmen, die ein hohes Maß an Robustheit aufweisen. o Wie kann man die Anwendbarkeit von Boosting auf Regressionsprobleme erweitern? Boosting-Methoden wurden ursprünglich für Klassifikationsprobleme entwickelt. Um die Anwendbarkeit auf Regressionsprobleme zu erweitern, werden die vorherigen Konvergenzresultate benutzt und neue Boosting-ähnliche Algorithmen zur Regression entwickelt. Wir zeigen, daß diese Algorithmen gute theoretische und praktische Eigenschaften haben. o Ist Boosting praktisch anwendbar? Die dargestellten theoretischen Ergebnisse werden begleitet von Simulationsergebnissen, entweder, um bestimmte Eigenschaften von Algorithmen zu illustrieren, oder um zu zeigen, daß sie in der Praxis tatsächlich gut funktionieren und direkt einsetzbar sind. Die praktische Relevanz der entwickelten Methoden wird in der Analyse chaotischer Zeitreihen und durch industrielle Anwendungen wie ein Stromverbrauch-Überwachungssystem und bei der Entwicklung neuer Medikamente illustriert. N2 - In this work we consider statistical learning problems. A learning machine aims to extract information from a set of training examples such that it is able to predict the associated label on unseen examples. We consider the case where the resulting classification or regression rule is a combination of simple rules - also called base hypotheses. The so-called boosting algorithms iteratively find a weighted linear combination of base hypotheses that predict well on unseen data. We address the following issues: o The statistical learning theory framework for analyzing boosting methods. We study learning theoretic guarantees on the prediction performance on unseen examples. Recently, large margin classification techniques emerged as a practical result of the theory of generalization, in particular Boosting and Support Vector Machines. A large margin implies a good generalization performance. Hence, we analyze how large the margins in boosting are and find an improved algorithm that is able to generate the maximum margin solution. o How can boosting methods be related to mathematical optimization techniques? To analyze the properties of the resulting classification or regression rule, it is of high importance to understand whether and under which conditions boosting converges. We show that boosting can be used to solve large scale constrained optimization problems, whose solutions are well characterizable. To show this, we relate boosting methods to methods known from mathematical optimization, and derive convergence guarantees for a quite general family of boosting algorithms. o How to make Boosting noise robust? One of the problems of current boosting techniques is that they are sensitive to noise in the training sample. In order to make boosting robust, we transfer the soft margin idea from support vector learning to boosting. We develop theoretically motivated regularized algorithms that exhibit a high noise robustness. o How to adapt boosting to regression problems? Boosting methods are originally designed for classification problems. To extend the boosting idea to regression problems, we use the previous convergence results and relations to semi-infinite programming to design boosting-like algorithms for regression problems. We show that these leveraging algorithms have desirable theoretical and practical properties. o Can boosting techniques be useful in practice? The presented theoretical results are guided by simulation results either to illustrate properties of the proposed algorithms or to show that they work well in practice. We report on successful applications in a non-intrusive power monitoring system, chaotic time series analysis and a drug discovery process. --- Anmerkung: Der Autor ist Träger des von der Mathematisch-Naturwissenschaftlichen Fakultät der Universität Potsdam vergebenen Michelson-Preises für die beste Promotion des Jahres 2001/2002. KW - Boosting KW - Klassifikation mit großem Margin KW - Support-Vector Lernen KW - Regression KW - Regularisierung KW - Mathematische Optimierung KW - Stromverbrauchüberwachung KW - Boosting KW - Large Margin Classification KW - Support Vectors KW - Regression KW - Regularization KW - Mathematical Optimization KW - Power Monitoring KW - Time Series Analysis Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-0000399 ER - TY - THES A1 - Huong, Dinh Thi Thanh T1 - Correctness proofs and probabilistic tests for constructive specifications and functional programs Y1 - 2001 ER - TY - THES A1 - Dramlitsch, Thomas T1 - Distributed computations in a dynamic, heterogeneous Grid environment N2 - Die immer dichtere und schnellere Vernetzung von Rechnern und Rechenzentren über Hochgeschwindigkeitsnetzwerke ermöglicht eine neue Art des wissenschaftlich verteilten Rechnens, bei der geographisch weit auseinanderliegende Rechenkapazitäten zu einer Gesamtheit zusammengefasst werden können. Dieser so entstehende virtuelle Superrechner, der selbst aus mehreren Grossrechnern besteht, kann dazu genutzt werden Probleme zu berechnen, für die die einzelnen Grossrechner zu klein sind. Die Probleme, die numerisch mit heutigen Rechenkapazitäten nicht lösbar sind, erstrecken sich durch sämtliche Gebiete der heutigen Wissenschaft, angefangen von Astrophysik, Molekülphysik, Bioinformatik, Meteorologie, bis hin zur Zahlentheorie und Fluiddynamik um nur einige Gebiete zu nennen. Je nach Art der Problemstellung und des Lösungsverfahrens gestalten sich solche "Meta-Berechnungen" mehr oder weniger schwierig. Allgemein kann man sagen, dass solche Berechnungen um so schwerer und auch um so uneffizienter werden, je mehr Kommunikation zwischen den einzelnen Prozessen (oder Prozessoren) herrscht. Dies ist dadurch begründet, dass die Bandbreiten bzw. Latenzzeiten zwischen zwei Prozessoren auf demselben Grossrechner oder Cluster um zwei bis vier Grössenordnungen höher bzw. niedriger liegen als zwischen Prozessoren, welche hunderte von Kilometern entfernt liegen. Dennoch bricht nunmehr eine Zeit an, in der es möglich ist Berechnungen auf solch virtuellen Supercomputern auch mit kommunikationsintensiven Programmen durchzuführen. Eine grosse Klasse von kommunikations- und berechnungsintensiven Programmen ist diejenige, die die Lösung von Differentialgleichungen mithilfe von finiten Differenzen zum Inhalt hat. Gerade diese Klasse von Programmen und deren Betrieb in einem virtuellen Superrechner wird in dieser vorliegenden Dissertation behandelt. Methoden zur effizienteren Durchführung von solch verteilten Berechnungen werden entwickelt, analysiert und implementiert. Der Schwerpunkt liegt darin vorhandene, klassische Parallelisierungsalgorithmen zu analysieren und so zu erweitern, dass sie vorhandene Informationen (z.B. verfügbar durch das Globus Toolkit) über Maschinen und Netzwerke zur effizienteren Parallelisierung nutzen. Soweit wir wissen werden solche Zusatzinformationen kaum in relevanten Programmen genutzt, da der Grossteil aller Parallelisierungsalgorithmen implizit für die Ausführung auf Grossrechnern oder Clustern entwickelt wurde. N2 - In order to face the rapidly increasing need for computational resources of various scientific and engineering applications one has to think of new ways to make more efficient use of the worlds current computational resources. In this respect, the growing speed of wide area networks made a new kind of distributed computing possible: Metacomputing or (distributed) Grid computing. This is a rather new and uncharted field in computational science. The rapidly increasing speed of networks even outperforms the average increase of processor speed: Processor speeds double on average each 18 month whereas network bandwidths double every 9 months. Due to this development of local and wide area networks Grid computing will certainly play a key role in the future of parallel computing. This type of distributed computing, however, distinguishes from the traditional parallel computing in many ways since it has to deal with many problems not occurring in classical parallel computing. Those problems are for example heterogeneity, authentication and slow networks to mention only a few. Some of those problems, e.g. the allocation of distributed resources along with the providing of information about these resources to the application have been already attacked by the Globus software. Unfortunately, as far as we know, hardly any application or middle-ware software takes advantage of this information, since most parallelizing algorithms for finite differencing codes are implicitly designed for single supercomputer or cluster execution. We show that although it is possible to apply classical parallelizing algorithms in a Grid environment, in most cases the observed efficiency of the executed code is very poor. In this work we are closing this gap. In our thesis, we will - show that an execution of classical parallel codes in Grid environments is possible but very slow - analyze this situation of bad performance, nail down bottlenecks in communication, remove unnecessary overhead and other reasons for low performance - develop new and advanced algorithms for parallelisation that are aware of a Grid environment in order to generelize the traditional parallelization schemes - implement and test these new methods, replace and compare with the classical ones - introduce dynamic strategies that automatically adapt the running code to the nature of the underlying Grid environment. The higher the performance one can achieve for a single application by manual tuning for a Grid environment, the lower the chance that those changes are widely applicable to other programs. In our analysis as well as in our implementation we tried to keep the balance between high performance and generality. None of our changes directly affect code on the application level which makes our algorithms applicable to a whole class of real world applications. The implementation of our work is done within the Cactus framework using the Globus toolkit, since we think that these are the most reliable and advanced programming frameworks for supporting computations in Grid environments. On the other hand, however, we tried to be as general as possible, i.e. all methods and algorithms discussed in this thesis are independent of Cactus or Globus. KW - Paralleles Rechnen KW - Verteiltes Rechnen KW - Cactus KW - Globus KW - dynamisch KW - adaptiv KW - Grid Computing KW - Distributed Computing KW - Cactus KW - Globus KW - dynamic KW - adaptive Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-0000759 ER - TY - THES A1 - Lanfermann, Gerd T1 - Nomadic migration : a service environment for autonomic computing on the Grid N2 - In den vergangenen Jahren ist es zu einer dramatischen Vervielfachung der verfügbaren Rechenzeit gekommen. Diese 'Grid Ressourcen' stehen jedoch nicht als kontinuierlicher Strom zur Verfügung, sondern sind über verschiedene Maschinentypen, Plattformen und Betriebssysteme verteilt, die jeweils durch Netzwerke mit fluktuierender Bandbreite verbunden sind. Es wird für Wissenschaftler zunehmend schwieriger, die verfügbaren Ressourcen für ihre Anwendungen zu nutzen. Wir glauben, dass intelligente, selbstbestimmende Applikationen in der Lage sein sollten, ihre Ressourcen in einer dynamischen und heterogenen Umgebung selbst zu wählen: Migrierende Applikationen suchen eine neue Ressource, wenn die alte aufgebraucht ist. 'Spawning'-Anwendungen lassen Algorithmen auf externen Maschinen laufen, um die Hauptanwendung zu beschleunigen. Applikationen werden neu gestartet, sobald ein Absturz endeckt wird. Alle diese Verfahren können ohne menschliche Interaktion erfolgen. Eine verteilte Rechenumgebung besitzt eine natürliche Unverlässlichkeit. Jede Applikation, die mit einer solchen Umgebung interagiert, muss auf die gestörten Komponenten reagieren können: schlechte Netzwerkverbindung, abstürzende Maschinen, fehlerhafte Software. Wir konstruieren eine verlässliche Serviceinfrastruktur, indem wir der Serviceumgebung eine 'Peer-to-Peer'-Topology aufprägen. Diese “Grid Peer Service” Infrastruktur beinhaltet Services wie Migration und Spawning, als auch Services zum Starten von Applikationen, zur Dateiübertragung und Auswahl von Rechenressourcen. Sie benutzt existierende Gridtechnologie wo immer möglich, um ihre Aufgabe durchzuführen. Ein Applikations-Information- Server arbeitet als generische Registratur für alle Teilnehmer in der Serviceumgebung. Die Serviceumgebung, die wir entwickelt haben, erlaubt es Applikationen z.B. eine Relokationsanfrage an einen Migrationsserver zu stellen. Der Server sucht einen neuen Computer, basierend auf den übermittelten Ressourcen-Anforderungen. Er transferiert den Statusfile des Applikation zu der neuen Maschine und startet die Applikation neu. Obwohl das umgebende Ressourcensubstrat nicht kontinuierlich ist, können wir kontinuierliche Berechnungen auf Grids ausführen, indem wir die Applikation migrieren. Wir zeigen mit realistischen Beispielen, wie sich z.B. ein traditionelles Genom-Analyse-Programm leicht modifizieren lässt, um selbstbestimmte Migrationen in dieser Serviceumgebung durchzuführen. N2 - In recent years, there has been a dramatic increase in available compute capacities. However, these “Grid resources” are rarely accessible in a continuous stream, but rather appear scattered across various machine types, platforms and operating systems, which are coupled by networks of fluctuating bandwidth. It becomes increasingly difficult for scientists to exploit available resources for their applications. We believe that intelligent, self-governing applications should be able to select resources in a dynamic and heterogeneous environment: Migrating applications determine a resource when old capacities are used up. Spawning simulations launch algorithms on external machines to speed up the main execution. Applications are restarted as soon as a failure is detected. All these actions can be taken without human interaction. A distributed compute environment possesses an intrinsic unreliability. Any application that interacts with such an environment must be able to cope with its failing components: deteriorating networks, crashing machines, failing software. We construct a reliable service infrastructure by endowing a service environment with a peer-to-peer topology. This “Grid Peer Services” infrastructure accommodates high-level services like migration and spawning, as well as fundamental services for application launching, file transfer and resource selection. It utilizes existing Grid technology wherever possible to accomplish its tasks. An Application Information Server acts as a generic information registry to all participants in a service environment. The service environment that we developed, allows applications e.g. to send a relocation requests to a migration server. The server selects a new computer based on the transmitted resource requirements. It transfers the application's checkpoint and binary to the new host and resumes the simulation. Although the Grid's underlying resource substrate is not continuous, we achieve persistent computations on Grids by relocating the application. We show with our real-world examples that a traditional genome analysis program can be easily modified to perform self-determined migrations in this service environment. KW - Peer-to-Peer-Netz ; GRID computing ; Zuverlässigkeit ; Web Services ; Betriebsmittelverwaltung ; Migration KW - Grid KW - 'Peer To Peer' KW - Migration KW - Spawning Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-0000773 ER - TY - THES A1 - Harmeling, Stefan T1 - Independent component analysis and beyond N2 - 'Independent component analysis' (ICA) ist ein Werkzeug der statistischen Datenanalyse und Signalverarbeitung, welches multivariate Signale in ihre Quellkomponenten zerlegen kann. Obwohl das klassische ICA Modell sehr nützlich ist, gibt es viele Anwendungen, die Erweiterungen von ICA erfordern. In dieser Dissertation präsentieren wir neue Verfahren, die die Funktionalität von ICA erweitern: (1) Zuverlässigkeitsanalyse und Gruppierung von unabhängigen Komponenten durch Hinzufügen von Rauschen, (2) robuste und überbestimmte ('over-complete') ICA durch Ausreissererkennung, und (3) nichtlineare ICA mit Kernmethoden. N2 - Independent component analysis (ICA) is a tool for statistical data analysis and signal processing that is able to decompose multivariate signals into their underlying source components. Although the classical ICA model is highly useful, there are many real-world applications that require powerful extensions of ICA. This thesis presents new methods that extend the functionality of ICA: (1) reliability and grouping of independent components with noise injection, (2) robust and overcomplete ICA with inlier detection, and (3) nonlinear ICA with kernel methods. T2 - Independent component analysis and beyond KW - ICA KW - Zuverlässigkeitsanalyse KW - robuste ICA KW - überbestimmte ICA KW - Ausreissererkennung KW - nichtlineare ICA KW - Kern-PCA KW - Kernmethoden KW - ICA KW - reliability assessment KW - robust ICA KW - overcomplete ICA KW - outlier detection KW - nonlinear ICA KW - kernel PCA KW - kernel methods Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-0001540 ER - TY - THES A1 - Nienhaus, Marc T1 - Real-Time-Non-Photorealistic rendering techniques for illustrating 3D scenes and their dynamics Y1 - 2005 CY - Potsdam ER - TY - THES A1 - Ziehe, Andreas T1 - Blind source separation based on joint diagonalization of matrices with applications in biomedical signal processing T1 - Blinde Signalquellentrennung beruhend auf simultaner Diagonalisierung von Matrizen mit Anwendungen in der biomedizinischen Signalverarbeitung T1 - Blinde Signalquellentrennung beruhend auf simultaner Diagonalisierung von Matrizen mit Anwendungen in der biomedizinischen Signalverarbeitung N2 - This thesis is concerned with the solution of the blind source separation problem (BSS). The BSS problem occurs frequently in various scientific and technical applications. In essence, it consists in separating meaningful underlying components out of a mixture of a multitude of superimposed signals. In the recent research literature there are two related approaches to the BSS problem: The first is known as Independent Component Analysis (ICA), where the goal is to transform the data such that the components become as independent as possible. The second is based on the notion of diagonality of certain characteristic matrices derived from the data. Here the goal is to transform the matrices such that they become as diagonal as possible. In this thesis we study the latter method of approximate joint diagonalization (AJD) to achieve a solution of the BSS problem. After an introduction to the general setting, the thesis provides an overview on particular choices for the set of target matrices that can be used for BSS by joint diagonalization. As the main contribution of the thesis, new algorithms for approximate joint diagonalization of several matrices with non-orthogonal transformations are developed. These newly developed algorithms will be tested on synthetic benchmark datasets and compared to other previous diagonalization algorithms. Applications of the BSS methods to biomedical signal processing are discussed and exemplified with real-life data sets of multi-channel biomagnetic recordings. N2 - Diese Arbeit befasst sich mit der Lösung des Problems der blinden Signalquellentrennung (BSS). Das BSS Problem tritt häufig in vielen wissenschaftlichen und technischen Anwendungen auf. Im Kern besteht das Problem darin, aus einem Gemisch von überlagerten Signalen die zugrundeliegenden Quellsignale zu extrahieren. In wissenschaftlichen Publikationen zu diesem Thema werden hauptsächlich zwei Lösungsansätze verfolgt: Ein Ansatz ist die sogenannte "Analyse der unabhängigen Komponenten", die zum Ziel hat, eine lineare Transformation V der Daten X zu finden, sodass die Komponenten Un der transformierten Daten U = V X (die sogenannten "independent components") so unabhängig wie möglich sind. Ein anderer Ansatz beruht auf einer simultanen Diagonalisierung mehrerer spezieller Matrizen, die aus den Daten gebildet werden. Diese Möglichkeit der Lösung des Problems der blinden Signalquellentrennung bildet den Schwerpunkt dieser Arbeit. Als Hauptbeitrag der vorliegenden Arbeit präsentieren wir neue Algorithmen zur simultanen Diagonalisierung mehrerer Matrizen mit Hilfe einer nicht-orthogonalen Transformation. Die neu entwickelten Algorithmen werden anhand von numerischen Simulationen getestet und mit bereits bestehenden Diagonalisierungsalgorithmen verglichen. Es zeigt sich, dass unser neues Verfahren sehr effizient und leistungsfähig ist. Schließlich werden Anwendungen der BSS Methoden auf Probleme der biomedizinischen Signalverarbeitung erläutert und anhand von realistischen biomagnetischen Messdaten wird die Nützlichkeit in der explorativen Datenanalyse unter Beweis gestellt. KW - Signaltrennung KW - Mischung KW - Diagonalisierung KW - Bioelektrisches Signal KW - Magnetoencephalographie KW - Elektroencephalographie KW - Signalquellentrennung KW - Matrizen-Eigenwertaufgabe KW - Simultane Diagonalisierung KW - Optimierungsproblem KW - blind source separation KW - BSS KW - ICA KW - independent component analysis KW - approximate joint diagonalization KW - EEG KW - MEG Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-5694 ER - TY - THES A1 - Flöter, André T1 - Analyzing biological expression data based on decision tree induction T1 - Analyse biologischer Expressionsdaten mit Hilfe von Entscheidungsbauminduktion N2 - Modern biological analysis techniques supply scientists with various forms of data. One category of such data are the so called "expression data". These data indicate the quantities of biochemical compounds present in tissue samples. Recently, expression data can be generated at a high speed. This leads in turn to amounts of data no longer analysable by classical statistical techniques. Systems biology is the new field that focuses on the modelling of this information. At present, various methods are used for this purpose. One superordinate class of these meth­ods is machine learning. Methods of this kind had, until recently, predominantly been used for classification and prediction tasks. This neglected a powerful secondary benefit: the ability to induce interpretable models. Obtaining such models from data has become a key issue within Systems biology. Numerous approaches have been proposed and intensively discussed. This thesis focuses on the examination and exploitation of one basic technique: decision trees. The concept of comparing sets of decision trees is developed. This method offers the pos­sibility of identifying significant thresholds in continuous or discrete valued attributes through their corresponding set of decision trees. Finding significant thresholds in attributes is a means of identifying states in living organisms. Knowing about states is an invaluable clue to the un­derstanding of dynamic processes in organisms. Applied to metabolite concentration data, the proposed method was able to identify states which were not found with conventional techniques for threshold extraction. A second approach exploits the structure of sets of decision trees for the discovery of com­binatorial dependencies between attributes. Previous work on this issue has focused either on expensive computational methods or the interpretation of single decision trees ­ a very limited exploitation of the data. This has led to incomplete or unstable results. That is why a new method is developed that uses sets of decision trees to overcome these limitations. Both the introduced methods are available as software tools. They can be applied consecu­tively or separately. That way they make up a package of analytical tools that usefully supplement existing methods. By means of these tools, the newly introduced methods were able to confirm existing knowl­edge and to suggest interesting and new relationships between metabolites. N2 - Neuere biologische Analysetechniken liefern Forschern verschiedenste Arten von Daten. Eine Art dieser Daten sind die so genannten "Expressionsdaten". Sie geben die Konzentrationen biochemischer Inhaltsstoffe in Gewebeproben an. Neuerdings können Expressionsdaten sehr schnell erzeugt werden. Das führt wiederum zu so großen Datenmengen, dass sie nicht mehr mit klassischen statistischen Verfahren analysiert werden können. "System biology" ist eine neue Disziplin, die sich mit der Modellierung solcher Information befasst. Zur Zeit werden dazu verschiedenste Methoden benutzt. Eine Superklasse dieser Methoden ist das maschinelle Lernen. Dieses wurde bis vor kurzem ausschließlich zum Klassifizieren und zum Vorhersagen genutzt. Dabei wurde eine wichtige zweite Eigenschaft vernachlässigt, nämlich die Möglichkeit zum Erlernen von interpretierbaren Modellen. Die Erstellung solcher Modelle hat mittlerweile eine Schlüsselrolle in der "Systems biology" erlangt. Es sind bereits zahlreiche Methoden dazu vorgeschlagen und diskutiert worden. Die vorliegende Arbeit befasst sich mit der Untersuchung und Nutzung einer ganz grundlegenden Technik: den Entscheidungsbäumen. Zunächst wird ein Konzept zum Vergleich von Baummengen entwickelt, welches das Erkennen bedeutsamer Schwellwerte in reellwertigen Daten anhand ihrer zugehörigen Entscheidungswälder ermöglicht. Das Erkennen solcher Schwellwerte dient dem Verständnis von dynamischen Abläufen in lebenden Organismen. Bei der Anwendung dieser Technik auf metabolische Konzentrationsdaten wurden bereits Zustände erkannt, die nicht mit herkömmlichen Techniken entdeckt werden konnten. Ein zweiter Ansatz befasst sich mit der Auswertung der Struktur von Entscheidungswäldern zur Entdeckung von kombinatorischen Abhängigkeiten zwischen Attributen. Bisherige Arbeiten hierzu befassten sich vornehmlich mit rechenintensiven Verfahren oder mit einzelnen Entscheidungsbäumen, eine sehr eingeschränkte Ausbeutung der Daten. Das führte dann entweder zu unvollständigen oder instabilen Ergebnissen. Darum wird hier eine Methode entwickelt, die Mengen von Entscheidungsbäumen nutzt, um diese Beschränkungen zu überwinden. Beide vorgestellten Verfahren gibt es als Werkzeuge für den Computer, die entweder hintereinander oder einzeln verwendet werden können. Auf diese Weise stellen sie eine sinnvolle Ergänzung zu vorhandenen Analyswerkzeugen dar. Mit Hilfe der bereitgestellten Software war es möglich, bekanntes Wissen zu bestätigen und interessante neue Zusammenhänge im Stoffwechsel von Pflanzen aufzuzeigen. KW - Molekulare Bioinformatik KW - Maschinelles Lernen KW - Entscheidungsbäume KW - machine learning KW - decision trees KW - computational biology Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-6416 ER - TY - THES A1 - Ghasemzadeh, Mohammad T1 - A new algorithm for the quantified satisfiability problem, based on zero-suppressed binary decision diagrams and memoization T1 - Ein neuer Algorithmus für die quantifizierte Aussagenlogik, basierend auf Zero-suppressed BDDs und Memoization N2 - Quantified Boolean formulas (QBFs) play an important role in theoretical computer science. QBF extends propositional logic in such a way that many advanced forms of reasoning can be easily formulated and evaluated. In this dissertation we present our ZQSAT, which is an algorithm for evaluating quantified Boolean formulas. ZQSAT is based on ZBDD: Zero-Suppressed Binary Decision Diagram , which is a variant of BDD, and an adopted version of the DPLL algorithm. It has been implemented in C using the CUDD: Colorado University Decision Diagram package. The capability of ZBDDs in storing sets of subsets efficiently enabled us to store the clauses of a QBF very compactly and let us to embed the notion of memoization to the DPLL algorithm. These points led us to implement the search algorithm in such a way that we could store and reuse the results of all previously solved subformulas with a little overheads. ZQSAT can solve some sets of standard QBF benchmark problems (known to be hard for DPLL based algorithms) faster than the best existing solvers. In addition to prenex-CNF, ZQSAT accepts prenex-NNF formulas. We show and prove how this capability can be exponentially beneficial. N2 - In der Dissertation stellen wir einen neuen Algorithmus vor, welcher Formeln der quantifizierten Aussagenlogik (engl. Quantified Boolean formula, kurz QBF) löst. QBFs sind eine Erweiterung der klassischen Aussagenlogik um die Quantifizierung über aussagenlogische Variablen. Die quantifizierte Aussagenlogik ist dabei eine konservative Erweiterung der Aussagenlogik, d.h. es können nicht mehr Theoreme nachgewiesen werden als in der gewöhnlichen Aussagenlogik. Der Vorteil der Verwendung von QBFs ergibt sich durch die Möglichkeit, Sachverhalte kompakter zu repräsentieren. SAT (die Frage nach der Erfüllbarkeit einer Formel der Aussagenlogik) und QSAT (die Frage nach der Erfüllbarkeit einer QBF) sind zentrale Probleme in der Informatik mit einer Fülle von Anwendungen, wie zum Beispiel in der Graphentheorie, bei Planungsproblemen, nichtmonotonen Logiken oder bei der Verifikation. Insbesondere die Verifikation von Hard- und Software ist ein sehr aktuelles und wichtiges Forschungsgebiet in der Informatik. Unser Algorithmus zur Lösung von QBFs basiert auf sogenannten ZBDDs (engl. Zero-suppressed Binary decision Diagrams), welche eine Variante der BDDs (engl. Binary decision Diagrams) sind. BDDs sind eine kompakte Repräsentation von Formeln der Aussagenlogik. Der Algorithmus kombiniert nun bekannte Techniken zum Lösen von QBFs mit der ZBDD-Darstellung unter Verwendung geeigneter Heuristiken und Memoization. Memoization ermöglicht dabei das einfache Wiederverwenden bereits gelöster Teilprobleme. Der Algorithmus wurde unter Verwendung des CUDD-Paketes (Colorado University Decision Diagram) implementiert und unter dem Namen ZQSAT veröffentlicht. In Tests konnten wir nachweisen, dass ZQSAT konkurrenzfähig zu existierenden QBF-Beweisern ist, in einigen Fällen sogar bessere Resultate liefern kann. KW - Binäres Entscheidungsdiagramm KW - Erfüllbarkeitsproblem KW - DPLL KW - Zero-Suppressed Binary Decision Diagram (ZDD) KW - Formeln der quantifizierten Aussagenlogik KW - Erfüllbarkeit einer Formel der Aussagenlogik KW - ZQSA KW - DPLL KW - Zero-Suppressed Binary Decision Diagram (ZDD) KW - Quantified Boolean Formula (QBF) KW - Satisfiability KW - ZQSAT Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-6378 ER - TY - THES A1 - Leininger, Andreas T1 - New diagnosis and test methods with high compaction rates Y1 - 2006 SN - 3-86664-066-8 PB - Mensch & Buch Verl. CY - Berlin ER - TY - THES A1 - Hetzer, Dirk T1 - Adaptive Quality of Service based Bandwidth Planning in Internet Y1 - 2006 CY - Potsdam ER - TY - THES A1 - Dornhege, Guido T1 - Increasing information transfer rates for brain-computer interfacing T1 - Erhöhung der Informationstransferrate einer Gehirn-Computer-Schnittstelle N2 - The goal of a Brain-Computer Interface (BCI) consists of the development of a unidirectional interface between a human and a computer to allow control of a device only via brain signals. While the BCI systems of almost all other groups require the user to be trained over several weeks or even months, the group of Prof. Dr. Klaus-Robert Müller in Berlin and Potsdam, which I belong to, was one of the first research groups in this field which used machine learning techniques on a large scale. The adaptivity of the processing system to the individual brain patterns of the subject confers huge advantages for the user. Thus BCI research is considered a hot topic in machine learning and computer science. It requires interdisciplinary cooperation between disparate fields such as neuroscience, since only by combining machine learning and signal processing techniques based on neurophysiological knowledge will the largest progress be made. In this work I particularly deal with my part of this project, which lies mainly in the area of computer science. I have considered the following three main points: Establishing a performance measure based on information theory: I have critically illuminated the assumptions of Shannon's information transfer rate for application in a BCI context. By establishing suitable coding strategies I was able to show that this theoretical measure approximates quite well to what is practically achieveable. Transfer and development of suitable signal processing and machine learning techniques: One substantial component of my work was to develop several machine learning and signal processing algorithms to improve the efficiency of a BCI. Based on the neurophysiological knowledge that several independent EEG features can be observed for some mental states, I have developed a method for combining different and maybe independent features which improved performance. In some cases the performance of the combination algorithm outperforms the best single performance by more than 50 %. Furthermore, I have theoretically and practically addressed via the development of suitable algorithms the question of the optimal number of classes which should be used for a BCI. It transpired that with BCI performances reported so far, three or four different mental states are optimal. For another extension I have combined ideas from signal processing with those of machine learning since a high gain can be achieved if the temporal filtering, i.e., the choice of frequency bands, is automatically adapted to each subject individually. Implementation of the Berlin brain computer interface and realization of suitable experiments: Finally a further substantial component of my work was to realize an online BCI system which includes the developed methods, but is also flexible enough to allow the simple realization of new algorithms and ideas. So far, bitrates of up to 40 bits per minute have been achieved with this system by absolutely untrained users which, compared to results of other groups, is highly successful. N2 - Ein Brain-Computer Interface (BCI) ist eine unidirektionale Schnittstelle zwischen Mensch und Computer, bei der ein Mensch in der Lage ist, ein Gerät einzig und allein Kraft seiner Gehirnsignale zu steuern. In den BCI Systemen fast aller Forschergruppen wird der Mensch in Experimenten über Wochen oder sogar Monaten trainiert, geeignete Signale zu produzieren, die vordefinierten allgemeinen Gehirnmustern entsprechen. Die BCI Gruppe in Berlin und Potsdam, der ich angehöre, war in diesem Feld eine der ersten, die erkannt hat, dass eine Anpassung des Verarbeitungssystems an den Menschen mit Hilfe der Techniken des Maschinellen Lernens große Vorteile mit sich bringt. In unserer Gruppe und mittlerweile auch in vielen anderen Gruppen wird BCI somit als aktuelles Forschungsthema im Maschinellen Lernen und folglich in der Informatik mit interdisziplinärer Natur in Neurowissenschaften und anderen Feldern verstanden, da durch die geeignete Kombination von Techniken des Maschinellen Lernens und der Signalverarbeitung basierend auf neurophysiologischem Wissen der größte Erfolg erzielt werden konnte. In dieser Arbeit gehe ich auf meinem Anteil an diesem Projekt ein, der vor allem im Informatikbereich der BCI Forschung liegt. Im Detail beschäftige ich mich mit den folgenden drei Punkten: Diskussion eines informationstheoretischen Maßes für die Güte eines BCI's: Ich habe kritisch die Annahmen von Shannon's Informationsübertragungsrate für die Anwendung im BCI Kontext beleuchtet. Durch Ermittlung von geeigneten Kodierungsstrategien konnte ich zeigen, dass dieses theoretische Maß den praktisch erreichbaren Wert ziemlich gut annähert. Transfer und Entwicklung von geeigneten Techniken aus dem Bereich der Signalverarbeitung und des Maschinellen Lernens: Eine substantielle Komponente meiner Arbeit war die Entwicklung von Techniken des Machinellen Lernens und der Signalverarbeitung, um die Effizienz eines BCI's zu erhöhen. Basierend auf dem neurophysiologischem Wissen, dass verschiedene unabhängige Merkmale in Gehirnsignalen für verschiedene mentale Zustände beobachtbar sind, habe ich eine Methode zur Kombination von verschiedenen und unter Umständen unabhängigen Merkmalen entwickelt, die sehr erfolgreich die Fähigkeiten eines BCI's verbessert. Besonders in einigen Fällen übertraf die Leistung des entwickelten Kombinationsalgorithmus die beste Leistung auf den einzelnen Merkmalen mit mehr als 50 %. Weiterhin habe ich theoretisch und praktisch durch Einführung geeigneter Algorithmen die Frage untersucht, wie viele Klassen man für ein BCI nutzen kann und sollte. Auch hier wurde ein relevantes Resultat erzielt, nämlich dass für BCI Güten, die bis heute berichtet sind, die Benutzung von 3 oder 4 verschiedenen mentalen Zuständen in der Regel optimal im Sinne von erreichbarer Leistung sind. Für eine andere Erweiterung wurden Ideen aus der Signalverarbeitung mit denen des Maschinellen Lernens kombiniert, da ein hoher Erfolg erzielt werden kann, wenn der temporale Filter, d.h. die Wahl des benutzten Frequenzbandes, automatisch und individuell für jeden Menschen angepasst wird. Implementation des Berlin Brain-Computer Interfaces und Realisierung von geeigneten Experimenten: Eine weitere wichtige Komponente meiner Arbeit war eine Realisierung eines online BCI Systems, welches die entwickelten Methoden umfasst, aber auch so flexibel ist, dass neue Algorithmen und Ideen einfach zu verwirklichen sind. Bis jetzt wurden mit diesem System Bitraten von bis zu 40 Bits pro Minute von absolut untrainierten Personen in ihren ersten BCI Experimenten erzielt. Dieses Resultat übertrifft die bisher berichteten Ergebnisse aller anderer BCI Gruppen deutlich.
Bemerkung: Der Autor wurde mit dem Michelson-Preis 2005/2006 für die beste Promotion des Jahrgangs der Mathematisch-Naturwissenschaftlichen Fakultät der Universität Potsdam ausgezeichnet. KW - Kybernetik KW - Maschinelles Lernen KW - Gehirn-Computer-Schnittstelle KW - BCI KW - EEG KW - Spatio-Spectral Filter KW - Feedback KW - Multi-Class KW - Classification KW - Signal Processing KW - Brain Computer Interface KW - Information Transfer Rate KW - Machine Learning KW - Single Trial Analysis KW - Feature Combination KW - Common Spatial Pattern Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-7690 ER - TY - THES A1 - Scholz, Matthias T1 - Approaches to analyse and interpret biological profile data T1 - Methoden zur Analyse und Interpretation biologischer Profildaten N2 - Advances in biotechnologies rapidly increase the number of molecules of a cell which can be observed simultaneously. This includes expression levels of thousands or ten-thousands of genes as well as concentration levels of metabolites or proteins. Such Profile data, observed at different times or at different experimental conditions (e.g., heat or dry stress), show how the biological experiment is reflected on the molecular level. This information is helpful to understand the molecular behaviour and to identify molecules or combination of molecules that characterise specific biological condition (e.g., disease). This work shows the potentials of component extraction algorithms to identify the major factors which influenced the observed data. This can be the expected experimental factors such as the time or temperature as well as unexpected factors such as technical artefacts or even unknown biological behaviour. Extracting components means to reduce the very high-dimensional data to a small set of new variables termed components. Each component is a combination of all original variables. The classical approach for that purpose is the principal component analysis (PCA). It is shown that, in contrast to PCA which maximises the variance only, modern approaches such as independent component analysis (ICA) are more suitable for analysing molecular data. The condition of independence between components of ICA fits more naturally our assumption of individual (independent) factors which influence the data. This higher potential of ICA is demonstrated by a crossing experiment of the model plant Arabidopsis thaliana (Thale Cress). The experimental factors could be well identified and, in addition, ICA could even detect a technical artefact. However, in continuously observations such as in time experiments, the data show, in general, a nonlinear distribution. To analyse such nonlinear data, a nonlinear extension of PCA is used. This nonlinear PCA (NLPCA) is based on a neural network algorithm. The algorithm is adapted to be applicable to incomplete molecular data sets. Thus, it provides also the ability to estimate the missing data. The potential of nonlinear PCA to identify nonlinear factors is demonstrated by a cold stress experiment of Arabidopsis thaliana. The results of component analysis can be used to build a molecular network model. Since it includes functional dependencies it is termed functional network. Applied to the cold stress data, it is shown that functional networks are appropriate to visualise biological processes and thereby reveals molecular dynamics. N2 - Fortschritte in der Biotechnologie ermöglichen es, eine immer größere Anzahl von Molekülen in einer Zelle gleichzeitig zu erfassen. Das betrifft sowohl die Expressionswerte tausender oder zehntausender Gene als auch die Konzentrationswerte von Metaboliten oder Proteinen. Diese Profildaten verschiedener Zeitpunkte oder unterschiedlicher experimenteller Bedingungen (z.B. unter Stressbedingungen wie Hitze oder Trockenheit) zeigen, wie sich das biologische Experiment auf molekularer Ebene widerspiegelt. Diese Information kann genutzt werden, um molekulare Abläufe besser zu verstehen und um Moleküle oder Molekül-Kombinationen zu bestimmen, die für bestimmte biologische Zustände (z.B.: Krankheit) charakteristisch sind. Die Arbeit zeigt die Möglichkeiten von Komponenten-Extraktions-Algorithmen zur Bestimmung der wesentlichen Faktoren, die einen Einfluss auf die beobachteten Daten ausübten. Das können sowohl die erwarteten experimentellen Faktoren wie Zeit oder Temperatur sein als auch unerwartete Faktoren wie technische Einflüsse oder sogar unerwartete biologische Vorgänge. Unter der Extraktion von Komponenten versteht man die Reduzierung dieser stark hoch-dimensionalen Daten auf wenige neue Variablen, die eine Kombination aus allen ursprünglichen Variablen darstellen und als Komponenten bezeichnet werden. Die Standard-Methode für diesen Zweck ist die Hauptkomponentenanalyse (PCA). Es wird gezeigt, dass - im Vergleich zur nur die Varianz maximierenden PCA - moderne Methoden wie die Unabhängige Komponentenanalyse (ICA) für die Analyse molekularer Datensätze besser geeignet sind. Die Unabhängigkeit von Komponenten in der ICA entspricht viel besser unserer Annahme individueller (unabhängiger) Faktoren, die einen Einfluss auf die Daten ausüben. Dieser Vorteil der ICA wird anhand eines Kreuzungsexperiments mit der Modell-Pflanze Arabidopsis thaliana (Ackerschmalwand) demonstriert. Die experimentellen Faktoren konnten dabei gut identifiziert werden und ICA erkannte sogar zusätzlich einen technischen Störfaktor. Bei kontinuierlichen Beobachtungen wie in Zeitexperimenten zeigen die Daten jedoch häufig eine nichtlineare Verteilung. Für die Analyse dieser nichtlinearen Daten wird eine nichtlinear erweiterte Methode der PCA angewandt. Diese nichtlineare PCA (NLPCA) basiert auf einem neuronalen Netzwerk-Algorithmus. Der Algorithmus wurde für die Anwendung auf unvollständigen molekularen Daten erweitert. Dies ermöglicht es, die fehlenden Werte zu schätzen. Die Fähigkeit der nichtlinearen PCA zur Bestimmung nichtlinearer Faktoren wird anhand eines Kältestress-Experiments mit Arabidopsis thaliana demonstriert. Die Ergebnisse aus der Komponentenanalyse können zur Erstellung molekularer Netzwerk-Modelle genutzt werden. Da sie funktionelle Abhängigkeiten berücksichtigen, werden sie als Funktionale Netzwerke bezeichnet. Anhand der Kältestress-Daten wird demonstriert, dass solche funktionalen Netzwerke geeignet sind, biologische Prozesse zu visualisieren und dadurch die molekularen Dynamiken aufzuzeigen. KW - Bioinformatik KW - Hauptkomponentenanalyse KW - Unabhängige Komponentenanalyse KW - Neuronales Netz KW - Maschinelles Lernen KW - Fehlende Daten KW - Ackerschmalwand KW - nichtlineare PCA (NLPCA) KW - molekulare Netzwerke KW - nonlinear PCA (NLPCA) KW - molecular networks Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-7839 ER - TY - THES A1 - Buchholz, Henrik T1 - Real-time visualization of 3D city models T1 - Echtzeit-Visualisierung von 3D-Stadtmodellen N2 - An increasing number of applications requires user interfaces that facilitate the handling of large geodata sets. Using virtual 3D city models, complex geospatial information can be communicated visually in an intuitive way. Therefore, real-time visualization of virtual 3D city models represents a key functionality for interactive exploration, presentation, analysis, and manipulation of geospatial data. This thesis concentrates on the development and implementation of concepts and techniques for real-time city model visualization. It discusses rendering algorithms as well as complementary modeling concepts and interaction techniques. Particularly, the work introduces a new real-time rendering technique to handle city models of high complexity concerning texture size and number of textures. Such models are difficult to handle by current technology, primarily due to two problems: - Limited texture memory: The amount of simultaneously usable texture data is limited by the memory of the graphics hardware. - Limited number of textures: Using several thousand different textures simultaneously causes significant performance problems due to texture switch operations during rendering. The multiresolution texture atlases approach, introduced in this thesis, overcomes both problems. During rendering, it permanently maintains a small set of textures that are sufficient for the current view and the screen resolution available. The efficiency of multiresolution texture atlases is evaluated in performance tests. To summarize, the results demonstrate that the following goals have been achieved: - Real-time rendering becomes possible for 3D scenes whose amount of texture data exceeds the main memory capacity. - Overhead due to texture switches is kept permanently low, so that the number of different textures has no significant effect on the rendering frame rate. Furthermore, this thesis introduces two new approaches for real-time city model visualization that use textures as core visualization elements: - An approach for visualization of thematic information. - An approach for illustrative visualization of 3D city models. Both techniques demonstrate that multiresolution texture atlases provide a basic functionality for the development of new applications and systems in the domain of city model visualization. N2 - Eine zunehmende Anzahl von Anwendungen benötigt Benutzungsschnittstellen, um den Umgang mit großen Geodatenmengen zu ermöglichen. Virtuelle 3D-Stadtmodelle bieten eine Möglichkeit, komplexe raumbezogene Informationen auf intuitive Art und Weise visuell erfassbar zu machen. Echtzeit-Visualisierung virtueller Stadtmodelle bildet daher eine Grundlage für die interaktive Exploration, Präsentation, Analyse und Bearbeitung raumbezogener Daten. Diese Arbeit befasst sich mit der Entwicklung und Implementierung von Konzepten und Techniken für die Echtzeit-Visualisierung virtueller 3D-Stadtmodelle. Diese umfassen sowohl Rendering-Algorithmen als auch dazu komplementäre Modellierungskonzepte und Interaktionstechniken. Insbesondere wird in dieser Arbeit eine neue Echtzeit-Rendering-Technik für Stadtmodelle hoher Komplexität hinsichtlich Texturgröße und Texturanzahl vorgestellt. Solche Modelle sind durch die derzeit zur Verfügung stehende Technologie schwierig zu bewältigen, vor allem aus zwei Gründen: - Begrenzter Textur-Speicher: Die Menge an gleichzeitig nutzbaren Texturdaten ist beschränkt durch den Speicher der Grafik-Hardware. - Begrenzte Textur-Anzahl: Die gleichzeitige Verwendung mehrerer tausend Texturen verursacht erhebliche Performance-Probleme aufgrund von Textur-Umschaltungs-Operationen während des Renderings. Das in dieser Arbeit vorgestellte Verfahren, das Rendering mit Multiresolutions-Texturatlanten löst beide Probleme. Während der Darstellung wird dazu permanent eine kleine Textur-Menge verwaltet, die für die aktuelle Sichtperspektive und die zur Verfügung stehende Bildschirmauflösung hinreichend ist. Die Effizienz des Verfahrens wird in Performance-Tests untersucht. Die Ergebnisse zeigen, dass die folgenden Ziele erreicht werden: - Echtzeit-Darstellung wird für Modelle möglich, deren Texturdaten-Menge die Kapazität des Hauptspeichers übersteigt. - Der Overhead durch Textur-Umschaltungs-Operationen wird permanent niedrig gehalten, so dass die Anzahl der unterschiedlichen Texturen keinen wesentlichen Einfluss auf die Bildrate der Darstellung hat. Die Arbeit stellt außerdem zwei neue Ansätze zur 3D-Stadtmodell-Visualisierung vor, in denen Texturen als zentrale Visualisierungselemente eingesetzt werden: - Ein Verfahren zur Visualisierung thematischer Informationen. - Ein Verfahren zur illustrativen Visualisierung von 3D-Stadtmodellen. Beide Ansätze zeigen, dass Rendering mit Multiresolutions-Texturatlanten eine Grundlage für die Entwicklung neuer Anwendungen und Systeme im Bereich der 3D-Stadtmodell-Visualisierung bietet. KW - Computergrafik KW - Geovisualisierung KW - 3D-Stadtmodelle KW - Texturen KW - computer graphics KW - geovisualization KW - 3d city models KW - textures Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-13337 ER - TY - THES A1 - Hu, Ji T1 - A virtual machine architecture for IT-security laboratories T1 - Eine virtuelle maschinenbasierte Architektur für IT-Sicherheitslabore N2 - This thesis discusses challenges in IT security education, points out a gap between e-learning and practical education, and presents a work to fill the gap. E-learning is a flexible and personalized alternative to traditional education. Nonetheless, existing e-learning systems for IT security education have difficulties in delivering hands-on experience because of the lack of proximity. Laboratory environments and practical exercises are indispensable instruction tools to IT security education, but security education in conventional computer laboratories poses particular problems such as immobility as well as high creation and maintenance costs. Hence, there is a need to effectively transform security laboratories and practical exercises into e-learning forms. In this thesis, we introduce the Tele-Lab IT-Security architecture that allows students not only to learn IT security principles, but also to gain hands-on security experience by exercises in an online laboratory environment. In this architecture, virtual machines are used to provide safe user work environments instead of real computers. Thus, traditional laboratory environments can be cloned onto the Internet by software, which increases accessibility to laboratory resources and greatly reduces investment and maintenance costs. Under the Tele-Lab IT-Security framework, a set of technical solutions is also proposed to provide effective functionalities, reliability, security, and performance. The virtual machines with appropriate resource allocation, software installation, and system configurations are used to build lightweight security laboratories on a hosting computer. Reliability and availability of laboratory platforms are covered by a virtual machine management framework. This management framework provides necessary monitoring and administration services to detect and recover critical failures of virtual machines at run time. Considering the risk that virtual machines can be misused for compromising production networks, we present a security management solution to prevent the misuse of laboratory resources by security isolation at the system and network levels. This work is an attempt to bridge the gap between e-learning/tele-teaching and practical IT security education. It is not to substitute conventional teaching in laboratories but to add practical features to e-learning. This thesis demonstrates the possibility to implement hands-on security laboratories on the Internet reliably, securely, and economically. N2 - Diese Dissertation beschreibt die Herausforderungen in der IT Sicherheitsausbildung und weist auf die noch vorhandene Lücke zwischen E-Learning und praktischer Ausbildung hin. Sie erklärt einen Ansatz sowie ein System, um diese Lücke zwischen Theorie und Praxis in der elektronischen Ausbildung zu schließen. E-Learning ist eine flexible und personalisierte Alternative zu traditionellen Lernmethoden. Heutigen E-Learning Systemen mangelt es jedoch an der Fähigkeit, praktische Erfahrungen über große Distanzen zu ermöglichen. Labor- bzw. Testumgebungen sowie praktische Übungen sind jedoch unverzichtbar, wenn es um die Ausbildung von Sicherheitsfachkräften geht. Konventionelle Laborumgebungen besitzen allerdings einige Nachteile wie bspw. hoher Erstellungsaufwand, keine Mobilität, hohe Wartungskosten, etc. Die Herausforderung heutiger IT Sicherheitsausbildung ist es daher, praktische Sicherheitslaborumgebungen und Übungen effektiv mittels E-Learning zu unterstützen. In dieser Dissertation wird die Architektur von Tele-Lab IT-Security vorgestellt, die Studenten nicht nur erlaubt theoretische Sicherheitskonzepte zu erlernen, sondern darüber hinaus Sicherheitsübungen in einer Online-Laborumgebung praktisch zu absolvieren. Die Teilnehmer können auf diese Weise wichtige praktische Erfahrungen im Umgang mit Sicherheitsprogrammen sammeln. Zur Realisierung einer sicheren Übungsumgebung, werden virtuelle Maschinen anstatt reale Rechner im Tele-Lab System verwendet. Mittels virtueller Maschinen können leicht Laborumgebungen geklont, verwaltet und über das Internet zugänglich gemacht werden. Im Vergleich zu herkömmlichen Offline-Laboren können somit erhebliche Investitions- und Wartungskosten gespart werden. Das Tele-Lab System bietet eine Reihe von technischen Funktionen, die den effektiven, zuverlässigen und sicheren Betrieb dieses Trainingssystems gewährleistet. Unter Beachtung angemessener Ressourcennutzung, Softwareinstallationen und Systemkonfigurationen wurden virtuelle Maschinen als Übungsstationen erstellt, die auf einem einzelnen Rechner betrieben werden. Für ihre Zuverlässigkeit und Verfügbarkeit ist das Managementsystem der virtuellen Maschinen verantwortlich. Diese Komponente besitzt die notwendigen Überwachungs- und Verwaltungsfunktionen, um kritische Fehler der virtuellen Maschinen während der Laufzeit zu erkennen und zu beheben. Damit die Übungsstationen nicht bspw. zur Kompromittierung von Produktivnetzwerken genutzt werden, beschreibt die Dissertation Sicherheits-Managementlösungen, die mittels Isolation auf System und Netzwerk Ebene genau dieses Risiko verhindern sollen. Diese Arbeit ist der Versuch, die Lücke zwischen E-Learning/Tele-Teaching und praktischer Sicherheitsausbildung zu schließen. Sie verfolgt nicht das Ziel, konventionelle Ausbildung in Offline Laboren zu ersetzen, sondern auch praktische Erfahrungen via E-Learning zu unterstützen. Die Dissertation zeigt die Möglichkeit, praktische Erfahrungen mittels Sicherheitsübungsumgebungen über das Internet auf zuverlässige, sichere und wirtschaftliche Weise zu vermitteln. KW - Computersicherheit KW - VM KW - E-Learning KW - IT security KW - virtual machine KW - E-Learning Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-7818 ER -