Nachhilfe Informatik (Polynomielle Kombinatorische Optimierungsalgorithmen)

[alex1515]

Hallo zusammen,

meine Freundin benötigt in ihrem Masterstudium Winfo dringend Hilfe in Informatik. Ihr fehlt nur noch eine Klausur bis sie den Master aufgeschlossen hat. Leider ist sie bereits durch die Klausur gefallen Ich hatte letztes Jahr mit Glück bestanden, aber mir fehlt nun auch das Wissen, um ihr helfen zu können.

Folgende Themen umfassen das Fach:
Titel: Polynomielle Kombinatorische Optimierungsalgorithmen
0 Einführung

0.1 Matrizen Exkurs​

0.2 Allgemeine Formulierungen von Optimierungsproblemen​

0.2.1 Generisches Optimierungsproblem​

0.2.2 Kombinatorisches Optimierungsproblem​

0.3 Einführung in die lineare Optimierung​

0.3.1 Lösungen für Lineare Probleme​

0.3.2 Formen von Linearen Problemen​

0.4 Dualitätstheorem​

0.5 Dualisieren von LPs​

0.6 Der Simplexalgorithmus​

0.6.1 Simplex Algorithmus-Zusammenfassung​

0.6.2 Beispielrechnung mit dem Simplexalgorithmus​

1 Probleme, Schranken, Zertifikate

1.1 Verschiedene Probleme​

1.2 Dualität und Schranken​

1.2.1 Lineare Optimierung und untere Schranke Probleme​

2 Optimale Bäume und Wege

2.1 Minimal aufspanndende Bäume​

2.2 Kürzeste Wege​

2.2.1 Zulässige Potentiale und lineare Optimierung​

3 Maximale Flussprobleme

3.1 Flüsse und Schnitte​

3.2 Erhöhender Weg (Augmenting Path) Algorithmus​

3.3 Anwendungen von Max Flow Min Cut​

3.3.1 Bipartite Matchings und Knotenüberdeckungen​

3.3.2 Transportproblem​

3.4 Minimale Schnitte und lineare Optimierung​

3.5 Der Algorithmus von Goldberg und Tarjan [1988]​

3.6 Minimale Schnitte in ungerichteten Graphen („Min-Cut“)​

4 Minimale Kostenflüsse

4.1 Optimalitätsbedingungen, Reduktionen​

4.2 Primale Minimum Kosten Fluss Algorithmen​

4.2.1 Basis-Algorithmus​

4.2.2 Die Netzwerk-Simplex Methode​

4.3 Primal-Duale min Kosten Flussalgorithmen​

4.3.1 Primal-Dualer Algorithmus mit billigsten augmentierenden Wegen​

4.4 Skalierungsalgorithmen für das MKFP​

5 Optimale Matchings

5.1 Matchings und alternierende Wege​

5.2 Maximum Matching​

5.3 Perfektes Matching mit minimum Gewicht​

Bei uns im Studiengang kann es keiner so richtig gut. Alle sind froh, wenn sie da überhaupt durch kommen. Es geht hauptsächlich um das Herleiten von Beweisen, Korrektheit, Laufzeit etc. (z.B. "Zeigen Sie, dass..."). Weniger um das Ausführen von Algorithmen an einem gegebenem Graphen.

Wisst ihr wo man Nachhilfe in diesem Thema erhalten kann? Kennt ihr jemanden, der sich darin gut auskennt?

Perfekt wäre jemand aus Köln oder Umgebung

Viele Grüße,
Alex

EDIT: Titel nicht ganz ausgefüllt. Wende mich mal an einen Mod.

 

[_killy_]

Youtube mal als grobe Empfehlung, ansonsten Studenten der höheren Semester die ebenfalls beim gleichen Prof den Kurs hatten ... so als simple Lösung.

 

[zindelino]

Wie wäre es einfach mal im Bereich bei den wiss. Mitarbeitern nachzufragen. Evtl. hat ein Tutor ja mal eine gute Adresse oder kennt ehemalige Tutoren, die sowas gerne machen würden.

 

[alex1515]

@_killy_
Wir sind schon am Ende des Masters und quasi die, die im höherem Semester sind. Zu Youtube gibt es dazu leider überhaupt nichts.

@zindelino
Haben wir schon gemacht. Leider hat keiner Zeit bzw. Lust.

Das ist alles recht mathematisch und gute Erklärungen findet man kaum. Beispiel:

 

[_killy_]

@alex1515

Wenn ich auf Youtube nach "minimum cost flow reduction problem" suche ... finde ich da auch entsprechende Videos.

 

[Bennomatico]

Seid ihr gar nicht mit den anderen Tagen Studenten vernetzt? Irgendwer hat dich immer ein paar alte Klausuren. Vllt Mal ein paar "fremde" Mitstudenten freundlich fragen.

 

[hallo7]

Vortragenden fragen, vor allem wenn man höheres Semester ist sollte man die ja kennen bzw. jemanden kennen der mit ihnen arbeitet.
Ansonsten Studienvertretung fragen, vor allem wenn ihr viele seid und sagt ihr blickt da nicht durch. Dann muss der Vortragende eben eine extra Einheit machen und es besser erklären.

Allgemein find ich es grausig, dass sowas auf Deutsch gelehrt wird. Klar das man dann nicht viel im Internet dazu findet (es hat da auch jeder seine eigenen Übersetzungen was sehr nervig is)

 

[lokon]

Die geposteten Auszüge stammen scheinbar aus einem Vorlesungsskript. Da fehlen dann je nach Ersteller eben Übergänge oder eine didaktisch bessere Herangehensweise, die in Lehrbüchern oder Fachbüchern vielleicht eher vorhanden ist. Abkürzungsverzeichnisse oder "Algorithmennamen" Deutsch-Englisch sind wie schon geschrieben eher suboptimal dargestellt. Tabelle mit DE-ENG der wichtigen Algorithmen und Alternativnamen hilft vielleicht weiter.

Ausgehend von

Max Flow Min Cut

und andere Terminologien kann dann eine Literaturrecherche weiterhelfen.
Bei der DNB gibt es Ergebnisse und weitere Empfehlungen via "bibtip" (unten). Der Link geht auf DNB aber das Buch wurde via google und in Google Books gefunden.

Apropos Bücher - Schonmal einen unauffälligen Blick in die Bücherregale der Lehrkräfte/ des Lehrstuhls geworfen? Oder welche Bücher zitiert werden ?

http://scholar.google.de/ oder andere Zitierdatenbanken haben recht gute Ergebnisse für erweiternde Literatursuche - also welche Bücher bei einem "Fachausdruck" am meisten zitiert werden. Oder welche Bücher am Lehrstuhl zitiert werden.

Über das Uni-VPN oder Eduroam oder Bibliothekscomputer sollte normalerweise eine freie Benutzung inklusive Downloads von zB Springerlink oder Sciencedirect möglich sein, da eigentlich alle Universitäten die Nationallizenz haben können. Google Scholar bietet manchmal Links an.

Für die Algorithmen gibt es vermutlich auch interaktive Beispiele die Wolfram Alpha oder andere interaktive Spielereien nutzen und visuell vielleicht besser "erklären".

Ansonsten gibt es immernoch genug Material das google mit dem Algorithmusnamen und filetype:pdf findet - Vorlesungsfolien, die eventuelle Skriptlücken didaktisch füllen, Übungs/Tutorienmaterial usw...

Klar das man dann nicht viel im Internet dazu findet

Naja .. durch 7 seiten pdf google-ergebnisse via "Min Cut Max Flow" beispiele filetype:pdf - " wegen Wortzusammenhang - muss sich auch erstmal durchgeklickt werden.