@phdthesis{Ghasemzadeh2005,
  author    = {Ghasemzadeh, Mohammad},
  title     = {A new algorithm for the quantified satisfiability problem, based on zero-suppressed binary decision diagrams and memoization},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-6378},
  school      = {Universit{\"a}t Potsdam},
  year      = {2005},
  abstract  = {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.},
  subject      = {Bin{\"a}res Entscheidungsdiagramm},
  language  = {en}
}
@phdthesis{Floeter2005,
  author    = {Fl{\"o}ter, Andr{\´e}},
  title     = {Analyzing biological expression data based on decision tree induction},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-6416},
  school      = {Universit{\"a}t Potsdam},
  year      = {2005},
  abstract  = {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.},
  subject      = {Molekulare Bioinformatik},
  language  = {en}
}
@phdthesis{Ziehe2005,
  author    = {Ziehe, Andreas},
  title     = {Blind source separation based on joint diagonalization of matrices with applications in biomedical signal processing},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-5694},
  school      = {Universit{\"a}t Potsdam},
  year      = {2005},
  abstract  = {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.},
  subject      = {Signaltrennung},
  language  = {en}
}
@phdthesis{Kirsch2005,
  author    = {Kirsch, Florian},
  title     = {Entwurf und Implementierung eines computergraphischen Systems zur Integration komplexer, echtzeitf{\"a}higer 3D-Renderingverfahren},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-6079},
  school      = {Universit{\"a}t Potsdam},
  year      = {2005},
  abstract  = {Thema dieser Arbeit sind echtzeitf{\"a}hige 3D-Renderingverfahren, die 3D-Geometrie mit {\"u}ber der Standarddarstellung hinausgehenden Qualit{\"a}ts- und Gestaltungsmerkmalen rendern k{\"o}nnen. Beispiele sind Verfahren zur Darstellung von Schatten, Reflexionen oder Transparenz. Mit heutigen computergraphischen Software-Basissystemen ist ihre Integration in 3D-Anwendungssysteme sehr aufw{\"a}ndig: Dies liegt einerseits an der technischen, algorithmischen Komplexit{\"a}t der Einzelverfahren, andererseits an Ressourcenkonflikten und Seiteneffekten bei der Kombination mehrerer Verfahren. Szenengraphsysteme, intendiert als computergraphische Softwareschicht zur Abstraktion von der Graphikhardware, stellen derzeit keine Mechanismen zur Nutzung dieser Renderingverfahren zur Verf{\"u}gung. Ziel dieser Arbeit ist es, eine Software-Architektur f{\"u}r ein Szenengraphsystem zu konzipieren und umzusetzen, die echtzeitf{\"a}hige 3D-Renderingverfahren als Komponenten modelliert und es damit erlaubt, diese Verfahren innerhalb des Szenengraphsystems f{\"u}r die Anwendungsentwicklung effektiv zu nutzen. Ein Entwickler, der ein solches Szenengraphsystem nutzt, steuert diese Komponenten durch Elemente in der Szenenbeschreibung an, die die sichtbare Wirkung eines Renderingverfahrens auf die Geometrie in der Szene angeben, aber keine Hinweise auf die algorithmische Implementierung des Verfahrens enthalten. Damit werden Renderingverfahren in 3D-Anwendungssystemen nutzbar, ohne dass ein Entwickler detaillierte Kenntnisse {\"u}ber sie ben{\"o}tigt, so dass der Aufwand f{\"u}r ihre Entwicklung drastisch reduziert wird. Ein besonderer Augenmerk der Arbeit liegt darauf, auf diese Weise auch verschiedene Renderingverfahren in einer Szene kombiniert einsetzen zu k{\"o}nnen. Hierzu ist eine Unterteilung der Renderingverfahren in mehrere Kategorien erforderlich, die mit Hilfe unterschiedlicher Ans{\"a}tze ausgewertet werden. Dies erlaubt die Abstimmung verschiedener Komponenten f{\"u}r Renderingverfahren und ihrer verwendeten Ressourcen. Die Zusammenarbeit mehrerer Renderingverfahren hat dort ihre Grenzen, wo die Kombination von Renderingverfahren graphisch nicht sinnvoll ist oder fundamentale technische Beschr{\"a}nkungen der Verfahren eine gleichzeitige Verwendung unm{\"o}glich machen. Die in dieser Arbeit vorgestellte Software-Architektur kann diese Grenzen nicht verschieben, aber sie erm{\"o}glicht den gleichzeitigen Einsatz vieler Verfahren, bei denen eine Kombination aufgrund der hohen Komplexit{\"a}t der Implementierung bislang nicht erreicht wurde. Das Verm{\"o}gen zur Zusammenarbeit ist dabei allerdings von der Art eines Einzelverfahrens abh{\"a}ngig: Verfahren zur Darstellung transparenter Geometrie beispielsweise erfordern bei der Kombination mit anderen Verfahren in der Regel vollst{\"a}ndig neuentwickelte Renderingverfahren; entsprechende Komponenten f{\"u}r das Szenengraphsystem k{\"o}nnen daher nur eingeschr{\"a}nkt mit Komponenten f{\"u}r andere Renderingverfahren verwendet werden. Das in dieser Arbeit entwickelte System integriert und kombiniert Verfahren zur Darstellung von Bumpmapping, verschiedene Schatten- und Reflexionsverfahren sowie bildbasiertes CSG-Rendering. Damit stehen wesentliche Renderingverfahren in einem Szenengraphsystem erstmalig komponentenbasiert und auf einem hohen Abstraktionsniveau zur Verf{\"u}gung. Das System ist trotz des zus{\"a}tzlichen Verwaltungsaufwandes in der Lage, die Renderingverfahren einzeln und in Kombination grunds{\"a}tzlich in Echtzeit auszuf{\"u}hren.},
  subject      = {Dreidimensionale Computergraphik},
  language  = {de}
}
@phdthesis{RobinsonMallett2005,
  author    = {Robinson-Mallett, Christopher},
  title     = {Modellbasierte Modulpr{\"u}fung f{\"u}r die Entwicklung technischer, softwareintensiver Systeme mit Real-Time Object-Oriented Modeling},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-6045},
  school      = {Universit{\"a}t Potsdam},
  year      = {2005},
  abstract  = {Mit zunehmender Komplexit{\"a}t technischer Softwaresysteme ist die Nachfrage an produktiveren Methoden und Werkzeugen auch im sicherheitskritischen Umfeld gewachsen. Da insbesondere objektorientierte und modellbasierte Ans{\"a}tze und Methoden ausgezeichnete Eigenschaften zur Entwicklung großer und komplexer Systeme besitzen, ist zu erwarten, dass diese in naher Zukunft selbst bis in sicherheitskritische Bereiche der Softwareentwicklung vordringen. Mit der Unified Modeling Language Real-Time (UML-RT) wird eine Softwareentwicklungsmethode f{\"u}r technische Systeme durch die Object Management Group (OMG) propagiert. F{\"u}r den praktischen Einsatz im technischen und sicherheitskritischen Umfeld muss diese Methode nicht nur bestimmte technische Eigenschaften, beispielsweise temporale Analysierbarkeit, besitzen, sondern auch in einen bestehenden Qualit{\"a}tssicherungsprozess integrierbar sein. Ein wichtiger Aspekt der Integration der UML-RT in ein qualit{\"a}tsorientiertes Prozessmodell, beispielsweise in das V-Modell, ist die Verf{\"u}gbarkeit von ausgereiften Konzepten und Methoden f{\"u}r einen systematischen Modultest. Der Modultest dient als erste Qualitit{\"a}tssicherungsphase nach der Implementierung der Fehlerfindung und dem Qualit{\"a}tsnachweis f{\"u}r jede separat pr{\"u}fbare Softwarekomponente eines Systems. W{\"a}hrend dieser Phase stellt die Durchf{\"u}hrung von systematischen Tests die wichtigste Qualit{\"a}tssicherungsmaßnahme dar. W{\"a}hrend zum jetzigen Zeitpunkt zwar ausgereifte Methoden und Werkzeuge f{\"u}r die modellbasierte Softwareentwicklung zur Verf{\"u}gung stehen, existieren nur wenig {\"u}berzeugende L{\"o}sungen f{\"u}r eine systematische modellbasierte Modulpr{\"u}fung. Die durchg{\"a}ngige Verwendung ausf{\"u}hrbarer Modelle und Codegenerierung stellen wesentliche Konzepte der modellbasierten Softwareentwicklung dar. Sie dienen der konstruktiven Fehlerreduktion durch Automatisierung ansonsten fehlertr{\"a}chtiger, manueller Vorg{\"a}nge. Im Rahmen einer modellbasierten Qualit{\"a}tssicherung sollten diese Konzepte konsequenterweise in die sp{\"a}teren Qualit{\"a}tssicherungsphasen transportiert werden. Daher ist eine wesentliche Forderung an ein Verfahren zur modellbasierten Modulpr{\"u}fung ein m{\"o}glichst hoher Grad an Automatisierung. In aktuellen Entwicklungen hat sich f{\"u}r die Generierung von Testf{\"a}llen auf Basis von Zustandsautomaten die Verwendung von Model Checking als effiziente und an die vielf{\"a}ltigsten Testprobleme anpassbare Methode bew{\"a}hrt. Der Ansatz des Model Checking stammt urspr{\"u}nglich aus dem Entwurf von Kommunikationsprotokollen und wurde bereits erfolgreich auf verschiedene Probleme der Modellierung technischer Software angewendet. Insbesondere in der Gegenwart ausf{\"u}hrbarer, automatenbasierter Modelle erscheint die Verwendung von Model Checking sinnvoll, das die Existenz einer formalen, zustandsbasierten Spezifikation voraussetzt. Ein ausf{\"u}hrbares, zustandsbasiertes Modell erf{\"u}llt diese Anforderungen in der Regel. Aus diesen Gr{\"u}nden ist die Wahl eines Model Checking Ansatzes f{\"u}r die Generierung von Testf{\"a}llen im Rahmen eines modellbasierten Modultestverfahrens eine logische Konsequenz. Obwohl in der aktuellen Spezifikation der UML-RT keine eindeutigen Aussagen {\"u}ber den zur Verhaltensbeschreibung zu verwendenden Formalismus gemacht werden, ist es wahrscheinlich, dass es sich bei der UML-RT um eine zu Real-Time Object-Oriented Modeling (ROOM) kompatible Methode handelt. Alle in dieser Arbeit pr{\"a}sentierten Methoden und Ergebnisse sind somit auf die kommende UML-RT {\"u}bertragbar und von sehr aktueller Bedeutung. Aus den genannten Gr{\"u}nden verfolgt diese Arbeit das Ziel, die analytische Qualit{\"a}tssicherung in der modellbasierten Softwareentwicklung mittels einer modellbasierten Methode f{\"u}r den Modultest zu verbessern. Zu diesem Zweck wird eine neuartige Testmethode pr{\"a}sentiert, die auf automatenbasierten Verhaltensmodellen und CTL Model Checking basiert. Die Testfallgenerierung kann weitgehend automatisch erfolgen, um Fehler durch menschlichen Einfluss auszuschließen. Das entwickelte Modultestverfahren ist in die technischen Konzepte Model Driven Architecture und ROOM, beziehungsweise UML-RT, sowie in die organisatorischen Konzepte eines qualit{\"a}tsorientierten Prozessmodells, beispielsweise das V-Modell, integrierbar.},
  subject      = {Software},
  language  = {de}
}
@phdthesis{Morozov2005,
  author    = {Morozov, Alexei},
  title     = {Optimierung von Fehlererkennungsschaltungen auf der Grundlage von komplement{\"a}ren Erg{\"a}nzungen f{\"u}r 1-aus-3 und Berger Codes},
  url       = {http://nbn-resolving.de/urn:nbn:de:kobv:517-opus-5360},
  school      = {Universit{\"a}t Potsdam},
  year      = {2005},
  abstract  = {Die Dissertation stellt eine neue Herangehensweise an die L{\"o}sung der Aufgabe der funktionalen Diagnostik digitaler Systeme vor. In dieser Arbeit wird eine neue Methode f{\"u}r die Fehlererkennung vorgeschlagen, basierend auf der Logischen Erg{\"a}nzung und der Verwendung von Berger-Codes und dem 1-aus-3 Code. Die neue Fehlererkennungsmethode der Logischen Erg{\"a}nzung gestattet einen hohen Optimierungsgrad der ben{\"o}tigten Realisationsfl{\"a}che der konstruierten Fehlererkennungsschaltungen. Außerdem ist eins der wichtigen in dieser Dissertation gel{\"o}sten Probleme die Synthese vollst{\"a}ndig selbstpr{\"u}fender Schaltungen.},
  subject      = {logische Erg{\"a}nzung},
  language  = {de}
}