Zufällige Graphen
Random Graphs

Modul MA5208

Dieses Modul wird durch Fakultät für Mathematik bereitgestellt.

Diese Modulbeschreibung enthält neben den eigentlichen Beschreibungen der Inhalte, Lernergebnisse, Lehr- und Lernmethoden und Prüfungsformen auch Verweise auf die aktuellen Lehrveranstaltungen und Termine für die Modulprüfung in den jeweiligen Abschnitten.

Basisdaten

MA5208 ist ein Semestermodul in Englisch auf Master-Niveau das unregelmäßig angeboten wird.

Die Gültigkeit des Moduls ist von SS 2012 bis SS 2012.

GesamtaufwandPräsenzveranstaltungenUmfang (ECTS)
150 h 45 h 5 CP

Inhalte, Lernergebnisse und Voraussetzungen

Inhalt

Although random graphs were first considered as a mere tool for proving the existence of graphs with seemingly contradictory properties, they now form a field of study in their own right. In many cases, they provide appropriate models for real-world networks, and the investigation of their typical properties then lay the foundation for the average-case analysis of many algorithms in optimization. In this course we first focus on the binomial G(n,p) model and investigate some of the phase transitions in its evolution. We then switch to more complicated models for constrained random graphs, such as random trees and random regular graphs. Finally, we analyse randomized algorithms and the expected performance of deterministic algorithms for several optimization problems. The underlying probabilistic methods comprise: First and Second Moment, Large Deviation Inequalities, Generating Functions, Markov Chains.

Lernergebnisse

At the end of the module, students have understood different models of random graphs. They can apply various probabilistic methods to determine typical properties of these random graphs. They are able to use these properties to design and analyse the performance of algorithms for some of the classical optimization problems.

Voraussetzungen

MA1001 Analysis 1, MA1002 Analysis 2, MA1101 Linear Algebra 1, MA1102 Linear Algebra 2, MA1401 Introduction to Probability, MA1501 Introduction to Discrete Mathematics, MA2501 Algorithmic Discrete Mathematics

Lehrveranstaltungen, Lern- und Lehrmethoden und Literaturhinweise

Lern- und Lehrmethoden

Lectures on the blackboard, exercises for work during the tutorials and for homework.

Medienformen

Blackboard

Literatur

N. Alon and J. Spencer: The Probabilistic Method. Wiley, 2011. B. Bollobas: Random Graphs. Cambridge University Press, 2001. P. Flajolet and R. Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009. S. Janson, T. Luczak, and A. Rucinski: Random Graphs. Wiley, 2000. R. Motwani and P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.

Modulprüfung

Beschreibung der Prüfungs- und Studienleistungen

Klausur oder mündliche Prüfung (abhängig von der Teilnehmerzahl)

Wiederholbarkeit

Eine Wiederholungsmöglichkeit wird am Semesterende angeboten.

Kondensierte Materie

Wenn Atome sich zusammen tun, wird es interessant: Grundlagenforschung an Festkörperelementen, Nanostrukturen und neuen Materialien mit überraschenden Eigenschaften treffen auf innovative Anwendungen.

Kern-, Teilchen-, Astrophysik

Ziel der Forschung ist das Verständnis unserer Welt auf subatomarem Niveau, von den Atomkernen im Zentrum der Atome bis hin zu den elementarsten Bausteinen unserer Welt.

Biophysik

Biologische Systeme, vom Protein bis hin zu lebenden Zellen und deren Verbänden, gehorchen physikalischen Prinzipien. Unser Forschungsbereich Biophysik ist deutschlandweit einer der größten Zusammenschlüsse in diesem Bereich.