Modulcode:	Inf-RGA
Englische Bezeichnung:	Random Graphs and Algorithms
Modulverantwortliche(r):	Prof. Dr. Anand Srivastav
Turnus:	unregelmäßig (SS17 SS18)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	180 Std.
Dauer:	ein Semester
Modulkategorien:	WI (MSc Inf (15))
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Das Thema der Vorlesung ist das Gebiet der zufälligen Graphen und effizienten Algorithmen für das Erkennen von Eigenschaften zufälliger Graphen. Es werden u.a. behandelt: Konzentrationsungleichungen, Martingale, Färbungen, Cliquen, Subgraphen, die Giant Component, Gradsequenzen, Preferential-Attachment Graphen, Internetmodellierung.

Lernziele:

Anwenden von Konzentrationsungleichungen, u.a. Martingale, auf kombinatorische Probleme, Erlernen der Modellierung und der Analyse von Zufallsgraphen, Analyse kombinatorischer Algorithmen für Zufallsgraphen, Erlernen der Modellierung von Real-World und Small-World-Netzwerken, u.a. des Internets.

Lehrinhalte:

Second Moment Method, Chernov-Hoeffding Ungleichungen, Martingalungleichungen, Evolution der G(n,p)-Graphen, Bestimmung der chromatischen Zahl, der Cliquenzahl, des Zusammenhangs, der Giant Component und von Subgraphen im G(n,p)-Modell, Phasenuebergang, Preferantial-Attachment Graphen, Zufallsgraphen mit Gradsequenzen, Small-World-Netzwerke und Internet.

Weitere Voraussetzungen:

Diskrete Wahrscheinlichkeits-Theorie (Mathe C oder Stochastik), Kenntnisse der Linearen Algebra und Analysis (Mathe B,C oder LA I, Analysis I,II), Graphentheorie.

Prüfungsleistung:

Abschließende Klausur (Bei weniger als 5 Teilnehmern mündliche Prüfung).

Lehr- und Lernmethoden:

Tafelvortrag

Verwendbarkeit:

Wahlpflichtmodul im Master Mathematik und Master Informatik.

Literatur:

1. Béla Bollobás "Modern Graph Theory", Springer 1991.
2. Noga Alon, Joel H. Spencer "The Probabilistic Method", Wiley Interscience Series in Discrete Mathematics 1998.
3. Svante Janson, Tomasz Luczak, Andrzej Rucinski "Random Graphs", Wiley 2000.

Verweise:

Kommentar: