Modulcode:	BA6.6
Englische Bezeichnung:	Efficient Algorithms
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (SS09 SS10 WS10/11 SS11 SS12)
Präsenzzeiten:	6Ü
ECTS:	16
Workload:	480 Std.
Dauer:	ein Semester
Modulkategorien:	BA6 (Sonstige)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

In diesem Projektmodul werden approximative Algorithmen zur Lösung klassischer Optimierungsprobleme der Informatik behandelt. Hauptaugenmerk liegt hierbei einerseits auf den Designtechniken, andererseits auf Fragen der Effizienz bei der Implementierung.

Lernziele:

Die Studenten erlernen, Algorithmen hinsichtlich Laufzeit und Güte zu analysieren, die verwendeten Verfahrensweisen zu erkennen, zu verbessern und auf andere Problemstellungen zu übertragen.

Lehrinhalte:

Bin Packing, das Knapsack-Problem und Scheduling sind klassische Probleme der Informatik, die auch bei vielen Optimierungsproblemen in der echten Welt eine Rolle spielen. Sie gehören zu den NP-vollständigen Problemen; für diese ist bis heute unbekannt, ob effiziente (d.h. schnelle) Algorithmen existieren, die immer eine optimale Lösung finden. Es sind aber Approximationsalgorithmen bekannt, die die Probleme effizient und näherungsweise, also mit einer garantierte Genauigkeit, lösen. Manche Algorithmen (Approximationsschemata genannt) können sogar Lösungen beliebig nahe am Optimum finden; dabei nimmt die Laufzeit natürlich mit der Genauigkeit zu, ist aber immer noch effizient.

Im Rahmen des Bachelorprojekts soll ein Approximationsschema für Bin Packing, Knapsack oder Scheduling implementiert werden. Außerdem bietet sich die Möglichkeit, erste Erfahrungen im Bereich der approximativen Algorithmen zu sammeln.

Weitere Voraussetzungen:

Das Projektmodul richtet sich an Bachelorstudenten der Informatik im 5. und 6. Semester. Voraussetzungen für die Teilnahme sind

• Programmierkenntnisse in Java oder C
• Interesse an Optimierungsproblemen
• Besuch der Vorlesung Algorithmen und Datenstrukturen

Prüfungsleistung:

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

Verweise:

Kommentar: