Liste der Praktika und Diplomarbeiten

Praktika und Diplomarbeiten

Gegenwärtig optimiert gcc (bzw. egcs) nur direkt rekursive tail-calls. Diese Optimierung soll möglichst allgemein für tail-calls erweitert werden.

Neuere Prozessoren führen Statistiken über viele Vorgänge wie das genaue Verhalten des Cache. In diesem Praktikum sollen diese Daten über eine möglichst allgemein gehaltene Schnittstelle unter Linux für intel x86 und dec alpha zur Verfügung gestellt werden.

Voraussetzungen: Linux-Kernel

Viele Prozessoren erlauben es, während der Laufzeit die Betriebsfrequenz des Prozessors herunterzusetzen. Dadurch laufen Programme natürlich langsamer. Der Stromverbrauch geht jedoch effektiv meist stärker als nur proportional zurück. Wenn also keine hohen Anforderungen an die Antwortzeit eines Prozesses bestehen, kann es energiesparender sein, diesen Prozess bei niedriger Taktfrequenz auszuführen, statt ihn bei höchster Frequenz auszuführen und entsprechend früher in die Idle-Loop zu gehen.

• BIOS-Schnittstellen
• Scheduler
• Traces

Literatur: Mark Weiser, Alan Demers, Brent Welch, Scott Shenker. "Scheduling for Reduced CPU Energy", Operating System Design and Implementation (OSDI) Conference, Monterey, CA. November, 1994.

Voraussetzungen: Linux-Kernel

Programm slicing ist eine Programmanalysetechnik, um jene Programmteile herauszufinden, die für gewisse Eigenschaften verantwortlich sind. Im folgenden Programm ist etwa nur ein sehr kleiner Teil für die Nichttermination der Anfrage verantwortlich. Die in der Laborübung logikorientierte Programmiersprachen verwendeten Lesarten sollen nun mittels Slicing-Techniken implementiert werden. Eine Technik zur Generierung von Slices, die die Terminationseigenschaft eines Programms erklärt, wurde bereits entwickelt. Siehe dazu den Artikel Termination slicing in logic programs.

:- phrase(rnaloop, "AAAGCGTTT").
rnaloop -->
   {Bs = [_,_,_|_]},
   complseq(Bs), {false},
   list([_,_,_|_]),
   list(Bs).
%
list([]) --> {false},
   [].
list([E|Es]) --> {false},
   [E],
   list(Es).
%
complseq([]) --> {false},
   [].
complseq([B|Bs]) -->
   complseq(Bs), {false},
   [C],
   {base_compl(C,B)}.
%
base_compl(0'A,0'T) :- false.
base_compl(0'T,0'A) :- false.
base_compl(0'C,0'G) :- false.
base_compl(0'G,0'C) :- false.

Voraussetzungen: Prologübung

Constraints erlauben die flexible Analyse von Programmanhängigkeiten. In dieser Diplomarbeit sollen constraints zur Implementierung einer Datenflußanalyse eingesetzt werden

Voraussetzungen: Prologübung

Seiteneffekte, wie sie in herkömmlichen Programmiersprachen üblich sind, passen nicht direkt zu deklarativen Programmiersprachen. Wie Entwicklungen vor allem in puren funktionalen Programmiersprachen gezeigt haben, ist es aber dennoch möglich Seitenffekte mit einer deklarativen Programmiersprache zu verbinden. Es sollen die bisherigen Ansätze zusammengefaßt werden, und auf Logik-Programmiersprachen angewandt werden.

Voraussetzungen: Prologübung

Die Wahl der richtigen Methode zum Labeling eines Constraintsystems entscheidet oft über seine praktische Einsetzbarkeit. Vergleich anhand konkreter Probleme.

Voraussetzungen: Prologübung

Die meisten praktischen Implementierungen von Parsern in Prolog verwenden Seiteneffekte zum Lesen einer Datei. Durch neuere Implementierungstechniken ist es möglich geworden, daß eine Datei direkt auf eine Liste von Zeichen effizient abgebildet werden kann. Dadurch erübrigt sich die Verwendung von Seiteneffekten innerhalb eines Parsers. Es soll ein Parser für Prolog entwickelt werden, der eine Liste von Zeichen auf den entsprechenden Prologterm abbildet. Dieser Parser soll mit existierenden Parsern verglichen werden.

Voraussetzungen: Prologübung

In diesem Werk beschreibt Raymondus Lullus (1232-1316) eine Art Grammatik zur Darstellung von Argumentationsweisen (Ars compediosa inveniendi veritatem), die sich zur Umsetzung in Prolog geradezu anbietet.

Eine interessante Persönlichkeit ist Raimundus Lullus, der um 1300 mittels mehrerer konzentrischer Scheiben, die mit verschiedenen Wörtern beschriftet waren, durch Drehen der Scheiben immer neue »Wahrheiten« hervorbrachte (»ars inveniendi«). Die Fortsetzung findet solche »automatische Wissensverarbeitung und -erzeugung« in den Kalkülen von Leibniz, de Morgan und Boole und schließlich in den regelbasierten Expertensystemen, wie man sie im Bereich der sogenannten Künstlichen Intelligenz hat. (Aus: Uni Ulm intern, Juni 1995:

• Die Ars des Raimundus Lullus. Eine mediterrane Kommunikationslogik, Berlin 1989, text machines text
• Texte der österreichischen Nationalbibliothek.
• Kommt in vielen Romanen vor: Umberto Eco, Die Insel des vorigen Tages als aristotelisches Fernrohr. Jonathan Swift, Gullivers Reisen. Christoph Martin Wieland, Der neue Amadis, 10. Gesang.
• Artistic Websites

Voraussetzungen: Prologübung

Zur Schonung der Batterie auf einem Laptop sollen die Plattenzugriffsstrategien von Linux adaptiert werden. üblicherweise wird durch den update-Dämon immer wieder auf die Platte zugegriffen. Dadurch ist es nicht möglich, die Platte zur Einsparung der Batterie abzuschalten. (Eine einfache, aber nicht optimale und zufriedenstellende Lösung ist es, den update-Dämon erst gar nicht zu starten und manuell zu sync-en.) Es soll eine für Laptops geeignetere Strategie implementiert werden, die die Zeit zu der die Platte abgeschaltet sein kann, maximiert.

Gegenwärtig gibt es eine relativ einfache, aber nicht optimale Lösung: mobile-update. Es fehlen vor allem Adaptierungen für Power-Managements etc.

Voraussetzungen: Linux-Kernel

Zur Darstellung gerichteter Graphen soll die Lösungsannotation graphs_marks(Graphs,Marks) realisiert werden. Dabei ist Graphs eine Liste von Prädikatsindikatoren. Jedes Prädikat beschreibt einen gerichteten Graphen, dessen Knoten Atome (Konstanten) sind. Marks ist eine Liste der Knoten, die gesondert hervorgehoben werden sollen (In diesem Falle Joseph II). Die erste Relation wird durch einfache möglichst senkrechte Striche dargestellt, die zweite durch doppelte möglichst horizontale Striche. Genauere Beschreibung im WWW.

kind_von(joseph_I, leopold_I).
kind_von(karl_VI, leopold_I).
kind_von(maria_theresia, karl_VI).
kind_von(joseph_II, maria_theresia).
kind_von(joseph_II, franz_I).
kind_von(leopold_II, maria_theresia).
kind_von(leopold_II, franz_I).
kind_von(marie_antoinette, maria_theresia).
kind_von(franz_II, leopold_II).

gatte_gattin(franz_I, maria_theresia).

:- graphs_marks([kind_von/2,gatte_gattin/2], [P]) <<< P = joseph_II.

Voraussetzungen: Prologübung

Zur besseren Darstellung einer Lösung (Antwortsubstitution) soll diese graphisch (z.B. mittels postscript) dargestellt werden. Die Treiber sollen als DCGs beschrieben werden, die einen Postscript-Text beschreiben. Ein Treiber ist also nichts anderes als eine Relation zwischen einem Term und einem Postscripttext. Hier ein kleines Beispiel. Die Zeile besagt, daß die Variable Cs als Postscripttext dargestellt werden soll. Die Variable Cs wird durch das Nichtterminal box1//0 beschrieben. Fragt man nach den Antworsubstitutionen, so wird der Postscripttext in einem eigenen Fenster dargestellt.

:- postscript(Cs) <<< phrase(box1, Cs).

:- europastadt(Stadt) <<< stadt(Stadt).

Literatur zu Postscript:

• PostScript-Minikurs, ziemlich gut
• Postscripttutorial (Dies ist eine lokale Kopie des Originals).
• Internet Postscript Resources
• Zürcher Postscriptcorner
• Cs4Ce
• Imation Postscript Pages

Voraussetzungen: Prologübung

Prozesse teilen gewisse Hauptspeicherbereiche miteinander. Etwa die nicht modifizierbaren Teile unabhängiger Prozessinstanzen, Bibliotheken und die nicht modifizierten Teile zwischen Vater- und Kindprozeß. Daten, die vom Prozeß selbst initialisiert wurden, werden jedoch nicht mit identischen Daten eines anderen Prozesses zusammengelegt. Durch das Zusammenlegen solcher Daten wird der Hauptspeicherbedarf und damit auch das Swapping (paging) in Linux weiter reduziert. Es soll a) gemessen werden, welche Speichereinsparungen dadurch erzielt werden könnten und b) der Linux-Kernel daraufhin adaptiert werden.

Siehe dazu auch das Mergemem-Projekt

Gegenwärtig sind vor allem effiziente Strategien zum Auffinden identischer Seiten von Interesse.

Voraussetzungen: Linux-Kernel

Binäres Prolog ist eine stark vereinfachte Prologvariante, die verhältnismäßig einfach zu implementieren ist. Es soll ein Compiler entwickelt werden, der BinWAM-Code erzeugt.

Voraussetzungen: Prologübung

Die Ablaufmechanismen von Prologmaschinen sollen visualisiert werden. Beispiel 2-dimensionale Darstellung von WAM und VAM.

1. Graphischer Entwurf. Z.B. Wie stellt man Terme, Stacks, Bindungen etc. graphisch dar?
2. Animation. Für den Ablauf einer Prologmaschine beim Beweis eines konkreten Prologziels soll eine Folge von Bildbesschreibungen generiert werden.

Voraussetzungen: Prologübung

Es soll eine Schnittstelle entworfen werden, um Programmtransformationen in der Programmierumgebung GUPU interaktiv durchführen zu können.

Voraussetzungen: Prologübung

Für die Programmierumgebung GUPU wurde ein spezieller Emacs-Mode entwickelt, der das Entwickeln und Testen von Prologprogrammen unterstützt. Es soll ein allgemeiner einsetzbarer Mode zum Entwickeln und Testen von Prologprogrammen entwickelt werden.

Voraussetzungen: Emacs und Emacs-Lisp

Weitere mögliche Themenbereiche:

• Abstrakte Maschinen
• Algorithmen
• Animation
• Anwendungsprogrammierung
• Constraint Logic Programming
• Implementierung logischer Programmiersprachen
• Linux
• Postscript
• Programmanalyse
• Programmtransformationen
• Prolog
• Systemprogrammierung