Wahlpflicht-Praktikum im SS 2002

Effiziente Algorithmen für harte Probleme

Zeit: Montags, 14:15-15:45 Uhr
Raum: Am 15. April im Raum 2705 (Stammgelände), ab der zweiten Woche in Raum N0116 (Nordgelände)

Veranstalter: Peter Rossmanith

Hier ist ein Postsches Korrespondenzproblem, das noch auf eine Lösung wartet: (10,0) (0,001) (001,1)

Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6 Blatt 7 Blatt 8 Blatt 9

Teilnehmerzahl: Etwa 24 Studierende.

Bereich: Informatik I (alte Prüfungsordnung) - Informatik III (neue Prüfungsordnung)

Voraussetzungen: Bestandenes Vordiplom. Ein erfolgreicher Besuch der Veranstaltung Effiziente Algorithmen ist sehr wünschenswert. Ansonsten wird die Bereitschaft, sich in einzelne Themen dieser Vorlesung selbstständig einzuarbeiten, vorausgesetzt.

Scheinerwerb: Lauffähige, korrekte, schnelle Implementierungen der Algorithmen, die qualitativ hochwertige Lösungen liefern. Vorstellung einzelner Lösungen in einem kurzen Vortrag.

Inhalt

Es gibt für viele wichtige Probleme sehr effiziente Algorithmen, aber es gibt auch viele Probleme, die NP-hart sind. Diese Probleme müssen in der Praxis gelöst werden, wofür es verschiedene Ansätze gibt.

Manche dieser Probleme können wenigstens in polynomieller Zeit approximiert werden. Man erhält so eine Lösung, die zwar nicht optimal ist, aber höchstens um einen bekannten (oft sehr kleinen) Faktor vom Optimum abweicht.

In diesem Praktikum konzentrieren wir uns auf Algorithmen, die exakte Lösungen liefern. Als Techniken stehen uns Backtracking, Lokale Suche, Simulated Annealing, erschöpfende Suche und viele andere Techniken zur Verfügung.

Es wird jede Woche ein neues Problem geben, welches durch ein Programm gelöst werden soll. Testinstanzen werden zur Verfügung gestellt. Nach Abgabe werden die Programme an vor der Abgabe unbekannten Instanzen getestet. Selbstverständlich müssen die Programme korrekt sein. Aber darüberhinaus wird noch erwartet, daß sie die Aufgabe schnell (und mit vertretbarem Speicheraufwand) lösen können.

Teilweise werden Techniken im Praktikum vorgestellt, welche dann zur Lösung des Problems angewendet werden sollen. In diesem Fall muß also nur ein Algorithmus implementiert werden. Dennoch erfordern Details auch hier einige selbstständige Überlegungen. Andererseits wird es auch Aufgabenstellungen geben, für die der Lösungsweg vollständig selbstständig erarbeitet werden muß. Die TeilnehmerInnen müssen dann selbst einen geeigneten Algorithmus erfinden!

Die Algorithmen werden in C (bzw. C++) implementiert. Daher ist Erfahrung im Schreiben und Übersetzen von Programmen in C notwendig. Wir werden eventuell Softwarebibliotheken verwenden, die an den öffentlich zugänglichen Computern installiert sind und auch unter Linux (selbst!) installiert werden können.

Durchführung

In jeder Praktikumswoche findet ein zweistündiges Treffen statt, bei dem Einführungen in die Themengebiete gegeben, sowie Aufgaben und Lösungen besprochen werden. Außerdem dienen die Treffen dazu, Fragen zu beantworten.

Bei erfolgreicher Teilnahme wird ein unbenoteter Schein vergeben.

Wichtig: Das Praktikum Effiziente Algorithmen für harte Probleme zählt nach der alten Prüfungsordnung als Wahlpflichtpraktikum im Bereich Informatik I (Praktische Informatik), nach der neuen Prüfungsordnung (gültig ab November 1996) aber für den Bereich Informatik III. Studierende, die nach der neuen Prüfungsordnung DHP machen, können den Schein nicht als Praktikumsschein zu Informatik I verwenden!

Peter Rossmanith