TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Fakultät | Department Informatik
Informatikzentrum

Algorithmikpraktikum: Solving NP-hard Problems in Practice

Semester
StudiengangBachelor Informatik
IBR GruppeALG (Prof. Fekete)
ArtVorlesung/Übung
Dozent
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter

+49 531 3913111
Raum 335
Assistenten
PhotoDr. Phillip Keldenich
Wissenschaftlicher Mitarbeiter

+49 531 3913112
Raum 318
PhotoDominik Krupke
Wissenschaftlicher Mitarbeiter

+49 531 3913116
Raum 332
LP5
SWS0+3
Beginn Wird im einzelnen mit den Gruppen abgesprochen.
Voraussetzungen Zwingend erforderlich sind der souveräne Umgang mit dem Stoff aus Algorithmen und Datenstrukturen, gute Programmierkenntnisse (es stehen mehrere Sprachen zur Auswahl, u.a. Python, Java und C++), sowie Teamfähigkeit. Hilfreich, aber nicht zwingend erforderlich sind Wahlpflichtveranstaltungen der Algorithmik, wie zum Beispiel Algorithmen und Datenstrukturen 2, Netzwerkalgorithmen, Einführung in Algorithm Engineering oder Mathematische Methoden der Algorithmik.
SpracheDeutsch
AnmeldungIndividuelle Absprache per E-Mail
Inhalt

In diesem Praktikum geht es darum, bestimmte Instanzen eines NP-schweren Problems optimal zu lösen (es sind grundsätzlich verschiedene Probleme denkbar). Das geschieht mit Hilfe mächtiger Tools, guter Software und vor allem durch die Kombination von Theorie und Praxis. Insbesondere werden vorhandene Integer Programming Solver wie IBM CPLEX oder Gurobi benutzt. Dies bildet den Kern des Praktikums; darüber hinaus gibt es verschiedene Vertiefungsmöglichkeiten:

  • Den im Praktikum entwickelten Solver so weit wie möglich optimieren, sodass größere und schwerere Instanzen gelöst werden können. In Experimenten auf verschiedenen Instanzen evaluieren, wie sich Optimierungen auf Laufzeit und Speicherverbrauch auswirken.
  • Besonders schwere oder interessante Instanzen erzeugen und die Performance des Solvers darauf evaluieren.
  • Heuristische Ansätze entwickeln, die bei Instanzen zum Einsatz kommen können, die nicht mehr exakt gelöst werden können. Experimente durchführen, um diese heuristischen Ansätze bezüglich verschiedener Kriterien zu vergleichen.
  • Visualisierung von Instanzen, Lösungen und experimentellen Ergebnissen.
Literatur/Links

aktualisiert am 20.03.2021, 10:36 von Dr. Phillip Keldenich
printemailtop