10.10.04

DHP Prüfungsprotokoll: Mathe bei PD Brieden

Die ist mein Prüfungsprotokoll zu meiner Nebenfach Mathematik DHP Prüfung an der TUM bei PD Dr. Andreas Brieden.
Prüfungsfächer:
Lineare Optimierung - Gritzmann SS 03
Kombinatorische Optimierung - Tinhofer WS 01/02
Spieltheorie - Schlee SS 03

1) Lineare Optimierung
P: Sind Sie der Meinung, dass ihre VO Anwendungsbezug haben
A: ja
P: Dann schauen Sie mal dort auf die Karte (gefärbte Äcker um eine Stadt rum)
Modellieren Sie mal die Neuzuteilung der Felder als Optimierungsaufgabe!
A: F = Anzahl der Felder 1<=j<=F; L = Anzahl der Landwirte 1<=i<=L; b(i) Bestand des Landwirtes i; g(j) Grösse des Feldes j
Summe 1 bis F über g(i) * x(ij) = b(i) , 1<=i<=L
x(ij) element von {0,1}, x(ij) = 1, falls Feld j Landwirt i zugeteilt wird, sonst 0
Summe über alle Felder j von x(ij) <= 1

2) Lineare Optimierung
P: Ist das ein LP?
A: naja, da kam ich ins schleudern, hatte mir das bisher nur mit der linearen Zielfunktion gemerkt, die ja hier nicht gegeben ist.
ah, Nebenbedingungen müssen linear sein.
P: Sind sie das hier?
A: mh. Keine Ahnung, da nichts quadratisches wohl linear (?)
mit massiver Hilfe bin ich dann draufgekommen, dass x e {0,1} nicht linear ist. (Alles in allem grosser Kapitalfehler meinerseits)

3) Lineare Optimierung
P: Erklären Sie Simplex
A: Basislösung – Ecke zu Ecke – Basisaustausch – bis Lösung optimal
P: Laufzeit?
A: allgemein gut da polynomial, aber exponetiell Möglich
P: Beispiel?
A: Würfel von Kleen-Minty
P: Wann sind bei einem ganzzahligen Problem die Ecken auch ganzzahlig?
A: wenn die Matrix A total unimodular ist
P: Definition von unimodular und vollständig unimodular?
A: Def. erklärt
4)
P: Wie beweisst man jetzt dass die Ecken auch ganzzahlig sind?
A: Das ist ein Satz aus der VO. Beweis k.A.
dann wollte er mich unbedingt durch den Beweis führen. Naja, nicht so der Hit.

5) Kombinatorische Optimierung
P: Branch and Bound?
A: Schön erklärt am Beispiel mit Ganzzahligen Lösungen. Branch durch x1 wird beschränkt durch obere und untere Ganzzahl der Optimallösung (obere und untere Gaussklammer), danach neue Optimallösungen mit z.B. Simplex berechnen und dann x2 durch die nächsten ganzzahligen Werte beschränken, ...
P: Da war ja nur Branch, nicht Bound!
A: Bound wird da durch Simplexlösung vorgegeben. Allgemein exponentiell viele Unterscheidungen möglich.
P: Müssen die Schranken ganzzahlig sein oder egal?
A: k.A., aber eher egal. Wenn ich in etwas reinlaufe, wo zwar Schranke ok war, aber es dann keine Lösung mehr gibt, merke ich das irgendwann und kann dann in einen anderen Ast übergehen (k.A. ob das richtig ist. Er hat auf alle Fälle sehr kritisch geschaut und es mir am Schluss als dickes Minus angerechnet)

6) Kombinatorische Optimierung
P: Erklären Sie Greedy
A: (Endlich mal was schönes aus KOPT) Ich holte aus über Unabhängigkeitssysteme, allgemeines KOP (c(U) -> Max)
dann Greedy Alg. hingeschrieben, Matroid erklärt, mit lr = ur, wie das bei Matchings nicht gilt, aber bei Spannbäumen.
(Hier hätte ich noch Stunden weiter erzählen können.)

Spieltheorie kam nichts dran, aber das war ja bei einem Optimierungs PD abzusehen. Schade, da es eine interessante VO war und mal was anderes, aber egal.

ENDE

Prüfer war eigentlich ganz nett, nur die Fragen nicht so wirklich. Da merkte man, dass die jungen Karriereprofs etwas anspruchsvoller sind. ;)
Mit viel „Augenzudrücken“ gab es noch eine 3.0, Anfang war gut, dann ein paar Schnitzer und dann wieder gut bei KOP. (O-Ton)
ich selber hätte mir das folgende gegeben: 1) – 2.0; 2) - 5.0; 3) – 1.7; 4) – 5.0; 5) – 2.3; 6) – 1.0
Da ich das Führen von Beweisen nicht angemessen für eine Nebenfach Mathe DHP halte, hätte ich mir also eher was besseres gegeben. 2.7 oder so, aber ok, da ich ja auch einmal echt gepatzt hatte geht das mit der 3.0 schon in Ordnung. Danke an den Beisitzer, der sich wohl für mich ausgesprochen haben muss, da ihm meine Ausführungen zu KOP gefallen haben.

Posted by Karsten at 10.10.04 22:49 | TrackBack
Comments

Hi Karsten, Respekt-Respekt und herzlichen Glückwunsch zum passablen Ergebnis. Dann kann ich meine gedrückten Daumen wohl jetzt wieder loslassen, oder kommen noch mehr Prüfungen?

Posted by: Martin at 12.10.04 11:36
Post a comment









Remember personal info?