Administrative Hinweise

Das Praktikum kann als A5.3.5 für Bachelorstudenten, Masterpraktikum für Masterstudenten und 4-stündige vertiefende Übung (Fortgeschrittenenpraktikum) für Diplomstudenten belegt werden. Bitte tragen Sie sich dementsprechend in der StudiDB ein. Ohne Eintragung in der StudiDB können keine Scheine ausgestellt werden!

Nächstes Treffen: Dienstag, der 10. November. Danach: Dienstag, der 1. Dezember.

Weitere Materialien

Die XML-Schema-Datei für die Eingabeinstanzen
Eine Beispieldatei
Ein Instanzgenerator

UniVIS-Eintrag

Technische Fakultät

Bachelorstudiengang Informatik

Fortgeschrittenenpraktika-Projekte A5.3

Das Fortgeschrittenenpraktikum A5.3 muss nicht mehr verpflichtend absolviert werden. Alternativ können Wahlpflichmodule im Rahmen von 8 ECTS-Punkten absolviert werden.
Die ECTS-Punkte werden nur dann vergeben, wenn das komplette Modul erfolgreich abgeschlossen wurde.

A5.3.5: Fortgeschrittenenpraktikum - Effiziente Algorithmen (080250)

Dozentinnen/Dozenten:: Klaus Jansen, Ulrich Michael Schwarz
Angaben:: Übung, 4 SWS, ECTS: 8, Modul: A5.3.5
Termine:: Di, 10:00 - 12:00, CAP4 - R.1001
Falls gewünscht, kann der Termin während der Vorbesprechung noch abgeändert werden.
vom 26.10.2009 bis zum 10.2.2010
Voraussetzungen / Organisatorisches:: Interessierte können sich auch direkt bei Prof. Jansen, kj@informatik.uni-kiel.de, melden. Der Besuch der Vorlesung "Effiziente Algorithmen" wird empfohlen.
Inhalt:: Konkret soll das effiziente Polynomzeit-Approximationsschema (EPTAS) von Jansen (SODA '09 und Verbesserungen) für das Multiple Knapsack Problem implementiert werden. Bei diesem Problem sollen m Rucksäcke unterschiedlicher Größen so mit einer Auswahl aus n Items gefüllt werden, dass der Gesamtprofit maximiert wird. Da dies nicht in polynomieller Zeit exakt möglich ist (außer P=NP), liefert der Algorithmus eine gute Näherungslösung mit Wert (1-epsilon)OPT in Zeit f(epsilon)poly(n,m).