IV111 Probability in Computer Science

Faculty of Informatics
Autumn 2024
Extent and Intensity
2/2/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
In-person direct teaching
Teacher(s)
doc. RNDr. Vojtěch Řehák, Ph.D. (lecturer)
Mgr. Tomáš Macháček (seminar tutor)
Vojtěch Kůr (seminar tutor)
Mgr. Ing. Bc. Přemysl Till (assistant)
Guaranteed by
doc. RNDr. Vojtěch Řehák, Ph.D.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 26. 9. to Thu 12. 12. Thu 12:00–13:50 A318
  • Timetable of Seminar Groups:
IV111/01: Mon 30. 9. to Mon 16. 12. Mon 8:00–9:50 A218, T. Macháček
IV111/02: Mon 30. 9. to Mon 16. 12. Mon 10:00–11:50 A218, V. Řehák
IV111/03: Mon 30. 9. to Mon 16. 12. Mon 18:00–19:50 A218, V. Kůr
IV111/04: Wed 2. 10. to Wed 18. 12. Wed 14:00–15:50 A319, V. Řehák
Prerequisites
Knowledge of basic discrete mathematics (e.g. as presented in the course IB000).
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
At the end of the course student should have a broad knowledge and an ability of independent study of problems based on the probability theory and its computer science applications. Will be able to apply the results of the probability theory in practical examples. Should be able to learn independently new problems requiring knowledge of probability theory. Will be able to characterise basic principles of data compression and error correction. Should be able to apply information theory results in practice.
Learning outcomes
Student is able: to define basic terms of the mentioned topics (e.g., random variable, expectation, variance, random process, Markov chain, channel capacity, code rate); to explain meaning on the terms on practical examples; to solve simple examples e.g. using linearity o expectation; to provide basic analysis on both discrete- and continuous-time Markov chains; to compute (conditional) expectation, mutual information, and entropy random variables with given probability distribution; to demonstrate basic proof mentioned during lectures.
Syllabus
  • Probability. Discrete probabilistic space.
  • Random variable and its applications. Expectation and variation.
  • Markov and Chebyshev inequalities. Chernoff bounds. Weak and strong law of large numbers.
  • Random processes. Markov processes.
  • Entropy. Information.
  • Applications in computer science (information theory, coding theory etc).
Literature
  • MITZENMACHER, Michael and Eli UPFAL. Probability and computing : an introduction to randomized algorithms and probabilistic analysis. New York: Cambridge University Press, 2005, xvi, 352. ISBN 0521835402. info
  • GRIMMETT, Geoffrey R. and David STIRZAKER. Probability and random processes. 3rd ed. Oxford: Oxford University Press, 2001, xii, 596 s. ISBN 0-19-857222-0. info
  • TRIVEDI, Kishor Shridharbhai. Probability and statistics with reliability, queuing, and computer science applications. 2nd ed. New York: Wiley, 2002, xv, 830. ISBN 0471333417. info
  • COVER, T. M. and Joy A. THOMAS. Elements of information theory. 2nd ed. Hoboken, N.J.: Wiley-Interscience, 2006, xxiii, 748. ISBN 0471241954. info
  • STINSON, Douglas Robert. Cryptography : theory and practice. 3rd ed. Boca Raton: CRC Press, 2006, 593 s. ISBN 1584885084. info
  • FELLER, William. An introduction to probability theory and its applications. 3rd ed. [New York]: John Wiley & Sons, 1968, xviii, 509. ISBN 9780471257080. info
Teaching methods
Theoretical lectures and practical examples in tutorials.
Assessment methods
Combination of a written test followed by an oral exam.
Language of instruction
English
Further Comments
Study Materials
The course is taught annually.
The course is also listed under the following terms Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2024/IV111