Probabilistic Techniques II - NTIN095
Title in English: Pravděpodobnostní techniky II
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2019
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: Czech, English
Teaching methods: full-time
Additional information: http://kam.mff.cuni.cz/~samal/vyuka/pm2/
Guarantor: doc. Mgr. Robert Šámal, Ph.D.
doc. RNDr. Martin Klazar, Dr.
Class: Informatika Mgr. - volitelný
Classification: Informatics > Discrete Mathematics, Theoretical Computer Science
Opinion survey results   Examination dates   Schedule   Noticeboard   
Annotation -
Last update: (28.04.2016)
Probabilistic method is a way to prove existence of objects by counting: in a suitable probability space one shows that with nonzero probability we get the desired object. This class is a continuation of Probabilistic Techniques NTIN022 where the basic techniques were described. (The knowledge of those is necessary to follow this class.) In this class we will extend and deepen these techniques. The class is complementing (but not overlapping) with Probabilistic algorithms NDMI025.
Aim of the course -
Last update: T_KAM (04.05.2011)

The students will learn to actively use advanced techniques

in Probabilistic method.

Course completion requirements -
Last update: doc. Mgr. Robert Šámal, Ph.D. (14.02.2018)

For getting the credit from tutorials, the students are required to get at least 45 points from homework. The total number of available points will be at least 180. There is no provision for repeated attempts for the credit. Credit from tutorials is a necessary condition for an attempt to pass an exam.

The exam will be oral based on the contents of the lectures. Extra points gained by students by solving problems for tutorials will be considered in favor of the students.

Literature -
Last update: T_KAM (04.05.2011)

N. Alon, J.H. Spencer: Probabilistic Method, Wiley, 2000.

M. Molloy, B. Reed: Graph Colouring and the Probabilistic Method, Springer, 2002.

S. Janson, T. Luczak, A. Rucinski: Random Graphs, Wiley-Interscience, 2000.

Syllabus -
Last update: (22.04.2016)

Martingales, Azuma inequality.

Talagrand inequality.

Poisson paradigm -- Janson inequality and Brun sieve.

Quasirandomness.

Random graphs.

Multi-phase random processes (iterative coloring of sparse graphs).