Geplante Lehrveranstaltungen

Hier können Sie sich einen Überblick über geplante Lehrveranstaltungen schaffen. Änderungen sind jedoch noch möglich.

Module im SoSe 2020

Algorithmen für schwere Probleme (Master)

Dieses Modul befasst sich mit schweren Problemen, für die es vermutlich keine effizienten Algorithmen gibt, und stellt unter anderem folgende Lösungsansätze für solche Probleme vor.

  • Pseudopolynomielle Algorithmen
  • Algorithmen auf speziellen Graphen
  • Parametrisierte Algorithmen
  • Exakte Exponentialzeit Algorithmen

 

Master-Seminar über NP-schwere Probleme

Die Härte mancher Probleme gibt Anlass dazu, kreative Methoden zu finden um sich der Lösung eines Problems zu nähern. Man kann beispielsweise Teilprobleme lösen oder das Problem auf eingeschränkte Klassen untersuchen, um Approximationsalgorithmen bzw. parametrisierte Algorithmen zu finden oder das Problem unter einer bestimmten Einschränkung effizient zu lösen. In diesem Modul werden verschiedene dieser Methoden untersucht. Ziel dieses Moduls ist es, den Studierenden Einblicke in einige wichtige oder aktuelle Forschungsthemen, Resultate und Methoden aus dem Gebiet der NP-schweren Probleme zu geben.

 

Module im WiSe 2020/21

Knapsack Problems (Bachelor)

Dieses Modul befasst sich mit verschiedenen Varianten des Rucksackproblems und stellt verschiedene Lösungsmethoden für diese Probleme vor.

 

Master-Seminar über Graphparameter für gerichtete Graphen

In diesem Seminar beschäftigen wir uns mit der Analyse von Graphparametern für gerichtete Graphen. Hierzu betrachten wir gerichtete Formen der Cliquenweite, NLC-Weite und Rangweite sowie verschiedene Ansätze für eine gerichtete Form der Baumweite. Es sollen Beziehungen zwischen diesen Parametern und die Weite spezieller Graphklassen bzgl. dieser Parameter vorgestellt werden.

 

Module im SoSe 2021

Approximative Algorithmen (Bachelor)

Dieses Modul befasst sich mit den folgenden schweren Optimierungsproblemen, für die es vermutlich keine effizienten Algorithmen gibt, und stellt verschiedene Ansätze zum Finden von Näherungslösungen für diese Probleme vor.

  • Metric Traveling Salesman
  • Job Scheduling
  • Knapsack
  • Bin Packing
  • Steiner Tree
  • Weighted Vertex Cover

 

Master-Seminar über Algorithmen für perfekte Graphen

Perfekte Graphen sind eine der am besten untersuchten Graphenklassen. Zahlreiche Probleme lassen sich auf perfekten Graphen einfacher oder schneller lösen als auf allgemeinen Graphen. In diesem Seminar sollen verschiedene Typen perfekter Graphen, z.B. Bäume, bipartite Graphen, Intervallgraphen, Vergleichbarkeitsgraphen, Thresholdgraphen und Chordale Graphen vorgestellt und einige klassische Probleme auf diesen betrachtet werden.

Verantwortlich für den Inhalt: E-Mail sendenWE Informatik