TU Wien:Algorithmen in der Graphentheorie VU (Fleischner)

From VoWi
Jump to navigation Jump to search
Diese LVA wird nicht mehr von dieser Person angeboten, ist ausgelaufen, oder läuft aus und befindet sich daher nur noch zu historischen Zwecken im VoWi.

Daten[edit | edit source]

Lecturers Dr. Fleischner
ECTS 3
Department Computergraphik und Algorithmen
Links tiss:186181, Homepage
Zuordnungen
Master Embedded Systems Wahlmodul Algorithmik
Master Logic and Computation Wahlmodul Algorithms and Complexity
Master Software Engineering & Internet Computing Wahlmodul Algorithmik

Mattermost: Channel "algorithmen-in-der-graphentheorie" • Register • Mattermost-Infos

Inhalt[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

Freiwillig, dienen zur Vorbereitung auf die Prüfung.

Prüfung, Benotung[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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.

Retrieved from "https://vowi.fsinf.at/wiki?title=TU_Wien:Algorithmen_in_der_Graphentheorie_VU_(Fleischner)&oldid=131036"