D15 (2014) - Ausgezeichnete Informatikdissertationen
Steffen Hölldobler et al. (Hrsg.)
Ausgezeichnete Informatikdissertationen 2014
Autor*innen mit den meisten Dokumenten
Auflistung nach:
Neueste Veröffentlichungen
- TextdokumentGenerierung diskreter Zufallsvariablen und Berechnung der Fréchetdistanz(Ausgezeichnete Informatikdissertationen 2014, 2015) Bringmann, KarlIm ersten Teil dieser Dissertation untersuchen wir das fundamentale Problem der Generierung von Zufallsvariablen mit einer gegebenen diskreten Wahrscheinlichkeitsverteilung. Wir erweitern die klassische Lösung dieses Problems, Walkers Aliasmethode, in verschiedene Richtungen: Wir verbessern ihren Speicherbedarf, lösen den Spezialfall von sortierter Eingabe und untersuchen das Ziehen von natürlichen Verteilungen auf Maschinen mit beschränkter Präzision. Als Anwendung beschleunigen wir die Simulation eines physikalischen Modells. Der zweite Teil dieser Dissertation gehört zum Gebiet der Geometrie und handelt von Algorithmen für die Fréchetdistanz, einem beliebten Ähnlichkeitsmaß für Kurven, das in quadratischer Zeit berechnet werden kann (bis auf logarithmische Faktoren). Wir zeigen die erste bedingte untere Schranke für dieses Problem: Unter der starken Exponentialzeithypothese ist keine Verbesserung der quadratischen Laufzeit um einen polynomiellen Faktor möglich. Zusätzlich präsentieren wir einen verbesserten Approximationsalgorithmus für realistische Eingabekurven.
- TextdokumentTonhöheninformierten Trennung in Solo- und Begleitspuren(Ausgezeichnete Informatikdissertationen 2014, 2015) Cano, EstefaníaDiese Veröffentlichung im Forschungsgebiet der Klangquellentrennung befasst sich speziell mit der Separierung von einzelnen Musikinstrumenten aus bereits gemischten Audio-Signalen. Eine Methode zur tonhöheninformierten Trennung in Solo- und Begleitspuren wird detailliert beschrieben. Die praktische Anwendbarkeit der vorgestellten Methode wird anhand der Integration in die Musiklernsoftware Songs2See erläutert. Des Weiteren werden die Ergebnisse eine Studie im Hinblick auf Anwendbarkeit für die harmonisch/perkussive Klangquellentrennung präsentiert, welche die Klänge verschiedener musikalischer Instrumente untersucht.
- TextdokumentPlanare Graphen und ihre Dualgraphen auf Zylinderoberflächen(Ausgezeichnete Informatikdissertationen 2014, 2015) Auer, ChristopherDie Arbeit beschäftigt sich mit planaren Zeichnungen ungerichteter und gerichteter Graphen auf Zylinderoberflächen. Im ungerichteten Fall werden die Knoten auf einer Linie parallel zur Zylinderachse positioniert, während die Kanten diese Linie nicht schneiden. Es wird gezeigt, dass eine planare Zeichnung genau dann möglich ist, wenn die Kanten des Graphen in einer double-ended queue (Deque) verarbeitet werden können. Als Konsequenz ergibt sich, dass die Deque genau die planaren Graphen mit Hamiltonpfad charakterisiert. Dies erweitert die bereits bekannte Charakterisierung planarer Graphen mit Hamiltonkreis durch den Doppelstack. Im gerichteten Fall verlaufen die Kantenkurven entweder in Richtung der Zylinderachse (SUP) oder um die Achse herum (RUP). Die Arbeit charakterisiert RUP-Graphen und zeigt, dass RUP und SUP ihre Rollen tauschen, wenn man Graph und Dualgraph betrachtet. Mit Hilfe dieser Charakterisierung wird ein Erkennungs-Algorithmus für RUP-Graphen entwickelt.
- TextdokumentMessbarkeit und Beeinflussung von Eventual-Consistency in verteilten Datenspeichersystemen(Ausgezeichnete Informatikdissertationen 2014, 2015) Bermbach, DavidCloudspeicherdienste und NoSQL-Systeme, die sich zunehmend größerer Beliebtheit erfreuen, bieten meist weder transaktionale Features noch strikte Konsistenzgarantien. Stattdessen wird mit Eventual-Consistency lediglich garantiert, dass alle Schreiboperationen irgendwann – jedoch zu einem undefinierten Zeitpunkt – auf allen Replika ausgeführt werden. Die Unsicherheit, wann dies passiert, stellt dabei Anwendungsentwickler, die ein solches System nutzen moöchten, vor große Schwierigkeiten, da es jederzeit möglich ist, dass veraltete Daten gelesen werden oder parallele Updates zu weitergehenden Problemen führen. Mit dieser Arbeit wird erstmals ermöglicht, durch Experimente und Simulationen Wissen über den Grad der Inkonsistenz zu gewinnen und mit ebenfalls vorgestellten Verfahren auf Basis dieses Wissens Inkonsistenzen in der Anwendungsschicht aufzulösen oder sogar durch eine Middlewareschicht zusätzliche Konsistenzgarantien zu geben.
- TextdokumentUntere Schranken für heuristische Algorithmen(Ausgezeichnete Informatikdissertationen 2014, 2015) Berkholz, ChristophDieser Beitrag ist eine deutschsprachige Zusammenfassung der Dissertation des Autors. In der Dissertation werden drei verwandte heuristische Verfahren zum Lösen schwerer Probleme untersucht: der k-Konsistenztest für das Constraint-Satisfaction-Problem, Resolution beschränkter Weite für 3-SAT und der Knotenpartitionierungsalgorithmus für das Graphisomorphieproblem. Die Hauptergebnisse der Dissertation sind untere Schranken an die Zeitkomplexität der Verfahren. In diesem Beitrag werden die untersuchten Verfahren eingeführt und die erzielten unteren Schranken vorgestellt.
- TextdokumentObjektorientierte Software für Industrieroboter(Ausgezeichnete Informatikdissertationen 2014, 2015) Angerer, AndreasIndustrieroboter werden heutzutage in vielen Bereichen der Fertigungsindustrie eingesetzt und entlasten dort Menschen von schweren und sich wiederholenden Tätigkeiten. Ihr breiterer Einsatz wird jedoch immer mehr durch veraltete herstellerspezifische Programmiersprachen und proprietäre Software-Ökosysteme limitiert. In dieser Arbeit wird ein objektorientiertes Software-Design vorgestellt, mit dem sich Anwendungen für Industrieroboter mit Standard-Programmiersprachen entwickeln lassen. Dabei ist es erstmals gelungen, moderne Programmiersprachen mit den für die Industrierobotik nötigen Echtzeitanforderungen zu verbinden und gleichzeitig die Flexibilität der Programmierschnittstelle zu erhöhen. Die entwickelten Softwarekonzepte wurden in einer Referenzimplementierung umgesetzt und anhand mehrerer anspruchsvoller Applikationen evaluiert. Bereits heute werden die Ergebnisse dieser Arbeit in der KUKA Sunrise Steuerung für den seit Kurzem erhältlichen Roboter LBR iiwa eingesetzt.
- TextdokumentVerständnis von zellulärern Zuständen und Zellzustandsübergängen durch integrative Analyse epigenetischer Veränderungen(Ausgezeichnete Informatikdissertationen 2014, 2015) Ziller, Michael J.Wie kommt es, dass ein und dasselbe Genom eine derartige Vielzahl unterschiedlicher Zelltypen erzeugen kann? Die Antwort auf diese Frage liegt in der epigenetischen Regulation des Genoms. Im Rahmen dieser Dissertation wurden statistische Verfahren und neue Analyseansätze zur Auswertung von genomweiten Messungen des epigenetischen Zustands in verschiedenen Zellpopulationen entwickelt. Diese Verfahren gestatten es, die der Zellidentitätsbildung zugrunde liegenden molekularen Mechanismen besser zu verstehen und Teile der zugehörigen regulatorischen Netzwerke zu dekodieren. Auf diese Weise konnten diverse neue biologische Einsichten gewonnen und validiert werden. Darüber hinaus sind die vorgestellten Methoden in weiten Teilen der Epigenomik anwendbar und zeigen neue Konzepte zur Analyse von hochdimensionalen genomischen Daten auf [Zi14].
- TextdokumentIntrinsische Plagiatserkennung und Autorenerkennung mittels Grammatikanalyse(Ausgezeichnete Informatikdissertationen 2014, 2015) Tschuggnall, MichaelDurch die hohe und ständig steigende Anzahl an frei verfügbaren Textdokumenten wird es immer leichter, Quellen für mögliche Plagiate zu finden, während es auf der anderen Seite für automatische Erkennungstools aufgrund der großen Datenmengen immer schwieriger wird, diese zu erkennen. In dieser Arbeit wurden verschiedene Algorithmen zur intrinsischen Plagiatserkennung entwickelt, welche ausschließlich das zu prüfende Dokument untersuchen und so das Problem umgehen, externe Daten heranziehen zu müssen. Dabei besteht die Grundidee darin, den Schreibstil von Autoren auf Basis der von ihnen verwendeten Grammatik zur Formulierung von Sätzen zu untersuchen, und diese Information zu nutzen, um syntaktisch auffällige Textfragmente zu identifizieren. Unter Verwendung einer ähnlichen Analyse wird diese Idee auch auf das Problem, Textdokumente automatisch Autoren zuzuordnen, angewendet. Darüber hinaus wird gezeigt, dass die verwendete Grammatik auch ein unterscheidbares Kriterium darstellt, um Informationen wie das Geschlecht und das Alter des Verfassers abzuschätzen. Schlussendlich werden die vorherigen Analysen und Resultate verwendet und so adaptiert, dass Anteile von verschiedene Autoren in einem gemeinschaftlich verfassten Text automatisch erkannt werden können.
- TextdokumentRegularisierte Optimierungsverfahren für Rekonstruktion und Modellierung in der Computergraphik(Ausgezeichnete Informatikdissertationen 2014, 2015) Wenger, StephanDas Feld der Computergraphik beschäftigt sich mit virtuellen Abbildern der realen Welt, welche durch Modellierung oder Rekonstruktion aus Messdaten erstellt werden. Rekonstruktionsprobleme werden oft als regularisierte Optimierungsprobleme formuliert, in denen ein Datenterm die Konsistenz zwischen Modell und Daten sicherstellt, während ein Regularisierungsterm plausible Lösungen begünstigt. In meiner Arbeit zeige ich, dass verschiedene Rekonstruktionsprobleme der Computergraphik Instanzen einer gemeinsamen Klasse von Optimierungsproblemen sind, die mit einem einheitlichen algorithmischen Framework gelöst werden können. Darüber hinaus wird gezeigt, dass vergleichbare Optimierungsverfahren auch genutzt werden können, um Probleme der datenbasierten Modellierung zu lösen, bei denen die aus Messungen verfügbaren Daten nicht für eine genaue Rekonstruktion ausreichen. Als praxisrelevante Beispiele für Rekonstruktionsprobleme werden Sparsity- und Group-Sparsity-Methoden für die radiointerferometrische Bildrekonstruktion vorgestellt. Als Beispiel für Modellierung werden analoge Verfahren untersucht, um automatisch volumetrische Modelle astronomischer Nebel aus Einzelbildern zu erzeugen. Die Ergebnisse dieser Arbeit haben über das akademische Umfeld hinaus Sichtbarkeit erlangt und werden heute von mehreren Softwareunternehmen aus der Planetarienbranche praktisch eingesetzt.
- TextdokumentSkalierbare Analyse von räumlichen Daten in großangelegten wissenschaftlichen Simulationen(Ausgezeichnete Informatikdissertationen 2014, 2015) Tauheed, FarhanDie Wissenschaft befindet sich heutzutage in einem radikalen Umbruch. Wissenschaftler müssen sich heute nicht mehr nur auf traditionelle wissenschaftliche Methoden des Experimentierens, dem entwickeln von Theorien und dem Testen von Hypothesen verlassen. Zusätzlich können sie heute auch massive Mengen von Daten analysieren um neue wissenschaftliche Erkenntnisse zu erlangen. Immer schnellere Hardware sowie immer genauere Sensoren ermöglichen ihnen das Sammeln von Daten, das Bauen von Modellen und das Simulieren von Naturphänomenen im großen Maßstab. Wissenschaftliche Entdeckungen in diesem Zusammenhang bedingen allerdings Algorithmen für die effiziente Analyse von massiven Datenmengen. Die heute enormen Datenmengen machen die Ausführung der notwendigen Analysen zu einer beispiellosen Herausforderung. Die Effizienz heutiger Algorithmen reicht nicht aus um die Datenmengen schnell genug zu analysieren und das Problem wird immer schlimmer da die Datenmengen rasant wachsen. Diese Doktorarbeit konzentriert sich auf die Trends des Datenwachstums in den Wissenschaften und wie diese Trends die Leistung von Analysealgorithmen beeinflussen. Eine interessante Entwicklung bezüglich wissenschaftlicher Daten ist, dass wenn Wissenschaftler die Datenmenge erhöhen, die Daten gleichzeitig auch komplexer werden, so dass bekannte Algorithmen ineffizient werden. Die "Komplexität" der Daten wird durch die Veränderung der Datencharakteristiken, wie beispielsweise Verteilung, Dichte und Auflösung verursacht. Die Zunahme der Komplexität verschlechtert die Effizienz bestehender Algorithmen wesentlich und, noch wichtiger, hemmt auch die Skalierbarkeit der Algorithmen. Diese Arbeit schlägt eine Methodik zur Entwicklung neuer Analysealgorithmen vor welche effizient sind und besser skalieren als existierende Methoden. Mit wissenschaftlichen Daten demonstrieren wir, dass Algorithmen die mit unserer Methodik entwickelt wurden nicht nur schneller als heutige Algorithmen sind, sondern auch, dass sie wesentlich besser mit Komplexität und Größe zukünftiger Datensätze skalieren.