TU Wien:Algorithmen in der Graphentheorie VU (Fleischner)

Aus VoWi
Wechseln zu: Navigation, Suche

Daten[Bearbeiten]

Inhalt[Bearbeiten]

von der LVA-HP:

  • Charakterisierung Eulerscher Graphen
  • Der Satz von Menger und das Spaltungs-Lemma, Knotenabspaltungen, spannende Bäume in ungerichteten und erichteten Graphen (dieser Abschnitt dient quasi als theoretischer Hintergrund, aufgrunddessen das Funktionieren diverser Algorithmen in polynomieller Zeit begründet werden kann)
  • Algorithmen zur Erzeugung diverser Typen Eulerscher Linien
  • Das Chinesische Briefträgerproblem
  • Labyrinthe

Ablauf[Bearbeiten]

Vorlesung. Die Termine werden zu Beginn mit den Teilnehmern vereinbart. Es gibt freiwillige Übungsaufgaben, die man sich zuhause überlegen kann, diese werden dann in der nächsten Vorlesung diskutiert.

Benötigte/Empfehlenswerte Vorkenntnisse[Bearbeiten]

Grundsätzlich keine, außer Interesse für Graphentheorie. Von Graphen sollte man schon etwas gehört haben (z.B. von Algorithmen und Datenstrukturen 1)

Vortrag[Bearbeiten]

Grundsätzlich 2 "echte" Stunden mit einer Pause nach der 1. Stunde. Der Vortrag selber ist recht schnell, man muss aufpassen, dass man den roten Faden nicht verliert. Dies sorgt allerdings auch dafür, dass einem nicht langweilig wird.

SS13: Der Vortrag war fordernd (vor allem, wenn Beweise gebracht wurden) aber nicht zu schnell. Wenn man etwas nicht versteht, einfach nachfragen - der Vortragende erklärt es gern nochmals. Ihm scheint sehr wichtig zu sein, dass die Zuhörer auch verstehen, was er erzählt.

SS14: Ja, es ist ihm sogar äußerst wichtig, dass die Studenten verstehen, was er erzählt. Er erklärte die Sachen gerne auf Wunsch auch 2 oder 3 Mal. Man konnte mit ihm auch nach der Vorlesung gerne noch über gewisse Punkte sprechen, falls irgendwas unklar war.

Übungen[Bearbeiten]

Freiwillig, dienen zur Vorbereitung auf die Prüfung.

Prüfung, Benotung[Bearbeiten]

Mündliche Prüfung, wobei man sich den Termin einfach mit dem Professor ausmachen kann.

Für einen 1er müssen Sie auch Beweise können.

—Prof. Fleischner

SS 14: Für einen 4er reicht es, die einfachsten Definitonen zu kennen. Ich würde sagen, bei (aufmerksamem) Besuch der LVA und 3-5 Stunden Lernaufwand ist man bereits bei einem 4er. 3er und aufwärts jedoch benötigen schon tiefere Kenntnis (3er: Nicht nur Definitionen, sondern auch Sätze / Aussagen von Theoremen erklären können. 2er und 1er: Beweisideen / Beweise respektive)

Literatur[Bearbeiten]

Eingescannte Buchseiten auf der Homepage - Vorlesungsbesuch ist trotzdem empfehlenswert.

SS14: Skriptum als Download im TISS. ca. 50 Seiten = komplettes Stoffgebiet. Ausdrucken und Mitbringen in Vorlesung ist eine gute Idee um Notizen zu machen.

Zeitaufwand[Bearbeiten]

Etwa 3 Stunden pro Vorlesung (hingehen + nachher Beweise überlegen), Lernaufwand für die Prüfung unbekannt.

SS14: Lernaufwand für die Prüfung, je nachdem was man für eine Note möchte:

Meine Schätzung:

4er: 3-5 Stunden (minimales Verständnis von Nöten) 3er: 5-15 Stunden (tieferes Verständis von Nöten) 2er/1er: stark davon abhängig, ob einem Beweise leicht von der Hand gehen.

Ich persönlich hatte bei ca. 10 Stunden Lernaufwand einen 3er, es hat knapp nicht für den 2er gereicht)

Unterlagen[Bearbeiten]

Es gibt eine leider sehr unvollständige Mitschrift (pdf)(tex)

Im SS13 gab es auch ein Skriptum, das den ersten Teil der Vorlesung gut abgedeckt hat. Hingehen sollte man trotzdem, da vieles in der Vorlesung genauer erklärt wird.

Verbesserungsvorschläge / Kritik[Bearbeiten]

Ich fand es relativ beieindruckend wie Prof. Fleischner es schaffte einen 7 Zeilen Pseudocode Algrithmus, mit 2 Tafeln Mathematik zu "erklären".

Andere Meinung: Prof. Fleischner erklärt sehr detailiert und vollständig. Beim Beweis zum "Satz von Menger" hat er sich ein bisschen verlaufen, den Beweis in der nächsten Stunde aber nochmals gut erklärt. Dabei haben sich auch Diskussionen mit Studenten ergeben und man konnte seine Gedankengänge mitverfolgen (was bei sehr gut vorbereiteten Beweisen oft nicht der Fall ist, weil zu schnell vorgetragen wird. Man denke an Mathe-Vorlesungen).

SS14: Toller Vortrag. Ohne den Vortrag ist geht das Skriptum nur schwer von der Hand. Durch den Vortrag allerdings ist sofort klar, wie die Algorithmen in jedem Schritt arbeiten. Nicht scheu sein und einfach nochmal nachfragen, wenn etwas unklar ist. Der Professor schätzt das Interesse der Studenten sehr und freut sich sogar, etwas nochmal erklären zu können.