Projekt Algorithm Engineering

• Grundlagen der Stochastik

Für schwierige Probleme werden häufig randomisierte Verfahren eingesetzt deren Laufzeit als Zufallsvariable beschrieben werden kann. In vielen Fällen ist nur der Erwartungswert der Laufzeit analytisch bekannt, die konkrete Laufzeitverteilung ist dagegen meistens unbekannt. Wäre die Laufzeitverteilung bekannt, dann ließen sich einige Parameter für noch nicht gelöste Instanzen anpassen. Dadurch lässt sich insgesamt eine bessere Performance erzielen.

Die Themen stammen aus dem Bereich des Constraint Solving und des Satisfiability Problems. Es sollen unterschiedliche local-search und backtracking Algorithmen untersucht werden.

Selbstverständlich können auch eigene Themen vorgeschlagen werden.