Modul
Probability Theory and Combinatorial Optimization [M-MATH-102947]
Credits
8Recurrence
UnregelmäßigDuration
1 SemesterLanguage
Level
4Version
1Responsible
Organisation
- KIT-Fakultät für Mathematik
Part of
Bricks
Identifier | Name | LP |
---|---|---|
T-MATH-105923 | Probability Theory and Combinatorial Optimization | 8 |
Competence Certificate
The module will be completed by an oral exam (ca. 30 min).
Competence Goal
The students
- know basic problems of combinatorial optimization as discussed in the lectures and are able to explain them,
- know typical methods for the probabilistic analysis of algorithms and combinatorial optimization problems and are able to use them for the solution of specific optimization problems,
- are familiar with the essential techniques of proof and are able to explain them,
- know how to work in a self-organized and self-reflexive manner.
Prerequisites
none
Content
This course is devoted to the analysis of algorithms and combinatorial optimization problems in a probabilistic framework. A natural setting for the investigation of such problems is often provided by a (geometric) graph. For a given system (graph), the average or most likely behavior of an objective function of the system will be studied. In addition to asymptotic results, which describe a system as its size increases, quantitative laws for systems of fixed size will be described. Among the specific problems to be explored are
- the long-common-subsequence problem,
- packing problems,
- the Euclidean traveling salesperson problem,
- minimal Euclidean matching,
- minimal Euclidean spanning tree.
For the analysis of problems of this type, several techniques and concepts have been developed and will be introduced and applied in this course. Some of these are
- concentration inequalities and concentration of measure,
- subadditivity and superadditivity,
- martingale methods,
- isoperimetry,
- entropy.
Recommendation
It is recommended to have taken the module `Probability Theory' from the Bachelor program beforehand.
Workload
Total workload: 240 hours
Attendance: 90 hours
- lectures, problem classes, and examination
Self-studies: 150 hours
- follow-up and deepening of the course content
- work on problem sheets
- literature study and internet research related to the course content
- preparation for the module exam.