SubjectsSubjects(version: 957)
Course, academic year 2024/2025
   Login via CAS
Probabilistic Techniques - NTIX022
Title: Pravděpodobnostní techniky
Guaranteed by: Student Affairs Department (32-STUD)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: English
Teaching methods: full-time
Teaching methods: full-time
Is provided by: NTIN022
Additional information: http://iuuk.mff.cuni.cz/~samal/vyuka/pm/
Guarantor: doc. Mgr. Robert Šámal, Ph.D.
doc. RNDr. Martin Tancer, Ph.D.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
M Mgr. MSTR
M Mgr. MSTR > Povinně volitelné
Classification: Informatics > Discrete Mathematics, Theoretical Computer Science
Pre-requisite : {NXXX007, NXXX008, NXXX009, NXXX036, NXXX037, NXXX051, NXXX052, NXXX053}
Incompatibility : NTIN022
Interchangeability : NTIN022
Annotation -
Probabilistic techniques are a major tool of discrete mathematics, they are also frequently used in design and analysis of algorithms and other areas of computer science. The lecture introduces basic notions, methods, and estimates and illustrates them on examples from computer science and discrete mathematics.
Last update: IUUK (04.05.2015)
Aim of the course -

Student who takes the class will learn to actively use a modern

probabilistic techniques in discrete mathematics and computer science,

including the probabilistic method.

Last update: IUUK (04.05.2015)
Course completion requirements -

For getting the credit from tutorials, the students are required to get at least 50 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. Both exam and the tutorial test may be in person or in distant mode.

Last update: Klazar Martin, doc. RNDr., Dr. (22.09.2020)
Literature -
  • M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.
  • N. Alon, J. Spencer: The Probabilistic Method, 3rd edition, J. Wiley and Sons, 2008.
  • J. Matousek, J. Vondrak: The probabilistic method, lecture notes, KAM MFF UK, electronic version will be available on the web-site of the lecture, printed version in the library of MFF UK.
  • J. Spencer: Ten lectures on the probabilistic method, 2nd edition, SIAM, 1994.

Last update: IUUK (04.05.2015)
Requirements to the 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.

Last update: Tancer Martin, doc. RNDr., Ph.D. (05.10.2018)
Syllabus -

Basic notions and methods

  • events, expected value and its linearity
  • conditional probability, Bayes' rule

Basic inequalities and estimates

  • Markov's a Chebyshev's inequality
  • Chernoff-type estimates

Probabilistic method

  • basic method and alteration method
  • Lovász local lemma

Advanced techniques

  • balls and bins model, basic estimates and applications
  • Markov chains, stationary distribution
  • basic continuous distributions as limits of discrete ones, properties and applications

Last update: IUUK (04.05.2015)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html