Springe zum Hauptinhalt

Promotion/Habilitation

| 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001 | 2000 | 1999 | 1998 | 1997 |


Promotionen der Fakultät für Informatik im Jahr 2011


Hörr, Christian
"Algorithmen zur automatisierten Dokumentation und Klassifikation archäologischer Gefäße"
Promotion zum Dr.-Ing.

Gutachter: Prof. Dr. Guido Brunnett (Technische Universität Chemnitz), Prof. Dr. Fred Hamker (Technische Universität Chemnitz)

Abstract deutsch:
Gegenstand der vorliegenden Dissertation ist die Entwicklung von Algorithmen und Methoden mit dem Ziel, Archäologen bei der täglichen wissenschaftlichen Arbeit zu unterstützen.
Im Teil I werden Ideen präsentiert, mit denen sich die extrem zeitintensive und stellenweise stupide Funddokumentation beschleunigen lässt. Es wird argumentiert, dass das dreidimensionale Erfassen der Fundobjekte mittels Laser- oder Streifenlichtscannern trotz hoher Anschaffungskosten wirtschaftlich und vor allem qualitativ attraktiv ist. Mithilfe von nicht fotorealistischen Visualisierungstechniken können dann wieder aussagekräftige, aber dennoch objektive Bilder generiert werden. Außerdem ist speziell für Gefäße eine vollautomatische und umfassende Merkmalserhebung möglich. Im II. Teil gehen wir auf das Problem der automatisierten Gefäßklassifikation ein. Nach einer theoretischen Betrachtung des Typbegriffs in der Archäologie präsentieren wir eine Methodologie, in der Verfahren sowohl aus dem Bereich des unüberwachten als auch des überwachten Lernens zum Einsatz kommen. Besonders die letzteren haben sich dabei als überaus praktikabel erwiesen, um einerseits unbekanntes Material einer bestehenden Typologie zuzuordnen, andererseits aber auch die Struktur der Typologie selbst kritisch zu hinterfragen. Sämtliche Untersuchungen haben wir beispielhaft an den bronzezeitlichen Gräberfeldern von Kötitz, Altlommatzsch (beide Lkr. Meißen), Niederkaina (Lkr. Bautzen) und Tornow (Lkr. Oberspreewald-Lausitz) durchgeführt und waren schließlich sogar in der Lage, archäologisch relevante Zusammenhänge zwischen diesen Fundkomplexen herzustellen.

Abstract englisch:

The topic of the dissertation at hand is the development of algorithms and methods aiming at supporting the daily scientific work of archaeologists. Part I covers ideas for accelerating the extremely time-consuming and often tedious documentation of finds. It is argued that digitizing the objects with 3D laser or structured light scanners is economically reasonable and above all of high quality, even though those systems are still quite expensive. Using advanced non-photorealistic visualization techniques, meaningful but at the same time objective pictures can be generated from the virtual models. Moreover, specifically for vessels a fully-automatic and comprehensive feature extraction is possible.
In Part II, we deal with the problem of automated vessel classification. After a theoretical consideration of the type concept in archaeology we present a methodology, which employs approaches from the fields of both unsupervised and supervised machine learning. Particularly the latter have proven to be very valuable in order to assign unknown entities to an already existing typology, but also to challenge the typology structure itself. All the analyses have been exemplified by the Bronze Age cemeteries of Kötitz, Altlommatzsch (both district of Meißen), Niederkaina (district of Bautzen), and Tornow (district Oberspreewald-Lausitz). Finally, we were even able to discover archaeologically relevant relationships between these sites.

 

Kai Plociennik
"From Worst-Case to Average-Case Efficiency - Approximating Combinatorial Optimization Problems"
Promotion zum Dr.rer.nat.

Gutachter: Prof. Dr. Andreas Goerdt (Technische Universität Chemnitz), Prof. Dr. Hanno Lefmann (Technische Universität Chemnitz)

Abstract englisch:
In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different.

In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms.

Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.

Foto1 Promotionsverteidigung
Foto2 Promotionsverteidigung
Foto3 Promotionsverteidigung

Kunis, Raphael
"Realisierung einer Schedulingumgebung für gemischt-parallele Anwendungen und Optimierung von layer-basierten Schedulingalgorithmen"
Promotion zum Dr.-Ing.

Gutachter: Prof. Dr. Gudula Rünger (Technische Universität Chemnitz), Prof. Dr. Wolfram Hardt (Technische Universität Chemnitz)

Abstract deutsch:
Eine Herausforderung der Parallelverarbeitung ist das Erreichen von Skalierbarkeit großer paralleler Anwendungen für verschiedene parallele Systeme. Das zentrale Problem ist, dass die Ausführung einer Anwendung auf einem parallelen System sehr gut sein kann, die Portierung auf ein anderes System in der Regel jedoch zu schlechten Ergebnissen führt. Durch die Verwendung des Programmiermodells der parallelen Tasks mit Abhängigkeiten kann die Skalierbarkeit für viele parallele Algorithmen deutlich verbessert werden. Die Programmierung mit parallelen Tasks führt zu Task-Graphen mit Abhängigkeiten zur Darstellung einer parallelen Anwendung, die auch als gemischt-parallele Anwendung bezeichnet wird. Die Grundlage für eine effiziente Abarbeitung einer gemischt-parallelen Anwendung bildet ein geeigneter Schedule, der eine effiziente Abbildung der parallelen Tasks auf die Prozessoren des parallelen Systems vorgibt. Für die Berechnung eines Schedules werden Schedulingalgorithmen eingesetzt.

Ein zentrales Problem bei der Bestimmung eines Schedules für gemischt-parallele Anwendungen besteht darin, dass das Scheduling bereits für Single-Prozessor-Tasks mit Abhängigkeiten und ein paralleles System mit zwei Prozessoren NP-hart ist. Daher existieren lediglich Approximationsalgorithmen und Heuristiken um einen Schedule zu berechnen. Eine Möglichkeit zur Berechnung eines Schedules sind layerbasierte Schedulingalgorithmen. Diese Schedulingalgorithmen bilden zuerst Layer unabhängiger paralleler Tasks und berechnen den Schedule für jeden Layer separat.
Eine Schwachstelle dieser Schedulingalgorithmen ist das Zusammenfügen der einzelnen Schedules zum globalen Schedule. Der vorgestellte Algorithmus Move-blocks bietet eine elegante Möglichkeit das Zusammenfügen zu verbessern. Dies geschieht durch eine Verschmelzung der Schedules aufeinander folgender Layer.

Obwohl eine Vielzahl an Schedulingalgorithmen für gemischt-parallele Anwendungen existiert, gibt es bislang keine umfassende Unterstützung des Schedulings durch Programmierwerkzeuge. Im Besonderen gibt es keine Schedulingumgebung, die eine Vielzahl an Schedulingalgorithmen in sich vereint. Die Vorstellung der flexiblen, komponentenbasierten und erweiterbaren Schedulingumgebung SEParAT ist der zweite Fokus dieser Dissertation. SEParAT unterstützt verschiedene Nutzungsszenarien,
die weit über das reine Scheduling hinausgehen, z.B. den Vergleich von Schedulingalgorithmen und die Erweiterung und Realisierung neuer Schedulingalgorithmen. Neben der Vorstellung der Nutzungsszenarien werden sowohl die interne Verarbeitung eines Schedulingdurchgangs als auch die komponentenbasierte Softwarearchitektur detailliert vorgestellt.

Foto1 Promotionsverteidigung
Foto2 Promotionsverteidigung