Im kommenden Sommersemester werde ich eine Vorlesung zum Thema
Statistische Mechanik und Optimierung auf zufälligen Strukturen
anbieten. Hinter dem Titel verbirgt sich die folgende (normalerweise aus der Praxis stammende) Kritik an der traditionellen Analyse von Optimierungsalgorithmen:
Was schert mich, dass man mit viel Mühe eine Instanz konstruieren kann, bei der mein Algorithmus schlecht funktioniert, wenn man solche Instanzen suchen muss wie die Nadel im Heuhaufen?
In der Vorlesung sollen Ansätze aus der Statistischen Mechanik benutzt werden, um Algorithmen zu konstruieren, die (beweisbar) nur bei “Ausnahmen” schlecht funktionieren.
Statistische Mechanik ist (im Grunde) ein Teilgebiet der Wahrscheinlichkeitstheorie, und zwar netterweise, aufgrund der Ursprünge in der Physik, ein sehr intuitives. Physikkenntnisse brauchen Sie für die Vorlesung aber nicht.
Der Inhalt der Vorlesung zerfällt auf natürliche Art in drei Zeitabschnitte.
- Einführung: einige einfache Algorithmen auf zufälligen Strukturen
- Statistische Mechanik für Nicht-Physiker
- Aus der Statistischen Mechanik abgeleitete Algorithmen
Voraussetzungen
- Einführung in die Wahrscheinlichkeitstheorie und Statistik
- Kombinatorische Optimierung
Weitere organisatorische und inhaltliche Informationen
werde ich als Kommentare zu diesem Blogpost schreiben (s.u. bei Responses). Interessenten und Teilnehmer sind gleichfalls eingeladen, sich in den Kommentaren mit Fragen und Kritik zu Wort zu melden!!
Parallel zur Vorlesung soll ein ausfürliches Skript entstehen.
