Kombinatorische Optimierung / Die Berechnung kürzester Wege Die Einführung in die Kombinatorische Optimierung wird sich mit der Berechnung kürzester Wege befassen. Das prinzipielle Vorgehen des Dijkstra-Verfahrens soll erläutert und an Beispielen demonstriert werden. Ausgehend von dieser Basisversion sollen dem Verfahren verschiedene Datenstrukturen unterlegt und das daraus resultierende Laufzeitverhalten analysiert werden. Der Benutzer hat die Möglichkeit, bestehende Programme auf von ihm zu erzeugende Beispielgraphen anzuwenden bzw. eigene Programmteile oder Programmimplementierungen zu erzeugen und interaktiv an Beispielen zu testen und zu illustrieren. Die Einführung setzt sich aus vier Komponenten zusammen, die geeignet vernetzt und interaktiv bedienbar zru Verfügung gestellt werden. Das Konzept des Kursteils besteht aus einer Einführung in die Fragestellung, benötigte Begriffe der Graphentheorie, Darstellung des Grundalgorithmus (Dijkstra), formaler Beweis zur Korrektheit, Laufzeitanalyse, verschiedene Datenstrukturen, Laufzeitverhalten mit diesen Datenstrukturen, future-cost-Verfahren (A*-Verfahren), Bezug zur linearen Programmierung einem interaktiv-benutzbarem Programmeditor, der erlaubt, in Python geschriebene Programmecodes zu interpretieren. Die Programme können als Video durchlaufen, schrittweise abgearbeitet werden oder von Stopmarke zu Stopmarke laufen, die vom Benutzer gesetzt werden können. Im ersten Teil des Kurses werden vorgefertigte Programme verwendet werden. In späteren Teilen soll der Benutzer eigene Programmteile anfertigen. einem Demonstrationsfenster, in dem an Hand konkreter Beispiele die Funktionsweise und der Ablauf der Programme illustriert wird. einem Grapheneditor, der es ermöglicht, Graphen selbst zu erzeugen bzw. zu verändern. Stand des Projekts