| Kommentar |
Heuristische Suchalgorithmen werden in der Künstlichen Intelligenz, in Planungssystemen und in der kombinatorischen Optimierung eingesetzt, um Zustandsgraphen nach kostenoptimalen Lösungen zu durchsuchen. Die Effizienz des Suchprozesses hängt ganz wesentlich von der Güte der verwendeten Heuristik ab. Aktuelle Algorithmen verwenden als Heuristik sogenannte Pattern-Datenbanken (pattern databases), die komprimiert im Hauptspeicher liegen und über schnelle Indizierungsfunktionen adressiert werden. Am Beispiel von Einpersonen-Puzzles (n-Puzzle, Rubics Cube) und Sequenz-Alignmentverfahren der Bioinformatik wollen wir effiziente, parallele Algorithmen für die Erstellung großer Pattern-Datenbanken programmieren, die dann ihrerseits für die Lösungssuche in komplexen Problemen angewandt werden. Dabei kommen die Programmiersprachen C, C++ und Assembler sowie thread-parallele Methoden (OpenMP) zum Einsatz. Zur Entwicklung und Erprobung stehen hochparallele Cluster-Systeme mit großem Hauptspeicher und breiten Vektoreinheiten zur Verfügung.
Die Studierenden sollten Programmiererfahrung (möglichst C, C++) sowie Grundkenntnisse in Systemarchitektur mitbringen. Nach einer Einführung durch den Veranstalter halten die Studierenden Kurzvorträge zu ausgewählten Suchalgorithmen und Pattern-Datenbanken. Diese werden in Kleingruppen programmiert, getestet und optimiert und die Ergebnisse in einem Abschlussvortrag vorgestellt. |
