Basic information

This course is open for both bachelor and master students. It is intended to supplement the knowledge of probability with a special emphasis on its application in computer science. Some students have already heard about the probability in the mathematical subjects MB104 Discrete Mathematics or MV011 Statistics I, others have only a basic knowledge from high school. Hence, we start from the basic mathematical definitions. The aim is to build a rigorous basis to be able to solve more complex examples where naive intuition fails - which in probability occurs quite often. The 'more experienced' students would appreciate a revision and knowledge interconnection presented from an another teacher point of view. The core part will be devoted to the study of random processes (e.g. Markov models) and information theory and entropy with applications in computer science (e.g. encoding and channel capacity).

Teaching

The course has a two-hour lecture and 2-hour tutorial every week of semester. At the lecture, there will be demonstrated and explained definitions, basic concepts, illustrative examples and some demonstrative proofs of selected theorems. At the tutorials, we will apply the knowledge from lectures when solving some (usually) word problems.

This year, the lecture and tutorials are cancelled at the seventh week of the semester, for more details see the schedule.

Literature

Slides will be published in "Study Materials". It is worth mentioning that some proofs are missing to allow students to write them on their own. Other literature:

1. Michael MITZENMACHER a Eli UPFAL. Probability and computing : an introduction to randomized algorithms and probabilistic analysis. New York: Cambridge University Press, 2005. xvi, 352 s. ISBN 0-521-83540-2.
2. Geoffrey R. GRIMMETT a David STIRZAKER. Probability and random processes. 3rd ed. Oxford: Oxford University Press, 2001. xii, 596 s. ISBN 0-19-857222-0.
3. Kishor Shridharbhai TRIVEDI. Probability and statistics with reliability, queuing, and computer science applications. 2nd ed. New York: Wiley, 2002. xv, 830 s. ISBN 0-471-33341-7.
4. Elements of information theory. Edited by T. M. Cover - Joy A. Thomas. 2nd ed. Hoboken, N.J.: Wiley-Interscience, 2006. xxiii, 748. ISBN 9780471241959.
5. Douglas Robert STINSON. Cryptography: theory and practice. 3rd ed. Boca Raton: CRC Press, 2006. 593 p. ISBN 1-58488-508-4.
6. Chapter 2 of Mark M. Wilde. From Classical to Quantum Shannon Theory. arXiv:1106.1445. 2013.
7. David J. C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. xii, 628. ISBN 9780521642989. https://www.inference.org.uk/itprnn/book.pdf
   
8. William FELLER. An introduction to probability theory and its applications. 3rd ed. [New York]: John Wiley & Sons, 1968. xviii, 509. ISBN 0-471-25708-7.

The first book is a readable introduction to probability in computer science. The second one is a rigorous mathematical basis for the study of probability and random processes. The third book is written in a more practical way, the book is full of practical examples to the reliability of software and hardware components, computation of expected running time of processes, the processor utilization etc. The fourth book is a classic textbook on information theory. The fifth book is devoted to coding and serves as a supplement to information theory. The sixth item is a nicely written online chapter on data compression and channel capacity. The seventh book introduces information theory in tandem with applications; there are also online lectures on YouTube. The last one is a classical mathematical textbook where you can find what is expected to know by foreign colleagues (even with an earlier date of birth).