Statistische Mechanik kombinatorischer Optimierungsprobleme (53199)
Die Vorlesung und das zugehörige Seminar werden
im Wintersemester 2002/2003 von
A.K. Hartmann und M. Weigt angeboten. Sie richten sich an
Studenten/-innen ab dem
7. Semester.
Die Vorlesung findet Di. 11.15-12.45 im Seminarraum der IV Physik,
(MN 68) statt. Dazu wird auch ein Seminar mit
Möglichkeit des Scheinerwerbs angeboten (Ort/Zeit: nach Vereinbarung).
Inhalt:
Kombinatorische Optimierungsprobleme, wie sie z. B. bei der Erstellung
von Reiserouten, Stundenplänen oder beim Design von Chips auftreten,
benötigen zu ihrer numerischen Lösung oft sehr lange
Computerlaufzeiten. Die Analyse der Optimierungsaufgaben und die
Entwicklung guter Algorithmen gehören daher zu den zentralen Fragen
der Komplexitätstheorie der Informatik. In den letzten Jahren sind
hierbei Phänomene in den Mittelpunkt des Interesses gerückt, die stark
an Phasenübergänge erinnern - und sich daher am besten mit Methoden
der statistischen Physik verstehen lassen. Die Vorlesung führt in
dieses stark wachsende interdisziplinäre Forschungsgebiet ein. Im
Rahmen des zugehörigen Seminars werden Sie mit Hilfe von
Originalarbeiten an aktuelle Forschungsergebnisse herangeführt. Die
hier erworbenen Kenntnisse können Ihnen sowohl in der eigenen
Forschung als auch bei Anwendungen in der Industrie von großem Nutzen
sein.
Vorausgesetzt werden Kenntnisse in der statistischen Physik.
Themen der Vorlesung:
- Komplexitätstheorie
- Algorithmen
- Graphentheorie, Zufallsgraphen, Perkolation
- Phasenübergänge
- einfache Probleme, schnelle Algorithmen
- Knotenüberdeckungsproblem
- Erfüllbarkeitsproblem
In dem Seminar kann ein Schein erworben werden, wie er in der
Diplomprüfungsordnung verlangt wird.
Eine
Themen und Literaturliste ist bereitgestellt.
Auf besonderen Wunsch ist es auch möglich, Algorithmen am
Computer selbst zu erproben bzw. zu programmieren. Dazu stehen
umfangreiche Programmbibliotheken LEDA und
Numerical Recipes (jeweils nur lokal) zur Verfügung.
Dieser Teil ist aber freiwillig und nicht
zum Erwerb eines Scheins notwendig.
Voraussetzungen für den Erwerb eines Scheins (falls gewünscht):
- Regelmäßige Teilnahme an der Veranstaltung.
- Halten eines Vortrages von 60 Minuten Dauer.
- Erstellung einer schriftlichen Ausarbeitung (angemessene
Länge frei wählbar).
Für den Vortrag sollte gelten (sofern zutreffend):
- Er sollte sehr gut verständlich sein. Es geht nicht darum
darzustellen, daß man unglaublich schwierige Dinge
versteht, sondern darum, diese Punkte dem Zuhöhrer so
darzustellen, daß er etwas lernt.
- Zunächst wird das untersuchte Modell erläutert.
- Dann wird die Transformation des Modells auf das
mathematische Objekt, das optimiert wird, erklärt.
- Der Algorithmus wird ausführlich erläutert.
Eine Beispielausführung (Tafel) mit einem kleinen System
wäre angebracht.
- Zum Abschluß werden die wichtigsten Ergebnisse kurz
vorgestellt.
Zu den Homepages von
Alexander Hartmann und
Martin Weigt
Zeitplan:
hartmann@theorie.physik.uni-goettingen.de
weigt@theorie.physik.uni-goettingen.de
Last modified: Mon Oct 21 11:27:03 CEST 2002