Vorwort und Inhaltsverzeichnis

Ausgezeichnete
Informatikdissertationen
2006
Im Auftrag der GI herausgegeben durch
die beteiligten Mitglieder des Nominierungsausschusses
Abraham Bernstein, Universität Zürich
Thomas Dreier, Universität Karlsruhe (TH)
Steffen Hölldobler, Technische Universität Dresden
Günter Hotz, Universität des Saarlandes
Klaus-Peter Löhr, Freie Universität Berlin
Paul Molitor, Martin-Luther-Universität Halle-Wittenberg
Rüdiger Reischuk, Universität zu Lübeck
Dietmar Saupe, Universität Konstanz
Myra Spiliopoulou, Otto-von-Guericke-Universität Magdeburg
Dorothea Wagner (Vorsitzende), Universität Karlsruhe (TH)
Gesellschaft für Informatik 2007
Lecture Notes in Informatics (LNI) - Dissertations
Series of the Gesellschaft für Informatik e.V. (GI)
Volume D-7
ISBN 978-3-88579-411-0
Dissertations Editorial Board
Prof. Dr. Dorothea Wagner (Chair),
Universität Karlsruhe (TH)
Institut für Theoretische Informatik
76128 Karlsruhe
Abraham Bernstein, Universität Zürich
Thomas Dreier, Universität Karlsruhe (TH)
Steffen Hölldobler, Technische Universität Dresden
Günter Hotz, Universität des Saarlandes
Klaus-Peter Löhr, Freie Universität Berlin
Paul Molitor, Martin-Luther-Universität Halle-Wittenberg
Gustaf Neumann, Wirtschaftsuniversität Wien
Rüdiger Reischuk, Universität zu Lübeck
Dietmar Saupe, Universität Konstanz
Myra Spiliopoulou, Otto-von-Guericke-Universität Magdeburg
Dorothea Wagner (Vorsitzende), Universität Karlsruhe (TH)
Series Editorial Board
Heinrich C. Mayr, Universität Klagenfurt, Austria (Chairman, [email protected])
Jörg Becker, Universität Münster, Germany
Ulrich Furbach, Universität Koblenz, Germany
Axel Lehmann, Universität der Bundeswehr München, Germany
Peter Liggesmeyer, TU Kaiserslautern und Fraunhofer IESE, Germany
Ernst W. Mayr, Technische Universität München, Germany
Heinrich Müller, Universität Dortmund, Germany
Heinrich Reinermann, Hochschule für Verwaltungswissenschaften Speyer, Germany
Karl-Heinz Rödiger, Universität Bremen, Germany
Sigrid Schubert, Universität Siegen, Germany
Seminars
Reinhard Wilhelm, Universität des Saarlandes, Germany
Gesellschaft für Informatik, Bonn 2007
printed by Köllen Druck+Verlag GmbH, Bonn
3
Vorwort
Die Gesellschaft für Informatik e.V. (GI) vergibt gemeinsam mit der Schweizer Informatik Gesellschaft (SI), der Österreichischen Computergesellschaft (OCG) und dem German
Chapter of the ACM (GChACM) jährlich einen Preis für eine hervorragende Dissertation im Bereich der Informatik. Hierzu zählen nicht nur Arbeiten, die einen Fortschritt
für die Informatik bedeuten, sondern auch Arbeiten aus dem Bereich der Anwendungen
in anderen Disziplinen und Arbeiten, die die Wechselwirkungen zwischen Informatik und
Gesellschaft untersuchen. Die Auswahl dieser Dissertation stützt sich auf die von den Universitäten und Hochschulen für diesen Preis vorgeschlagenen Dissertationen. Jede dieser
Hochschulen kann jedes Jahr nur eine Dissertation vorschlagen. Somit sind die zum Auswahlverfahren der GI vorgeschlagenen Kandidatinnen und Kandidaten bereits „Preisträger“ ihrer Hochschule.
Für den Dissertationspreis 2006 wurden 22 Dissertationen vorgeschlagen, welche vom Nominierungsausschuss sorgfältig begutachtet und diskutiert wurden. Im Rahmen eines Kolloquiums im Internationalen Begegnungs- und Forschungszentrum für Informatik Schloss
Dagstuhl wurden die vorgeschlagenen Arbeiten von den Nominierten vorgestellt. Erfreulicherweise konnten fast alle Kandidaten trotz zum Teil weiter Anreise teilnehmen. Wie
jedes Jahr war für die Mitglieder des Nominierungsausschuss das persönliche Zusammentreffen mit den Nominierten das „Highlight“ der Auswahlarbeit. Das wissenschaftlich hohe Niveau der Vorträge, die regen Diskussionen und die angenehme Atmosphäre
in Schloss Dagstuhl wurde von allen Teilnehmerinnen und Teilnehmern des Kolloquiums
sehr begrüßt.
Wie jedes Jahr fiel es dem Nominierungsausschuss sehr schwer, eine einzige Dissertation
auszuwählen, die durch den Preis besonders gewürdigt wird. Mit der Präsentation aller vorgeschlagenen Dissertationen in diesem Band wird die Ungerechtigkeit, eine aus mehreren
ebenbürtigen Dissertationen hervorzuheben, etwas ausgeglichen. Dieser Band soll zudem
einen Beitrag zum Wissenstransfer innerhalb der Informatik und von den Universitäten in
die Bereiche Technik, Wirtschaft und Gesellschaft leisten.
Die beteiligten Gesellschaften zeichnen Herrn Dr.-Ing. Andrés Bruhn, der an der Universität des Saarlandes promovierte, für seine hervorragende Dissertation „Variationelle
Optische Flussberechnung - Präzise Modellierung und effiziente Numerik“ mit dem Dissertationspreis 2006 aus.
Das Maschinensehen beinhaltet die computergestützte Verarbeitung und Interpretation visueller Inhalte, ein Gebiet der Informatik, das angesichts der allgegenwärtigen Verfügbarkeit von Bildern und Videos an Bedeutung gewinnt. Eines der zentralen Probleme des
Maschinensehens ist die Schätzung von Bewegungsinformation aus digitalen Bildfolgen,
wozu eine möglichst vollständige und genaue Bestimmung des Verschiebungsvektorfeldes zwischen aufeinander folgenden Bildern - auch optischer Fluss genannt - benötigt
wird. Die Kenntnis des optischen Flussfeldes ist von großem Interesse für eine Reihe von
Anwendungen, angefangen bei der visuell basierten Roboternavigation über Fahrerassistenzsysteme bis hin zu Videokompressionsverfahren.
4
Bisherige Ansätze zur Berechnung des optischen Flusses waren entweder für Echtzeitanwendungen zu langsam oder führten zu Flussfeldschätzungen von unbefriedigender Qualität. Mit seiner Dissertation hat Andrés Bruhn das Ziel verfolgt, Qualität und Effizienz der
optischen Flussberechnung gleichzeitig zu garantieren. Auf Basis eines flexiblen, allgemeinen Rahmens für Variationsansätze zur Berechnung des optischen Flusses gelingt ihm
der Entwurf der zur Zeit präzisesten Verfahren. Mit sehr ausgefeilten, hochperformanten
Mehrgitteralgorithmen wird zudem die Berechnung in Echtzeit ermöglicht.
Herr Bruhn liefert mit seiner Dissertation bedeutende Beiträge zur Bewegungsanalyse in
Bildfolgen. Seine Verfahren ermöglichen erstmals eine gleichzeitig präzise und praktikable Schätzung von Bewegungsinformation.
Mit dieser Preisverleihung würdigen die beteiligten Gesellschaften - die Gesellschaft für
Informatik e.V. (GI), die Schweizer Informatik Gesellschaft (SI), die Österreichische Computergesellschaft (OCG) und das German Chapter of the ACM (GChACM) - eine herausragende wissenschaftliche Arbeit, die bedeutende Ergebnisse im Maschinensehen liefert,
große Anwendungsrelevanz hat, und von höchstem Interesse für die Informatik ist.
Ein besonderer Dank gilt dem Nominierungsausschuss, der sehr effizient und konstruktiv
zusammengearbeitet hat. Bei Frau Lilian Beckert möchte ich mich für die Unterstützung
bei der Entgegennahme der vorgeschlagenen Dissertationen und bei Herrn Robert Görke für die Zusammenstellung und Anpassung der Beiträge an das Format der GI-Edition
Lecture Notes in Informatics (LNI) bedanken. Für die finanzielle Unterstützung des Nominationskolloquiums sei den beteiligten Gesellschaften gedankt. Die Gastfreundschaft und
die hervorragende Bewirtung in Dagstuhl trugen zum Erfolg des Kolloquiums bei, wofür
ich mich an dieser Stelle ebenfalls herzlich bedanke.
Dorothea Wagner, Karlsruhe im August 2007
5
Kandidaten für den
GI-Dissertationspreis 2006
Dr. Andrés Bruhn
Dr.-Ing. Erik Buchmann
Dr. Görschwin Fey
Dr. Kilian Foth
Dr. Gereon Frahling
Dr. Tobias Frank
Dr. Stefan Frenz
Dr. Arnulph Fuhrmann
Dr. Torsten Gipp
Dr. Jiong Guo
Dr. Klaus Herrmann
Dr. Daniel Keysers
Dr. Stefan Kral
Dr. Jens Krüger
Dr. Sven Overhage
Dr. Daniel Reidenbach
Dr. Andreas Schäfer
Dr. Frank-Michael Schleif
Dr. Dominique Unruh
Dr. Manish Verma
Dr.-Ing. Christian Werner
Dr. Simon Winkelbach
Universität des Saarlandes
Universität Karlsruhe (TH)
Universität Bremen
Universität Hamburg
Universität Paderborn
TU Bergakademie Freiberg
Universität Ulm
TU Darmstadt
Universität Koblenz-Landau
Friedrich-Schiller-Universität Jena
TU Berlin
RWTH Aachen
TU Wien
TU München
Universität Augsburg
TU Kaiserslautern
Carl von Ossietzky-Universität Oldenburg
TU Clausthal
Universität Karlsruhe
Universität Dortmund
Universität Lübeck
TU Braunschweig
6
Beteiligte Mitglieder des Nominierungsausschusses
für den GI-Dissertationspreis 2006
Prof. Dr. Abraham Bernstein
Prof. Dr. Thomas Dreier
Prof. Dr. Steffen Hölldobler
Prof. Dr. Dr. h.c. mult. Günter Hotz
Prof. Dr.-Ing. Klaus-Peter Löhr
Prof. Dr. Paul Molitor
Prof. Dr. Rüdiger Reischuk
Prof. Dr. Dietmar Saupe
Prof. Dr. Myra Spiliopoulou
Prof. Dr. Dorothea Wagner (Vorsitzende)
Universität Zürich
Universität Karlsruhe
TU Dresden
Universität des Saarlandes
Freie Universität Berlin
Martin-Luther-Universität Halle-Wittenberg
Universität zu Lübeck
Universität Konstanz
Otto-von-Guericke-Universität Magdeburg
Universität Karlsruhe (TH)
7
Inhaltsverzeichnis
Andrés Bruhn
Variationsansätze zur Bewegungsschätzung: Präzise Modellierung und Effiziente Numerik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Erik Buchmann
Erkennung und Vermeidung von Unkooperativem Verhalten in Peer-to-PeerDatenstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Görschwin Fey
Increasing Robustness and Usability of Circuit Design Tools by Using Formal
Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Kilian Foth
Hybrid Methods of Natural Language Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Gereon Frahling
Algorithms for Dynamic Geometric Data Streams . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Tobias Frank
Advanced Visualization and Modeling of Tetrahedral Meshes . . . . . . . . . . . . . . . 59
Stefan Frenz
Zuverlässiger Verteilter Speicher mit Transaktionaler Konsistenz . . . . . . . . . . . 69
Arnulph Fuhrmann
Interaktive Animation Textiler Materialien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Torsten Gipp
Functional Web Site Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Jiong Guo
Algorithm Design Techniques for Parameterized Graph Modification Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Klaus Herrmann
Self-Organizing Infrastructures for Ambient Services . . . . . . . . . . . . . . . . . . . . . . 109
Daniel Keysers
Modeling of Image Variability for Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8
Stefan Kral
FFT Specific Compilation on IBM Blue Gene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Jens Krüger
A GPU Framework for Interactive Simulation and Rendering of Fluid Effects139
Sven Overhage
Vereinheitlichte Spezifikation von Komponenten: Grundlagen, UnSCom Spezifikationsrahmen und Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Daniel Reidenbach
The Ambiguity of Morphisms in Free Monoids and its Impact on Algorithmic
Properties of Pattern Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Andreas Schäfer
Specification and Verification of Mobile Real-Time Systems . . . . . . . . . . . . . . . . . 169
Frank-Michael Schleif
Prototype based Machine Learning for Clinical Proteomics . . . . . . . . . . . . . . . . . 179
Dominique Unruh
Protokollkomposition und Komplexität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
Manish Verma
Advanced Memory Optimization Techniques for Low-Power Embedded Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Christian Werner
Optimierte Protokolle für Web Services mit Begrenzten Datenraten . . . . . . . . . 209
Simon Winkelbach
Das 3d-Puzzle-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219