Basic information

This course is open for both bachelor's and master's 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 solve more complex examples where naive intuition fails - which in probability occurs quite often. The 'more experienced' students would appreciate a revision and a complete rebuild of their big-picture knowledge supported by practical applications in solutions to word problems. The core part will be devoted to studying 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 a 2-hour tutorial every week of the semester. In 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.

Attendance at tutorials is compulsory and absence will be penalized, see Assessment method for more detail. Some tutorials are canceled due to public holidays; for more details, see 

The exercises solved during the tutorials are available in 

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 and 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. Thomas M. COVER and Joy A. THOMAS. Elements of information theory. 2nd ed. Hoboken, N.J.: Wiley-Interscience, 2006. xxiii, 748. ISBN 9780471241959.
5. Douglas R. 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 studying 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, 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 be known by foreign colleagues (even with an earlier date of birth).