@phdthesis{Hofmeier2012, author = {Hofmeier, Andreas}, title = {Vergleichen und Aggregieren von partiellen Ordnungen}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26858}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {Das Vergleichen und Aggregieren von Informationen ist ein zentraler Bereich in der Analyse von Wahlsystemen. In diesen m{\"u}ssen die verschiedenen Meinungen von W{\"a}hlern {\"u}ber eine Menge von Kandidaten zu einem m{\"o}glichst gerechten Wahlergebnis aggregiert werden. In den meisten politischen Wahlen entscheidet sich jeder W{\"a}hler durch Ankreuzen f{\"u}r einen einzigen Kandidaten. Daneben werden aber auch Rangordnungsprobleme als eine Variante von Wahlsystemen untersucht. Bei diesen bringt jeder W{\"a}hler seine Meinung in Form einer totalen Ordnung {\"u}ber der Menge der Kandidaten zum Ausdruck, wodurch seine oftmals komplexe Meinung exakter repr{\"a}sentiert werden kann als durch die Auswahl eines einzigen, favorisierten Kandidaten. Das Wahlergebnis eines Rangordnungsproblems ist dann eine ebenfalls totale Ordnung der Kandidaten, welche die geringste Distanz zu den Meinungen der W{\"a}hler aufweist. Als Distanzmaße zwischen zwei totalen Ordnungen haben sich neben anderen Kendalls Tau-Distanz und Spearmans Footrule-Distanz etabliert. Durch moderne Anwendungsm{\"o}glichkeiten von Rangordnungsproblemen im maschinellen Lernen, in der k{\"u}nstlichen Intelligenz, in der Bioinformatik und vor allem in verschiedenen Bereichen des World Wide Web r{\"u}cken bereits bekannte, jedoch bislang eher wenig studierte Aspekte in den Fokus der Forschung. Zum einen gewinnt die algorithmische Komplexit{\"a}t von Rangordnungsproblemen an Bedeutung. Zum anderen existieren in vielen dieser Anwendungen unvollst{\"a}ndige „W{\"a}hlermeinungen" mit unentschiedenen oder unvergleichbaren Kandidaten, so dass totale Ordnungen zu deren Repr{\"a}sentation nicht l{\"a}nger geeignet sind. Die vorliegende Arbeit greift diese beiden Aspekte auf und betrachtet die algorithmische Komplexit{\"a}t von Rangordnungsproblemen, in denen W{\"a}hlermeinungen anstatt durch totale Ordnungen durch schwache oder partielle Ordnungen repr{\"a}sentiert werden. Dazu werden Kendalls Tau-Distanz und Spearmans Footrule-Distanz auf verschiedene nahe liegende Arten verallgemeinert. Es zeigt sich dabei, dass nun bereits die Distanzberechnung zwischen zwei Ordnungen ein algorithmisch komplexes Problem darstellt. So ist die Berechnung der verallgemeinerten Versionen von Kendalls Tau-Distanz oder Spearmans Footrule-Distanz f{\"u}r schwache Ordnungen noch effizient m{\"o}glich. Sobald jedoch partielle Ordnungen betrachtet werden, sind die Probleme NP-vollst{\"a}ndig, also vermutlich nicht mehr effizient l{\"o}sbar. In diesem Fall werden Resultate zur Approximierbarkeit und zur parametrisierten Komplexit{\"a}t der Probleme vorgestellt. Auch die Komplexit{\"a}t der Rangordnungsprobleme selbst erh{\"o}ht sich. F{\"u}r totale Ordnungen effizient l{\"o}sbare Varianten werden f{\"u}r schwache Ordnungen NP-vollst{\"a}ndig, f{\"u}r totale Ordnungen NP-vollst{\"a}ndige Varianten hingegen liegen f{\"u}r partielle Ordnungen teilweise außerhalb der Komplexit{\"a}tsklasse NP. Die Arbeit schließt mit einem Ausblick auf offene Problemstellungen.}, language = {de} } @phdthesis{Matzeder2012, author = {Matzeder, Marco}, title = {Zeichnen von B{\"a}umen auf Gittern}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus-26923}, school = {Universit{\"a}t Passau}, year = {2012}, abstract = {Das Zeichnen von Graphen besch{\"a}ftigt sich mit der Frage, wie die durch einen Graphen repr{\"a}sentierten Informationen f{\"u}r einen Betrachter {\"u}bersichtlich und verst{\"a}ndlich dargestellt werden k{\"o}nnen. Die Graphklasse der B{\"a}ume dient insbesondere zur Repr{\"a}sentation von hierarchischen Strukturen. Neben den hierarchisch und radial darstellenden Verfahren werden B{\"a}ume auch auf dem orthogonalen Gitter gezeichnet, in welchem die Knoten auf ganzzahligen Koordinaten liegen und die Kanten entlang der horizontalen und vertikalen Gitterlinien verlaufen. Gew{\"u}nscht wird eine gute Lesbarkeit der Zeichnungen und deren effiziente Berechnung. F{\"u}r die formale Bewertung der Lesbarkeit existieren speziell f{\"u}r das Zeichnen von B{\"a}umen definierte {\"A}sthetikkriterien, wie eine ebenenweise Darstellung, die Ordnungserhaltung und Kriterien zur Darstellung von Subgraphisomorphien und Symmetrien. Die vorliegende Arbeit befasst sich mit einer bislang wenig studierten Erweiterung des orthogonalen Gitters auf das hexagonale und oktagonale Gitter durch das Hinzunehmen von einer bzw. beider diagonalen Gitterrichtungen, und der Problemstellung, wie B{\"a}ume darauf gezeichnet werden. Dadurch k{\"o}nnen auch B{\"a}ume mit einem h{\"o}heren Grad gezeichnet werden als auf dem orthogonalen Gitter. Die Einschr{\"a}nkung, dass nur B{\"a}ume gezeichnet werden k{\"o}nnen, deren Grad kleiner ist als die Anzahl der Gitterrichtungen des verwendeten Gitters, besteht jedoch weiterhin. Als {\"A}sthetikkriterien werden die lokale Uniformit{\"a}t, die die L{\"a}nge der ausgehenden Kanten eines Knotens festlegt, und Pattern, die deren Richtungen festlegen, eingef{\"u}hrt. Gegen{\"u}ber dem bekannten linearen Fl{\"a}chenverbrauch von geradlinigen Zeichnungen von vollst{\"a}ndigen Bin{\"a}rb{\"a}umen auf dem orthogonalen Gitter, werden f{\"u}r Zeichnungen von vollst{\"a}ndigen d-n{\"a}ren B{\"a}umen mit d > 2 nicht-lineare untere Schranken f{\"u}r die ben{\"o}tigte Fl{\"a}che auf dem hexagonalen und dem oktagonalen Gitter gezeigt. Insgesamt werden f{\"u}r vollst{\"a}ndige und beliebige, geordnete und ungeordnete B{\"a}ume obere und untere Fl{\"a}chenschranken f{\"u}r Zeichnungen auf dem hexagonalen und oktagonalen Gitter pr{\"a}sentiert. Dabei zeigt sich, dass bei nicht-ordnungserhaltenden Zeichnungen zwar mehr als lineare, aber deutlich weniger als quadratische Fl{\"a}che ben{\"o}tigt wird. Im Gegensatz dazu gibt es geordnete B{\"a}ume, deren ordnungserhaltende Zeichnungen exponentielle Fl{\"a}che ben{\"o}tigen. Des Weiteren wird die Ermittlung der minimalen Zeichenfl{\"a}che f{\"u}r geordnete d-n{\"a}re B{\"a}ume ebenso als NP-vollst{\"a}ndig bewiesen, wie das Zeichnen von ungeordneten d-n{\"a}ren B{\"a}umen mit einheitlichen Kantenl{\"a}ngen. Schließlich werden zwei Linearzeitalgorithmen vorgestellt, die geordnete d-n{\"a}re B{\"a}ume unter Einhaltung der genannten {\"A}sthetikkriterien zeichnen.}, subject = {Baum }, language = {de} }