Uni-Logo

Programmierpraktikum Optimierung


Inhalt:

Es wird zwei (disjunkte) Untergruppen zu den folgenden Themen geben:

  • Meisterschaftsproblem (Sportligen)

    Gegeben: eine aktuelle Tabelle einer Liga sowie ein Spielplan der restlichen Spiele.
    Frage: Wer kann noch Meister werden?
    Je nach Punktevergabe in der Liga ist dieses Problem effizient exakt lösbar bzw. NP-vollständig.
    Es sollen verschiedene Verfahren (exakt und heuristisch) implementiert und getestet werden.

  • Verschnitt-/Packprobleme

    Gegeben: zweidimensionale rechteckige Objekte, die aus größeren Platten herausgeschnitten werden sollen.
    Aufgabe: Bestimme Schnittmuster, so dass der Verschnitt minimiert wird.
    Es sollen verschiedene heuristische Verfahren implementiert und an Praxisdaten getestet werden.


Termine:

Vorbesprechung: Donnerstag, 07.01.16, 69/E15

3-wöchiges Blockpraktikum in der VL-freien Zeit:

  • Freitag, 12.02.16 (9-12 Uhr, Kurzvorträge)
  • Montag, 15.02.16 bis Freitag, 19.02.16 (9-17 Uhr)
  • Montag, 07.03.16 bis Freitag, 18.03.16 (9-17 Uhr)

    Räume 93/E11, E09


  • Literatur

    • Bernholt, T., Gülich, A., Hofmeister, T., Schmitt, N., Wegener, I. [2002]: Komplexitätstheorie, effiziente Algorithmen und die Bundesliga. Informatik-Spektrum, 25(6), 488-502.
    • Bernholt, T., Gülich, A. [2000]: Anwendung von Komplexitätstheorie und Effizienten Algorithmen auf die Fußballbundesliga. Diplomarbeit, Universität Dortmund.
    • Adler, I., Erera, A. L., Hochbaum, D. S., Olinick, E. V. [2002]: Baseball, optimization, and the world wide web. Interfaces, 32(2), 12-22.
    • Ribeiro, C.C., Urrutia, S. [2005]: An application of integer programming to playoff elimination in football championships. International Transactions in Operational Research, 12(4), 375-386.
    • Wäscher, G., Haußner, H., Schumann, H. [2007]: An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109-1130.
    • Berkey, J.O., Wang, P. Y. [1987]: Two-dimensional finite bin-packing algorithms. Journal of the Operational Research Society 38(5), 423-429.
    • Lodi, A., Martello, S., Vigo, D. [2002]: Recent advances on two-dimensional bin packing problems. Discrete Applied Mathematics 123(1), 379-396.
    • Lodi, A., Martello, S., Vigo, D. [1999]: Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing 11(4), 345-357.
    • Instanzen Two-Dimensional Bin Packing Problems

    Teilnahme

    Teilnehmen können alle interessierten Bachelor-Studierenden aus den Studiengängen Informatik, Mathematik, Angewandte Systemwissenschaft und Cognitive Science. Die Veranstaltung zählt als Programmierpraktikum (P4 / 6 LP).


    Vorkenntnisse

    Von den Teilnehmern werden erwartet:

    • Programmierkenntnisse in Java (wie sie z.B. durch Informatik A und B vermittelt werden)
    • Grundlagen von Algorithmen und Datenstrukturen

    Kenntnisse aus dem Bereich der kombinatorischen Optimierung sind nützlich, aber nicht unbedingt Voraussetzung für eine Teilnahme.


    Schein

    Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmäßige aktive Teilnahme am Praktikum sowie die Präsentation von Kurzvorträgen im Rahmen des Praktikums.