Hintergrund

In vielen Bereichen der Informatik ist Effizienz ein entscheidender Faktor bei der Beurteilung von Software. Das heißt, neben der Frage, ob ein Programm korrekt arbeitet, kann es eine wesentliche Rolle spielen, ob es schnell genug arbeitet. Insbesondere bei großen Problemen entscheidet die Effizienz des Programmes darüber, ob überhaupt eine Lösung gefunden wird.

Inhalt

In dem Fachpraktikum werden grundlegende Techniken und Prinzipien des effizienten Programmierens geübt. Der Schwerpunkt liegt auf der Entwicklung und besonders der Implementierung von effizienten Datenstrukturen und Algorithmen. Die vorgesehenen Themen beinhalten Datenstrukturen (z.B. zur Darstellung von Mengen) und Algorithmen zu den Bereichen Parsing, String Matching, Sortieren, Dynamisches Programmieren und Suche in Graphen.

Ablauf

Die Teilnehmer bekommen ein wöchentlich zu bearbeitendes Aufgabenblatt mit einer oder mehreren Programmieraufgaben. Diese Aufgaben behandeln entweder einzelne möglichst anschauliche und motivierende Probleme, wie z.B. Spiele oder Puzzles, oder beziehen sich auf ein größeres Programmierprojekt, das sich durch das gesamte Praktikum hindurchzieht. Dieses Projekt ist die Implementierung eines Verifikations-Werkzeugs, das z.B. zur automatischen Fehlersuche eingesetzt werden kann. Zu jeder Programmieraufgabe werden Eingabedaten zur Verfügung gestellt, auf die das von den Teilnehmern entwickelte Programm angewandt werden soll. Die Problemgröße dabei ist skalierbar oder so groß, dass die Teilnehmer die Effizienz ihres Programmes ablesen können, um es u.U. zu verbessern.

Voraussetzungen

Bestandenes Vordiplom, Programmierkenntnisse in C oder Ada. Die Vorlesung Entwurf und Analyse Effizienter Algorithmen wird parallel zum Fachpraktikum im Sommersemester angeboten. Dort erworbene Kenntnisse können im Praktikum angewandt und vertieft werden.

Teilnehmerzahl: