Randomised algorithms

Modulnummer: Q10-40
Englischer Titel: Randomised algorithms
Leistungspunkte: 10
Lehrperson: Rybicki

Empfohlene Vorkenntnisse

Good basic knowledge in algorithms and data structures and discrete mathematics. No prior knowledge in probability theory is needed.

Zwingende Voraussetzungen

None

Inhalt

Randomisation and probabilistic techniques play an important role in computer science. This course focuses on the design and analysis of randomised algorithms, which are algorithms that make random choices during their execution. For many problems, such algorithms are both simpler and more efficient than known deterministic solutions.

In this course, participants will learn the basic probability-theoretic tools for the design and analysis of randomised algorithms as well as methods for analysing simple discrete stochastic processes. Topics include expected running time analysis, concentration bounds, applications of the probabilistic method, Markov chains and random walks, and martingales.

Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung

- completion and presentation of solutions to home work exercises.

Lehrveranstaltungen

Vorlesung: 4 SWS 6 LP
Übung: 2 SWS 3 LP
MAP: 1 LP

Zugeordneter Vertiefungsschwerpunkt

Algorithmen und Modelle: ja
Modellbasierte Systementwicklung: nein
Daten- und Wissensmanagement: nein
Ohne Vertiefungsschwerpunkt: nein

Sprache im Modul

Deutsch: nein
Englisch: ja

Angeboten für Studiengänge

M. Sc.: ja
M. Ed.: ja
Wirtschaftsmaster: ja

Angeboten im

Wintersemester: nein
Sommersemester: nein

Turnus

Unregelmäßig