Universitšt Oldenburg
Fachbereich Informatik

Zu vergebenden studentische Arbeiten


  • Diplomarbeit in den Bereichen graphische interaktive Benutzeroberflächen und Graphentheorie

    Interaktive graphische Benutzerschnittselle für das System GHS

    Das System GHS (Graph Handling System) ist ein umfangreiches System zur Untersuchung und Bearbeitung von großen Graphen. Unter anderem umfaßt es eine Reihe neuartiger Verfahren zur Graphzerlegung. Es wurde in der Arbeitsgruppe "Graphen und Netzwerke" (vormals Abteilung für Betriebssysteme und Verteilte Systeme) entwickelt und besteht aus einer C-Bibliothek mit entsprechenden Funktionen und Datenstrukturen. Zur Benutzung des Systems ist zur Zeit ein (i.a. kleines) C-Programm zu schreiben. Die Eingabe von Daten (z.B. externe Graphbeschreibungen) erfolgt über die Standardeingabe. Die Ergebnisse werden in Listen ausgegeben.

    In der Diplomarbeit soll ein interaktives graphisches System entworfen und realisiert werden, mit dem die Funktionen von GHS aufgerufen und die Ergebnisse dargestellt werden können. Unter anderem sollen vorhandene und neu abgeleitete Strukturen (Graphen, Untergraphen, Zerlegungen, ...) in einem hierarchischen Verzeichnis verwaltet und aus diesem heraus bearbeitet werden. Eine Plug-in-Schnittstelle für die graphische Darstellung solcher Strukturen ist vorzusehen. Das System soll durch einen Web-Browser benutzbar sein und mit Enterprise Java Techniken realisiert werden.

    Die Arbeit wird gemeinschaftlich von der Arbeitsgruppe "Graphen und Netzwerke" und der Abteilung für Software Engineering vergeben.

    Weitere Informationen bei: Prof. Dr. G. Stiege, Raum A5-2-231, oder Dr. I. Stierand, Raum A5-2-235


  • Studienarbeit/Individuelles Projekt

    Konstruktion und Untersuchung des Cliquengraphen von words.dat

    words.dat ist eine umfangreiche, von Knuth [Knut93] zusammengestellte Sammlung englischer Wörter aus 5 Buchstaben. Die Sammlung wird als schlichter Graph aufgefaßt, indem zwei Wörter, die sich an genau einer Stelle unterscheiden, durch eine Kante verbunden werden. Im Gegensatz zu allgemeinen schlichten Graphen gibt es für words.dat einfache effiziente Algorithmen zur Bestimmung aller maximalen (d.h. nicht mehr erweiterbaren) Cliquen. Eine weitere Besonderheit ist, daß in words.dat zwei maximale Cliquen höchstens einen gemeinsamen Knoten haben. Das erlaubt es, für words.dat einen "Cliquengraphen" zu definieren: Seine Knoten sind die maximalen Cliquen und zwei Cliquen sind genau dann durch eine Kante verbunden, wenn sie im Ausgangsgraphen einen gemeinsamen Knoten haben.

    Die Aufgabe der Arbeit beteht darin, den Cliquengraphen zu konstruieren und seine Eigenschaften zu untersuchen. Dazu ist das System GHS (Graph Handling System) zu verwenden.

    Weitere Informationen bei: Prof. Dr. G. Stiege, Raum A5-2-231, oder Dr. I. Stierand, Raum A5-2-235


  • Diplomarbeit/Doppelstudienarbeit/Studienarbeit/Individuelles Projekt

    Erzeugung und Sammlung von Testgraphen

    Das System GHS (Graph Handling System) ist ein umfangreiches System zur Untersuchung und Bearbeitung von großen Graphen. Unter anderem umfaßt es eine Reihe neuartiger Verfahren zur Graphzerlegung. Es wurde in der Arbeitsgruppe "Graphen und Netzwerke" (vormals Abteilung für Betriebssysteme und Verteilte Systeme) entwickelt und besteht aus einer C-Bibliothek mit entsprechenden Funktionen und Datenstrukturen. Zur Benutzung des Systems ist zur Zeit ein (i.a. kleines) C-Programm zu schreiben. Die Eingabe von Daten (z.B. externe Graphbeschreibungen) erfolgt über die Standardeingabe. Die Ergebnisse werden in Listen ausgegeben. Eine graphische interaktive Benutzerschnittstelle ist geplant.

    Die Arbeit hat zum Ziel, Graphen unterschiedlicher Art zum Testen von GHS und für andere Zwecke bereitzustellen. Das soll auf die folgenden drei Arten geschehen.

    Anmerkung: Für eine Diplomarbeit/Doppelstudienarbeit sind alle drei Punkte der Aufgabenstellung zu bearbeiten. Für eine einfache Studienarbeit/individuelles Projekt sind nur die Punkte 1. und 2. zu bearbeiten.


  • Studienarbeit/Individuelles Projekt

    Installation, Erprobung und Einführung des Systems LEDA

    LEDA [MehlN99] (siehe auch Algorithmic Solutions Software GmbH ) ist eine umfangreiche C++-Klassenbibliothek für effiziente Datentypen und Algorithmen. Das System soll mit einer neuen Lizenz im Bereich "Graphen und Netzwerke" eingesetzt werden.

    Die Aufgabe der Arbeit beteht aus zwei Teilen. Zum einen soll das System installiert, getestet und künftigen Benutzern in einer Präsentation vorgestellt werden. Zum anderen ist ein Propgramm zur Formatumsetzung zu erstellen, mit dem Graphdaten zwischen den Systemen LEDA und GHS (Graph Handling System) ausgetauscht werden können. Auch die Umsetzung ist in einer Präsentation vorzustellen.


    Weitere Informationen bei: Prof. Dr. G. Stiege, Raum A5-2-231, oder Dr. I. Stierand, Raum A5-2-235



    Last change: Oct 29 2002 stiege