DE EN
Forschungsinstitut für
Diskrete Mathematik
Menü

Programmierpraktikum Diskrete Optimierung (Modul P2C1)

← Semesterübersicht

Sommersemester 2018

Thema: Darstellungen von Rechteckpackungen

Rechteck-Packungsprobleme haben viele wichtige Anwendungen, insbesondere beim Entwurf von höchstintegrierten Logikchips. Dabei verfolgt man unterschiedliche Optimierungsziele (z.B. Minimierung des Flächenverbrauchs oder Optimierung von Verbindungslängen zwischen den Rechtecken). Die meisten Packungsprobleme erweisen sich dabei als NP-schwer. Um dennoch optimale Packungen zu berechnen, kann man sich enumerativer Methoden bedienen. Dafür muss man Anordnungen von Rechtecken kompakt kodieren können, und man muss in der Lage sein, aus einer Kodierung auf effiziente Art eine zugehörige Rechteckpackung zu bestimmen. In diesem Praktikum sollen verschiedene Repräsentierungen von Rechteckanordnungen implementiert und zur Berechnung optimaler Packungen verwendet werden.

Termine des Abschlusspräsentationen:

Freitag, 20. Juli:
  • 14:15: Alexander Holz
  • 14:30: Josefine Foos
  • 14:45: Lars Friederichs
Dienstag, 24. Juli:
  • 16:15: Tobias Bork
  • 16:30: Nicholas Schwab und Lukas Kempf
  • 17:00: Philipp Holzmann
  • 17:15: Pause
  • 17:30: Jan Polster
  • 17:45: Kuangda Konrad Zou
  • 18:00: Eva Gebertz
Hier kann eine genaue Beschreibung der einzelnen Aufgaben heruntergeladen werden, und hier kann eine Liste mit den Teilnehmern und Betreuern heruntergeladen werden.

Kleine Testinstanzen:

Instanzen mit gegebener Platzierung (für die Eintiegsaufgabe): Die angegebenen Platzierungen sind alle überlappungsfrei (man konstruiert sich leicht Instanzen mit Überlappungen daraus).

Packungsinstanzen:

Bilder von Packungen der Pack-Instanzen 1 bis 9 finden sich hier.
Allgemeine Hinweise zum Programmieren.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner