Attention: For the time being the tutorial will be held online and not at FU. Please follow the link below to access the Webex session,

Optimization 1 Tutorial Session
Hosted by Ricardo Euler

https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=m9a8e8814562709f96d842e0e4c707fbe
Friday, Dec 3, 2021 4:15 pm | 1 hour 30 minutes | (UTC+01:00) Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna
Occurs every Friday effective 12/3/2021 until 2/11/2022 from 4:15 PM to 5:45 PM, (UTC+01:00) Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna
Meeting number: 2734 932 5642
Password: Y6h3WJpBEq2

Join by video system
Dial 27349325642@fu-berlin.webex.com
You can also dial 62.109.219.4 and enter your meeting number.

Join by phone
+49-619-6781-9736 Germany Toll
+49-89-95467578 Germany Toll 2
Access code: 273 493 25642

The first tutorial will be held this Friday, 22.10.21 at 4:30 p.m. to accommodate students that want to go to the exam review session for Discrete Maths I at 4 p.m.

Please check out the Info Sheet. It contains all relevant information about the format of the lectures, tutorials and exercises.

Diese Vorlesung startet den Optimierungszweig der Diskreten Mathematik. Sie behandelt die Algorithmische Graphentheorie und die Lineare Optimierung.

Inhalt

1. Komplexität: Komplexitätsmaße, Laufzeit von Algorithmen, die Klassen P und NP, NP-Vollständigkeit
2. Matroide und Unabhängigkeitssysteme: Unabhängigkeitssysteme, Matroide, Bäume, Wälder, Orakel, Optimierung über Unabhängigkeitssystemen
3. Kürzeste Wege: Nichtnegative Gewichte, allgemeine Gewichte, all pairs
4. Netzwerflüsse: Das Max-Flow-Min-Cut Theorem, Augmentierende Wege, Minimalkostenflüsse, Transport- und Zuordnungsprobleme
5. Polyeder: Seitenflächen, Dimensionsformel, Projektionen von Polyedern, Transformation, Polarität, Darstellungssätze.
6. Grundlagen der Linearen Optimierung: Farkas Lemma, Dualitätssatz.
7. Simplexalgorithmus: Basis, Degeneration, Basistausch, revidierter Simplexalgorithmus, Schranken, dualer Simplexalgorithmus, Postoptimierung, Numerik.
8. Innere Punkte und Ellipsoidmethode: Grundlagen

Zielgruppe

Diese Veranstaltung richtet sich an Studierende der Mathematik mit Vorkenntnissen in Diskreter Mathematik, Linearer Algebra und Analysis. Einige Übungsaufgaben erfordern den Einsatz eines Computers.