TU Wien:Diskrete Mathematik für Informatik VU (Gittenberger)

Daten

Vortragende	Bernhard Gittenberger
ECTS	3
Alias	Discrete Mathematics for Computer Science (en)
Letzte Abhaltung	2023WS
Sprache	English
Mattermost	diskrete-mathematik-fuer-informatik • Register • Mattermost-Infos
Links	tiss:104283, eLearning, Homepage

Zuordnungen

Masterstudium Visual Computing

Inhalt

• Graphentheorie (mit Matroiden)
• Grundlagen der Topologie

Ablauf

Wöchentliche Vorträge und Kreuzerlübungen (an zwei verschiedenen Tagen), Übungstest, schriftliche Prüfung eine Woche nach der letzten Übungseinheit.

Benötigte/Empfehlenswerte Vorkenntnisse

Vorkenntnisse aus Mathematik 1 und 2 sind recht wichtig. Insbesondere Grundlagen der Mengenlehre und Beweisführung über Kontradiktion und Induktion sowie Implikationen im Kreis (a => b => c => a) sollten beherrscht werden, da es sich bei vielen Übungsbeispielen um Beweise dreht. Wenn jemand bei der Tafel diese Dinge nicht kann, wirds eng. (Wobei man hier dem Prof recht geben muß, daß diese Dinge in einem Masterstudium schon bekannt sein sollten..)

Vortrag

Vortrag in englischer Sprache, allerdings gut verständlich. Vortragender geht recht flott durch den Stoff durch. Algorithmen werden mit PPT veranschaulicht, alles andere wird wie bei Mathematik üblich an der Tafel vorgerechnet.

Übungen

Wöchentliche Kreuzerlübungen, 6 Übungseinheiten insgesamt. Man kreuzt die Beispiele im TUWEL an, die man zuhause errechnet, und in der Übungseinheit nimmt Prof. Gittenberger jemanden dran, der an der Tafel die Lösung erklärt. Die Übungseinheiten finden ca. von 13 bis 15 Uhr statt. In der 3. oder 4. Übungseinheit gibts außerdem einen Übungstest, bei dem praxisorientiert gefragt wird, sprich: Fokus liegt auf Algorithmen und Rechnungen. Theorie sollte man verstanden haben, Beweise kommen aber recht selten, und wenn, dann sinds einfache. Es empfiehlt sich sehr, die Übungsbeispiele vor dem Test noch mal alle durchzugehen.

Die Gesamtanzahl der Übungsbeispiele variiert von Semester zu Semester. Fix ist aber, daß für die Übungseinheit, in der der Test stattfindet, es wesentlich weniger Beispiele zu lösen gibt. ZB im WS 2013 gabs pro Einheit üblicherweise 8 Beispiele, aber in der Einheit mit dem Test nur 4. Im Jahr 2015 gabs gar nur 3 Beispiele.

Teilweise gibt es Lösungsvorschläge für die Übungsbeispiele:

• UE aus dem Jahr 2013: TU_Wien:Diskrete_Mathematik_für_Informatik_UE_(Gittenberger)/Übungen_WS13
• Informatik-Forum: https://web.archive.org/web/*/www.informatik-forum.at/forumdisplay.php?1461-Diskrete-Mathematik-VU

Zwischentest

WS2015: https://web.archive.org/web/*/www.informatik-forum.at/showthread.php?111632-Angabe-Zwischentest-2015

WS2019: https://vowi.fsinf.at/wiki/TU_Wien:Diskrete_Mathematik_f%C3%BCr_Informatik_VU_(Gittenberger)/%C3%9Cbungstest_2019-11-08

Prüfung, Benotung

Eine Woche nach der letzten Einheit gibt es eine schriftliche Prüfung, zu der man kommen muss; Abwesenheit muss begründet und die Begründung nachgewiesen werden. Man hat eine zweite (evtl. auch dritte) Chance im Januar, falls man beim ersten mal in der Prüfung negativ war. Algorithmen kommen i.d.R. nicht (dafür ist der Zwischentest da), Beweise aber sehr wohl. Es sind vier Fragen zu beantworten.

Die vier Beispiele setzen sich aus Definitionen und Beweisen zusammen, die Angaben für 2013 und 2015 findet man z.B. hier: https://web.archive.org/web/*/www.informatik-forum.at/showthread.php?105509-Pr%FCfung&p=838722 auch in den Materialien.

Das Bewertungssystem setzt sich aus den Punkten für die Tafelleistung, der Gesamtanzahl angekreuzter Übungsbeispiele, der Punkte für den Test, und der Prüfungspunkte zusammen.

Die kompletten Kriterien lauten gemäß TISS:

• Übungen+Tafelleistung: mindestens 30 von 80 Punkten (80 = 20 max. für Tafel + 60 max. für Beispiele)

Das ist anfangs etwas verwirrend, da wiegesagt die Anzahl der Übungsbeispiele variiert. Man muß sich die Punkte aus der Anzahl angekreuzter Beispiele ausrechnen: punkte_für_beispiele = anzahl_angekreuzter_beispiele * 60 / gesamtanzahl_beispiele. ZB bei insgesamt 45 Beispielen, 42 angekreuzten, ergibt sich 42*60/45 = 56 Punkte.

• Test: mindestens 6 von 20 Punkten . Weniger als 6 Punkte kann man in der Prüfung kompensieren, so daß man bei <6 Punkten nicht automatisch durchgefallen ist. (Aber, die Prüfung wird dann verdammt schwer.)
• Prüfung: mindestens 40 von 100 Punkten. Hat man jedoch beim Test weniger als 6 Punkte, dann steigt die Mindestanzahl auf 80 von 100 Punkten...
• Insgesamt: mindestens 120 von 200 Punkten. Hierzu einfach die Punkte von oben aufaddieren. So kann man auch sehen, wieviele Punkte man mindestens für die Prüfung braucht, um insgesamt positiv zu sein.

Beispiel: die 56 Punkte vom obigen Beispiel für die Übungspunkteberechnung, samt 15 Punkte auf dem Test, 16 für die Tafelleistung, ergibt 87 Punkte. 120-87 = 33, also bräuchte man theoretisch nur 33 Punkte, um insgesamt positiv zu sein. (d.h. das ist unter dem Minimum für die Prüfung, somit ist die Minimalleistung da genug.)

Eine weitere Erklärung gibt es hier .

Dauer der Zeugnisausstellung

Zeugnis war wenige Tage nach dem Final Exam da

Zeitaufwand

Eher hoch

Zeitaufwand für die Übungsaufgaben

Man sollte möglichst früh mit den Aufgaben anfangen. Etliche Tage muß man schon investieren, je nach Schwierigkeitsgrad der Beispiele. Und da man nur eine Woche Zeit hat, sieht man, daß es ansonsten recht eng werden kann.

Zeitaufwand für den Test

Für den Test sollte man sich zumindest ein paar Tage reservieren. Hier gilt es vor allem, die Algorithmen auswendig zu lernen, und gut zu üben, um diese schnell durchrechnen zu können. Theorie sollte man sich auch ansehen, Beweise kommen aber i.d.R nicht.

Zeitaufwand für die Prüfung

Die Woche nach der letzten Übungseinheit sollte man sich fürs Lernen reservieren. Insbesondere Beweisführungen sollten gut geübt werden. Nochmaliges Durchlesen der Mitschrift und Einprägen von Definitionen ist wichtig.

Unterlagen

• Eigene Mitschrift
• Folien auf der VU-Seite für Algorithmen
• inoffizielles Skriptum, wobei nur Kapitel 1 für die VU relevant ist: http://www.dmg.tuwien.ac.at/gittenberger/Skriptum-DiscrMath13W.pdf
• außerdem im Informatik Forum: https://web.archive.org/web/*/www.informatik-forum.at/showthread.php?108993-Stoff-Zusammenfassung
• Erklärung Matroide: http://www.maa.org/sites/default/files/pdf/shortcourse/2011/matroidsknown.pdf
• Armstrong - Basic Topology (gibts in der TU Bib zum Ausleihen)
• Prüfungsangaben: Materialien

Tipps

Es ist bei dieser Lehrveranstaltung sehr wichtig, möglichst viele Übungsbeispiele zu lösen. Für jede Übungseinheit sollte man am besten mindestens 60% der Beispiele lösen. Da der Schwierigkeitsgrad leicht steigt, ist es außerdem eine gute Idee, besonders bei den ersten paar Einheiten alle oder fast alle Beispiele zu lösen. Wie die obere Rechnung zeigt, kann man im Idealfall so dafür sorgen, daß man für die Prüfung nur das Minimum braucht. Bei der Tafelleistung wird eine exakte Vorgehensweise gefordert. Wenn zB man bei einem Beispiel eine Äquivalenz zeigen soll, aber der präsentierte Beweis eine Implikation ist, dann wird Prof. Gittenberger da nachbohren. Man kann zwar diskutieren, jedoch ist es nicht ratsam, um den heißen Brei herumzureden. Es kommt jeder mindestens einmal dran. Bei schlechten Tafelleistungen steigt die Chance, daß man irgendwann nochmal drankommt. In der letzten Übungseinheit tendiert der Prof dazu, die letzten paar Beispiele auf freiwilliger Basis lösen zu lassen.

Desweiteren ist eine gute Vorbereitung vor dem Test ebenfalls sehr wichtig, da sonst die Mindestanforderung für die Prüfungspunkte wirklich sehr hoch wird (80/100 Punkte).

Vorbereitung für Prüfung: Definitionen und Beweise

wenn man die unten stehenden Definitionen kennt und die Beweise schafft, sollte die Prüfung kein allzu großes Problem mehr darstellen.

Define

• subgrah, walk, cycle, circuit, trail, path
• Handshake Lemma
• loop, multiple edge, dir. ,undir., simple
• hypercube
• conn.comp, strongly, weakly, shadow
• vertex base
• tree and 4 equivalent def.
• forest
• spanning forest
• matrix-tree-theorem
• min/max spanning forests
• network
• independent system
• matroid
• basis of matroid
• rank of matroid
• network and flow network
• distance in network
• flow, size of flow
• cut, size of cut
• augmenting path
• Eulerian
• Hamilton
• planar, subdivision, Kuratowski, isomorphism
• dual graph
• bipartite
• matching, perfect matching
• vertex/edge coloring, chromatic number
• metric space, eps ball, neighbourhood
• open, closed set, boundary, complete
• continues function, homeomorphism
• topolociacal space T, basis of T
• connectedness
• topological properties, invariant under homeomorphism
• 2d manifold = surface
• path, pathconnected
• orientable
• handle, genus, betti numbers
• eulers characteristic for different surfaces

Prove

• |V|, |E| of hypercube
• a.ij ^[k] = # walks in G, i->j, with len=k
• xRy is euqivalence relation
• tree has at least 2 leafs
• G=(V,E), S={F <= E | F forest}, show that (E,S) is matroid
• sum(flow(sx)) = sum(flow(yt)), x are successors of s, y are predeccesors of t
• Eulerian <=> d(v) even for all v € V
• Eulers formula v-e+f=2
• G is hamiltonian <=> [G] is hamiltonian
• G simple, planar, no cyles len=3 -> e<=2v-4
• dmin<=5 in simple planar G
• show that G simple planar is: a. 6 colorable, b. 5 colorable

Highlights / Lob

noch offen

Verbesserungsvorschläge / Kritik

noch offen

Materialien

Neues Material hinzufügen

P

• Prüfung 2019-12-13
• Prüfung 2017-12-15
• Prüfung 2016-04-28
• Prüfung 2016-03-04
• Prüfung 2016-01-22
• Prüfung 2015-11-27
• Prüfung 2013-12-02

U

• Übungstest 2019-11-08