TU BRAUNSCHWEIG
| Carl Friedrich Gauß Faculty | Department of Computer Science
Informatikzentrum

Algorithmikpraktikum: Solving NP-hard Problems in Practice

Semester
ProgrammeBachelor Informatik
IBR GroupALG (Prof. Fekete)
TypeVorlesung/Übung
Lecturer
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Room 335
Assistants
PhotoPhillip Keldenich
Wissenschaftlicher Mitarbeiter
keldenich[[at]]ibr.cs.tu-bs.de
+49 531 3913112
Room 318
PhotoDominik Krupke
Wissenschaftlicher Mitarbeiter
krupke[[at]]ibr.cs.tu-bs.de
+49 531 3913116
Room 332
Credits5
Hours0+3
Start Wird im einzelnen mit den Gruppen abgesprochen.
Prerequisites 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.
LanguageGerman
RegistrationPlease contact us via email
Content

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.
References

last changed 2020-10-05, 13:16 by Phillip Keldenich
printemailtop