Applications of the Probabilistic MethodModulbeschreibung #40978 / Version 1
- 6 LP
- Mündliche Prüfung
- Benotet
- Winter- und Sommersemester
- Englisch
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
| Modul / Version | #40978 / #1 |
|---|---|
| Gültigkeit | SoSe 2020 – SoSe 2022 |
| Verfügbare Sprache(n) | Englisch |
| Leistungspunkte | 6 |
| Modulverantwortliche*r | Schaefer, Rafael |
| Benotung | Benotet |
| Prüfungsform | Mündliche Prüfung |
| Lehrsprache(n) | Englisch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Telekommunikationssysteme |
| Fachgebiet | 34331900 FG Informationstheorie und deren Anwendungen |
Kontakt
| Sekretariat | HFT 6 |
|---|---|
| Ansprechpartner*in | Günlü, Onur |
| E-Mail-Adresse | rafael.schaefer@tu-berlin.de |
| Webseite | http://www.commit.tu-berlin.de/menue/lehre/parameter/en/ |
Lernergebnisse
After completing the module the students will have a solid understanding of the probabilistic method and its applications in various information systems including analyzing randomized algorithms used in information theory, coding theory, information and differential privacy, machine learning, wireless communications, gambling, and data systems. They will get familiar with the current literature in the field and will be able to analyze, apply, and develop probabilistic inequalities as a proof technique to show the existence (and sometimes construction) of randomized algorithms that achieve a claimed performance in various network topologies.
Lehrinhalte
This course aims to expose students to powerful tools and ideas from probability theory that are not commonly covered in undergraduate probability courses or graduate courses on stochastic processes. The focus of the lecture will not be on randomized algorithms, but on the most recent applications of probabilistic methods in hot topics!
The course begins by a number of examples to motivate probabilistic thinking. We then discuss probability inequalities with an emphasis on advanced versions of Chernoff bounds (both the additive and multiplicative forms). Applications of these bounds in Information Theory, Information Security, and Machine Learning will be extensively discussed. Then, we introduce martingales that allow us to obtain more powerful concentration inequalities than Chernoff bounds. Applications of martingales in Gambling, (Polar) Coding Theory used in 5G, Hypothesis Testing, and DNA Pattern Matching will be given as examples. Next, we talk about “Balls into bins” and the Poisson approximation method. Finally, we plan to go into the details of the probabilistic method such as the basic counting argument, the expectation argument, the second moment method, and the Lovász local lemma.
Previous knowledge expected
- A course on probability theory (although a brief recap will be given at the beginning)
The course begins by a number of examples to motivate probabilistic thinking. We then discuss probability inequalities with an emphasis on advanced versions of Chernoff bounds (both the additive and multiplicative forms). Applications of these bounds in Information Theory, Information Security, and Machine Learning will be extensively discussed. Then, we introduce martingales that allow us to obtain more powerful concentration inequalities than Chernoff bounds. Applications of martingales in Gambling, (Polar) Coding Theory used in 5G, Hypothesis Testing, and DNA Pattern Matching will be given as examples. Next, we talk about “Balls into bins” and the Poisson approximation method. Finally, we plan to go into the details of the probabilistic method such as the basic counting argument, the expectation argument, the second moment method, and the Lovász local lemma.
Previous knowledge expected
- A course on probability theory (although a brief recap will be given at the beginning)
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
Arbeitsaufwand und Leistungspunkte
Applications of the Probabilistic Method (Vorlesung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 3 h | 45 h |
| Pre/post processing | 15 | 4 h | 60 h |
| 105 h | |||
Applications of the Probabilistic Method (Übung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 1 h | 15 h |
| Pre/post processing | 15 | 4 h | 60 h |
| 75 h | |||
Der Aufwand des Moduls summiert sich zu 180 Stunden. Damit umfasst das Modul 6 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
The module consists of conventional frontal teaching in class using slides and blackboard, developing theoretical and mathematical concepts and an oral examination.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
Prerequisite for participation to courses are a mathematical background at the level of beginning MS students in Electrical Engineering and an undergraduate level background in probability theory.
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Mündliche Prüfung |
| Sprache | Englisch, Deutsch |
| Dauer/Umfang | 30 minutes |
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Winter- und Sommersemester.
Maximale teilnehmende Personen
Die maximale Teilnehmerzahl beträgt 40.
Anmeldeformalitäten
Course teaching and organization is supported by an ISIS course. Module examination enrollment is done via QISPOS.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
nicht verfügbar
Empfohlene Literatur
- M. Mitzenmacher, E. Upfal, Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.
- N. Alon, J. H. Spencer, The probabilistic method. John Wiley & Sons, 2004.
- R. Motwani, P. Raghavan, Randomized algorithms. Cambridge University Press, 1995.
Zugeordnete Studiengänge
Dieses Modul findet in keinem Studiengang Verwendung.
Sonstiges
Verwendbarkeit: Studiengebiete:
Kommunikationssysteme und Informationssysteme
WiIng
Kommunikationssysteme und Informationssysteme
WiIng