Arbeitsgruppe Algorithmen und Komplexität

Projektgruppe Operations Research

(Bitte den Inhalt anpassen)

Inhalt

Optimierungsprobleme sind ein spannendes Thema. Einerseits treten sie in sehr vielen Bereichen des täglichen Lebens auf, wie in der Wirtschaft, andererseits spielen sie in der theoretischen Informatik eine große Rolle.
Viele Optimierungsprobleme sind NP-vollständig: Man weiß bis heute nicht, ob man effizient (d.h. schnell) eine optimale Lösung finden kann. Deswegen betrachtet man Approximationsalgorithmen, die effizient eine angenäherte Lösung mit garantierter Genauigkeit finden können.

Dieses Bachelor-Abschlussprojekt bietet Themen aus Theorie und Praxis an. Eine Übersicht finden Sie auf unserer zugehörigen Themenseite.

 

Betreuer

Prof. Klaus Jansen, Felix Land

Ansprechpartner

Felix Land>

 

Theoretische Fragestellungen

sind die Entwicklung von approximativen und Online-Algorithmen sowie untere Schranken für die Laufzeit. Betrachtete Probleme sind u.a.

  •  2D- und 3D-Packungen
  • Bin Packing
  • Scheduling von Jobs auf identischen oder heterogenen Maschinen
  • Knapsack-Probleme
  • Lineare Optimierung sowie ganzzahlige Optimierung


Es sind Themen mit direktem Bezug zu unseren DFG-Forschungsprojekten möglich.

 

Praktische Fragestellungen

sind Entwicklung und Implementierung von Algorithmen für Probleme wie

  • Fluglinienplanung (Fleet Assignment)
  • Touren- und Routenplanung
  • Robuste Algorithmen zur Bahnoptimierung
  • Sportliga-Optimierung
  • Stundenplan-Optimierung
  • Algorithmische Bioinformatik


Es sind Themen in Kooperation mit Firmen wie Fast Lean Smart (FLS), German Seed Aliance, Hell Gravure Systems, TimberTec, Lufthansa oder IBM  Zürich möglich.

 

Voraussetzungen

  • Interesse an Optimierungsproblemen
  • Besuch der Vorlesungen Algorithmen und Datenstrukturen

 

Gebotenes

  • Ein Einblick in theoretische und praktische Optimierungsprobleme
  • Je nach Schwerpunkt Erfahrungen in der Implementierung von Algorithmen oder ein erster Einblick in die universitäre Forschung
  • Bei erfolgreicher Teilnahme 15 ECTS-Credits
  • Abschluss des Bachelor-Studiums mit der Bachelorarbeit

 

Prüfungsleistung

Schriftliche Ausarbeitung (Bachelorarbeit) und institutsöffentlicher Vortrag

 

 

Weitere Informationen zur Operations Research im Univis