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 a complete rebuild of their big-picture knowledge supported by practical applications in solutions to word problems. 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 a 2-hour tutorial every week of the 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.

COVID Teaching

During the COVID time, the lectures are not allowed in the present form. Hence, the students are expected to watch the records stored in

During the regular time of the lecture, the lector will be available for individual consultations in a videoconference room. For more detail see:

He will not repeat the lecture, but he will be ready to reinterpret unclear parts of the lecture and keen on deeper discussions on the relevant topics.

The tutorials are based on the following collection of exercises. They are divided into individual tutorials and optional examples for individual practice. The students are expected to solve the examples individually. There are also solutions in the collection but it is very important to note that it is completely useless to look at the solution without making a serious effort in solving it. During the regular tutorial time, the tutors will be ready to discuss the difficult parts in the above-mentioned Zoom meeting room. Hence, the simple rules are: 

1. Try hard to solve the examples before the tutorial time.
2. Do not look at the solutions before the tutorial time - in many cases the solutions are simple, but it is difficult to find them.

Time will show, whether some tutorials (time slots during the week) will be closed, or newly opened.

At any time, the students are welcome to ask their questions in the IS discussion forum of this course. We will do our best to answer the questions soon (which means "within one working day"). 

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 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).