http://nobi.ethz.ch/group/stud_proj.html (PC Press Internet CD, 03/1996)
Diplom- & Semesterarbeiten SS96
- Algorithmen und Datenstrukturen
- Wir arbeiten in den Bereichen algorithmische Geometrie
und Heuristik, und es interessieren uns vor allem parallele
Algorithmen und deren Implementation. Die meisten Themen
können als Diplom- oder als Semesterarbeit behandelt
werden.
- Branch-and-Cut-Algorithmus [DA,SA]
- Parallele Alpha-Beta-Suche [DA,SA]
- Schnelle Memoryfunktionen bei
Branch and Bound Algorithmen [DA,SA]
- Partial reverse search [SA]
- Einsatz von Parallelrechnern für
erschöpfendes Suchen in grossen Zustandsräumen [DA,SA]
- Parallelisierung unregelmässiger Probleme [DA,SA]
- Heuristiken für Retrograde Analysis [DA]
- Portable 2D/3D-Interface-Definition und -Library [DA]
- Heuristischer Algorithmus für die Datenbankkompression [DA]
- Computational Geometry & Applications [DA]
- Informatikdidaktik
- Visualisierungen und Animationen: Didaktik in der Informatik [DAs]
- Spielprogramme für den Unterricht [DA]
- Karel the Robot - in Java [SA]
Der Branch-and-Cut-Algorithmus ist eine Erweiterung des
Branch-and-Bound für kombinatorische Optimierungsprobleme.
Dabei werden mittels Methoden der linearen Programmierung
Schranken fuer das Optimum berechnet. In der Arbeit soll
das Knapsack- oder ein ähnliches Problem mit Branch-and-Cut
gelöst werden. Vorhandene Bibliotheken können verwendet
werden. Eventuell wird die Software auf Parallelrechner
portiert.
Kontaktperson und Betreuung:
Ambros Marzetta
marzetta@inf.ethz.ch
Der in Zweipersonenspielen verwendete Alpha-Beta-Algorithmus
soll auf einem Parallelrechner (z.B.
GigaBooster)
implementiert werden. Als Anwendung sind diverse Spiele denkbar.
Kontaktperson und Betreuung:
Ambros Marzetta
marzetta@inf.ethz.ch
Branch and Bound ist ein häufig eingesetztes Werkzeug zum Lösen von
kombinatorischen Optimierungsproblemen. Anhand eines selbstgewählten
Beispiels (a. B. NP vollständiges Graphenproblem,
...) sollen die Möglichkeiten von schnellen Memoryfunktionen (Hashing,
History, Node-Ordering) ausgelotet werden. Zur Implementation in C
steht eine komfortable Umgebung (auch für Parallelrechner) zur Verfügung.
Kontaktperson und Betreuung:
Adrian Brüngger
bruengg@inf.ethz.ch
Partial reverse search ist eine mit dem Simplex-Algorithmus
verwandte Methode, um ganzzahlige lineare Programme zu lösen.
In einer Semesterarbeit sollen dieser Suchalgorithmus effizient
auf einem Parallelrechner implementiert und eventuell die
Resultate graphisch dargestellt werden.
Kontaktperson und Betreuung:
Ambros Marzetta
marzetta@inf.ethz.ch
Wir arbeiten an verschiedenen rechenintensiven Suchproblemen.
Beispiele: kombinatorische Rechnungen wie das Traveling Salesman
Problem; Berechnen der optimalen Spielweise für gewisse
Teilspiele in Schach und Mühle. Auf einer seriellen Maschine
dauert die Suche nach Lösungen Tage oder Wochen. Wir möchten
effiziente Suchalgorithmen für
Parallelrechner entwickeln, um grössere Probleme lösen
zu können.
Kontaktperson und Betreuung:
Ambros Marzetta
marzetta@inf.ethz.ch
Es gibt viele Probleme, die nicht so einfach parallelisierbar sind wie
die Multiplikation zweier Matrizen: zum Beispiel Einpersonenspiele (Schiebepuzzle,
Rubikwürfel,...), Knapsackproblem, Färben von Graphen,
Traveling Salesman, Zweipersonenspiele usw. Es geht darum, derartige
Probleme auf den Parallelrechnern Music, Paragon oder GigaBooster zu
implementieren, den Erfolg der Parallelisierung zu messen und
Gemeinsamkeiten bzw. Unterschiede zwischen den Algorithmen
festzustellen.
Kontaktperson und Betreuung:
Ambros Marzetta
marzetta@inf.ethz.ch
Erschöpfendes Rückwärts-Suchen (Exhaustive retrogarde analysis)
hat sich für die Berechnung von Zustandsräumen mit bis zu 10G
Zuständen bewährt (vgl. z.Bsp. Thompson, Stiller, Gasser), grössere
Räume liegen aber zur Zeit jenseits des Machbaren.
Mit Expertenwissen (Heuristiken) wollen wir Teile des Zustandsraumes
reduzieren (bezüglich Speicher + Rechenaufwand), wobei dabei Fehler
in Kauf genommen werden müssen. Für Bauernendspiele haben wir eine
Reduktion des Speichers und der Laufzeit um einen Faktor 30 bei einer
Fehlerrate von 2.5% erreicht.
Ziel der Arbeit ist, diese Versuche auf weitere Schachendspiele
auszudehnen, und dabei einen Satz an allgemein verwendbaren
Endspielheuristiken zu implementieren.
Kontaktperson und Betreuung:
Christoph Wirth
wirthc@inf.ethz.ch
Für die verschiedenen Anwendungen in unserer Gruppe verwenden
wir die unterschiedlichsten Plattformen - Unixrechner mit X, Motif,
Macintoshs und PCs unter Windows.
Ziel der Arbeit ist, eine system-unabhängige Library zu entwerfen,
die einen Basissatz an Funktionen im 2D/3D anbietet. In einem zweiten
Schritt soll diese Library auf den erwähnten Systemen implementiert
werden.
Kontaktpersonen und Betreuung:
Matthias Müller
muellerm@inf.ethz.ch,
Christoph Wirth
wirthc@inf.ethz.ch
Unsere erschöpfenden Datenbankberechnungen erzeugen grosse Datenmengen.
Um mit diesen arbeiten zu können, ist eine Kompression notwendig. Bekannte
Kompressionsmethoden wie Run-length oder Lempel-Ziv Kodierung arbeiten ohne a
priori Wissen über die Daten. Erfolgversprechender scheint ein Ansatz, bei
dem das problemspezifische Wissen, d.h. Wissen über den betrachteten
Zustandsraum, explizit verwendet wird.
Ziel dieser Diplomarbeit: Implementierung eines allgemeinen Programmmoduls,
welches vom bestehenden Datenbankberechnungspaket verwendet werden kann,
sowie Leistungsmessungen.
Kontaktperson und Betreuung:
Thomas Lincke
lincke@inf.ethz.ch
Partitioning of graphs (e.g. finite element meshes, triangulations, and
unstructured meshes for aircraft, jet engine, and space shuttle modeling)
is used for optimal load balancing and minimizing interprocessor
communication costs in parallel implementation. The goal of the
"Diplomarbeit" is to make a comparison of several existing methods
(public domain software) by applying them to the Boeing-Harwell, NASA and other
test data libraries. Implementation and/or improvements of known heuristics
(spectral graph partitioning, greedy algorithm, etc.) are further
possibilities.
Kontaktpersonen und Betreuung:
Nora Sleumer
sleumer@inf.ethz.ch,
E. von Stürler (CSCS)
sturler@scsc.ethz.ch
Im Gebiet der Informatikdidaktik werden in der Regel Visualisierungen und
Animationen zu grundlegenden Themen aus dem Bereich "Algorithmen und
Datenstrukturen" hergestellt. Das Spektrum solcher interaktiver
Unterrichtssoftware ist sehr breit. Es sind Anwendungen aus dem Umfeld der
Geometrie, der Spieltheorie, der Graphentheorie, dynamischer
Datenstrukturen, Rechnerarchitekturen usw. denkbar.
Kontaktperson und Betreuung:
W. Hartmann
hartmann@inf.ethz.ch
Wie funktionieren Spielprogramme? Dies soll eine Unterrichtssoftware an einem
Beispiel ("Awari") illustrieren. Der Anwender kann beispielsweise die
Berwertungsfunktionen ändern und somit beurteilen oder die Baumsuche
anhand einer Animation nachvollziehen.
Die Entwicklung der Software gliedert sich in zwei Teile: Einerseits soll ein allgemein
verwendbares "Grundgerüst" für beliebige (2 Personen-) Spiele entwickelt werden. Dieser Teil basiert auf dem vorhandenen "Simple Game Board".
Darauf aufbauend erfolgt die Implementierung des (Awari-) Spiels.
Entwicklungsumgebung ist die Programmiersprache "Java" auf dem
Macintosh.
Kontaktperson und Betreuung:
Fabian Mäser
maeser@inf.ethz.ch,
Silvia Ackermann
ackermann@inf.ethz.ch
Karel the Robot ist eine Lernumgebung zur Einführung
ins algorithmische Problemlösen mittels strukturierter Programmiersprachen.
Karel ist in einer einfachen, PASCAL-ähnlichen Programmiersprache
geschrieben. Es beinhaltet einen einfachen "graphischen" Interpreter.
Ziel der Semesterarbeit ist es, "Karel the Robot" auf Java
umzuschreiben.
Kontaktpersonen und Betreuung:
W. Hartmann
hartmann@inf.ethz.ch,
Silvia Ackermann
ackermann@inf.ethz.ch
[Department
| Gruppe ]
ETH Zürich: Department of Computer Science
Institute of Theoretical Computer Science
Comments to ackermann@inf.ethz.ch
February 26, 1996