| Logik in der
Informatik Prof. Dr. Martin Grohe |
 Institut für Informatik |
An dieser Stelle finden Sie im Laufe der Vorlesung aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt.
Inhalt: Die
Optimierung beschäftigt sich mit der Findung der besten
Lösung(en)
eines Problems. Die LO untersucht Probleme, bei denen die Gesamtheit
aller Lösungen
durch lineare (Un-)Gleichungen und das Ziel als eine bzw. mehrere
lineare Funktionen gegeben sind.
Angewand in technischen, betriebs- und volkswirtschaftlichen
Zusammenhängen, dient die
bereits in der Planung eingesetzte Optimierung dazu, knappe Ressourcen
so effektiv wie möglich
zu verwenden bzw. ein gewünschtes Ergebnis mit möglichst
geringem Ressourcenverbrauch zu erreichen.
In dieser Vorlesung werden wir die klassischen Lösungsverfahren
kennenlernen: Simplexmethode, duale
Simplexmethode, Methode der Potentiale zur Lösung der klassischen
Transportaufgabe, sowie die
Grundidee des polynomialen Algorithmus von Chatchijan der
eingeschriebenen Ellipsoide. Die
entwickelten Verfahren werden wir auch zur Lösung von
1-parametrischen LO-Aufgaben, verschiedenen
Transportaufgaben und zur Lösung von Aufgaben aus der Spieltheorie
anwenden.
Das Skript zur Vorlesung: als ps-File bzw. als pdf-File.
Ergänzend zu den Vorlesungen finden 2-stündige Übungen statt.
Es wird regelmäßig Übungsaufgaben geben, deren erfolgreiche Bearbeitung (mindestens 50% der Punkte) Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist.
Hausaufgabenblatt 1: als ps-File bzw. als pdf-File
Hausaufgabenblatt 2: als ps-File bzw. als pdf-File
Zu Beginn der Semesterferien finden mündliche Prüfungen statt. Für die Zulassung zur Prüfung müssen mindestens 50% der Punkte in den Übungaufgaben erworben werden.
| [PZ] |
Popova-Zeugmann, Skript
zur Vorlesung, HUB, 2004 |
| [F] |
R. Fletcher, Practical
Methods of Optimisation, John Wiley & Sons-Verlag, 2te
Auflage, 1995 |
| [M] |
P. Morris, Introduction
to Game Theory, Springer-Verlag, 1994 |