Lehrstuhl für Wirtschaftsmathematik

Mathematisches Institut, Fakultät für Mathematik, Physik und Informatik
Lehrstuhlinhaber: Prof. Dr. Jörg Rambau

VL: Approximations-Algorithmen

Approximationsalgorithmen

Quelle:Medizinische Universität Lübeck.

Die Ankündigung zu dieser Vorlesung finden sie hier. Eine Liste der behandelten Themen können sie hier finden.

Vorlesung

Dozent: PD Dr. Sascha Kurz
Zeit und Ort: Vorlesung: 2 SWS, Mo 10-12, S 78
  Übung: 1 SWS, Mo 12-13, S 78

Inhalt

Für viele kombinatorische Optimierungsprobleme hat sich herausgestellt, daß sie (gehen wir von P!=NP aus) vermutlich nicht durch schnelle exakte Algorithmen gelöst werden können, weshalb man sich mit Näherungslösungen zufrieden geben muß. Ein Algorithmus besitzt für ein Problem eine konstante Gütegarantie c, wenn zu jeder Eingabe in Polynomialzeit eine Lösung berechnet werden kann, deren Zielfunktionswert höchstens c Mal so viel (bei Minimierungsproblemen) wie der einer Optimallösung beträgt.

In der Vorlesung werden Approximationsalgorithmen vorgestellt, die für eine Reihe populärer Optimierungsprobleme beweisbar gute Lösungen in vertretbarer Zeit berechnen. Behandelt werden u.a. die Themen Primal-Dual-Methode, LP-Rounding und die Optimierungsprobleme Traveling Salesman, Steinerbaum, Bin-Packing, Facility Location und K-Median.

Eine anschliessende Fortführung des Themenbereiches in Form einer Diplomarbeit ist möglich.

Für Wirtschaftsmathematiker und andere angewandte Mathematiker ist die mathematischen Modellierung von praktischen Optimierungsproblemen mit Hilfe von Graphen und den zugehörigen Algorithmen zur Lösung der Probleme ein wichtiges Rüstzeug für das spätere Arbeitsfeld. Für Informatiker ist die Entwicklung von Algorithmen zur Lösung praktischer Probleme mit dem Computer ein zentraler Bestandteil ihrer Ausbildung.

Verwendbarkeit Masterstudiengänge Informatik/Mathematik

Modultyp: Alternative für Modul INF310 /Spezialisierungsmodul B1
Leistungspunkte: 4
Teilprüfung/Leistungsnachweis: 50 % der Hausaufgabenpunkte sowie mündliche Prüfung

Verwendbarkeit für Diplomstudiengänge

Veranstaltungstyp: 2 SWS Wahlpflichtvorlesung + 1 SWS Übung
Scheinkriterien: 50 % der Hausaufgabenpunkte sowie mündliche Prüfung

Zielgruppe

Die Veranstaltung richtet sich an Studierende der Informatik bzw. Mathematik insb. der Wirtschaftsmathematik ab dem 4. Semester und weitere Interessierte. Grundlegende Kenntnisse im Bereich Algorithmen und Linearer Optimierung sind hilfreich.

Literatur

Scheinvoraussetzung

Nach Vereinbarung.

e-Learning

Zu unseren Veranstaltungen finden Sie zusätzliche Angebote auf dem fakultätsübergreifenden e-Learning-Server eLearning.uni-bayreuth.de der Universität Bayreuth.

Ansprechpartner

Dozent PD Dr. Sascha Kurz FAN D.1.31 0921 / 55-7353 Sascha.Kurzuni-bayreuth.de Sprechstunde: n. V.
Sekretariat Leni Rostock FAN D.1.30 0921 / 55-7351 Leni.Rostockuni-bayreuth.de Öffnungszeiten: 9-12 Uhr

© 2005–2014 Lehrstuhl Wirtschaftsmathematik — Imprint
Webmaster Wirtschaftsmathematik
Letztes Update am: 29.10.2009

druckfreundliche Ausgabe der Seite