Aufgabenblatt 2
Ausgabetermin:	30.10.00
Abgabetermin:	Montag d. 6.11. um 14 Uhr per Email an die Übungsgruppenleiter
Motivation:	Begleitende Übungen zum Vorlesungsthema "Dynamische Datenstrukturen". Quantifizierte Erfahrungen mit "einfachen" und "gehobenen" Sortierverfahren. Dynamische Strukturen beim Problemlösen durch Suchen.
Aufgabe 1:	In der Datei MixNamDat.txt finden Sie 20000 unsortierte Namen mit zugehörigem Geburtsdatum (aus dem 20. Jahrhundert). Dieselbe Datei gibt es komprimiert als MixNamDat.zip. Sortieren Sie die Namen nach dem Geburtsdatum und erzeugen Sie eine aufwärts und eine abwärts sortierte Datei. Implementieren Sie dazu die zwei Sortierverfahren BubbleSort und BucketSort (s. Vorlesung und z.B. Wirth, Algorithmen und Datenstrukturen). Messen Sie für jedes der zwei Verfahren die Laufzeit beim Aufwärtssortieren von 1. der unsortierten Datei 2. der abwärts sortierten Datei 3. der bereits aufwärts sortierten Datei. Überlegen Sie, inwieweit Sie bei BucketSort auch den Namen (anstelle des Datums) als Sortierschlüssel verwenden können. Der Schlüssel sollte für beliebige Namen (nicht nur Meyer.....) geeignet sein. 5 Punkte
Aufgabe 2:	Probleme lassen sich manchmal durch schrittweises Transformieren von einem Anfangszustand in einen Zielzustand lösen. In jedem Zustand stehen im Allgemeinen mehrere Operationen zur Zustandsveränderung zur Verfügung. Vermeidet man Duplizierungen, so ergibt sich ein Suchbaum, der im Laufe der Suche sukzessive erzeugt wird. Aufgabe eines Suchverfahrens ist es, die bereits erkundeten "alten" Zustände und die noch nicht erkundeten "neuen" Zustände effektiv zu verwalten (s. z.B. Nilsson, Problem-Solving Methods in Artificial Intelligence). Beispiel: Suche nach einem Pfad in einem Labyrinth von A nach B (O ist Freiraum, X ist Hindernis). Es seien die Bewegungen GeheRechts, GeheLinks, GeheOben und GeheUnten erlaubt. O O O O O O O O O O O O  O X O X X X X X X O O O O X O O O O O O X O O O A X O X O X X X X O O O O X O X O O O O O O O O O O O X O O X X X X X X O X O X O X X O O O O O O O O O O O O O X O O O O X O X O X X X X O O O O O O X X X O B X X O O O X O X O X X O O O O O O X O O O O X O O O O O Implementieren Sie eine Java-Klasse Labyrinth, mit der für obiges Labyrinth ein Pfad von A nach B gesucht und ausgegeben wird. Verwenden Sie dazu eine Klasse Zustand mit der Methode GibNachfolger, sowie die zwei Listen NeuList und AltList zur Verwaltung von Zuständen (s.o.). Prüfen Sie bei neuen Zuständen jeweils, ob diese bereits bearbeitet (in AltList) oder auf anderem Wege erzeugt wurden (in NeuList) und vermeiden Sie Zyklen durch geeignete Maßnahmen. Findet Ihr Verfahren den kürzesten Pfad? 5 Punkte
Abzugebende Dokumente	Aufgabe 1: Kommentierter Quellcode und Protokoll der Laufzeitmessungen. Ergebnis Ihrer Überlegungen zu BucketSort. Aufgabe 2: Kommentierter Quellcode und erzeugte Ausgabe für das Beispiel. Schicken Sie bitte Ihre Dokumente - ein Exemplar je Übungsteam - als ein im Zip-Format komprimiertes Nur-Text-Attachment per Email an Ihren Übungsgruppenleiter.