FI:IA062 Randomized Algorithms - Course Information
IA062 Randomized Algorithms and ComputationsFaculty of Informatics
- Extent and Intensity
- 2/2/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
- prof. RNDr. Jozef Gruska, DrSc. (lecturer)
RNDr. Matej Pivoluska, Ph.D. (seminar tutor)
- Guaranteed by
- prof. RNDr. Jozef Gruska, DrSc.
Department of Computer Science - Faculty of Informatics
Contact Person: prof. RNDr. Jozef Gruska, DrSc.
Supplier department: Department of Computer Science - Faculty of Informatics
- Mon 17. 2. to Fri 15. 5. Wed 10:00–11:50 B410
- Timetable of Seminar Groups:
- No special requiremnts are neede.
- 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
- there are 48 fields of study the course is directly associated with, display
- Course objectives
- The aim: randomized algorithms and methods are becoming one of the key tools for an effective solution of a variety of problems in informatics and its aplications practically in all theoretical and aplication areas.
- Learning outcomes
- After finishing the lecture student will be able: To manage basic techniques to design randomized algorithms; to understand differences concerning power of deterministic and randomized algorithms; to manage basic tools for analysis of randomized algorithms; to work with tail inequalities; to understand power and use of the probabilistic method; to understand power of random walks; to understand power of randomized proofs; to understand basic principles of randomized cryptographic protocols.
- Randomized algorithms and methods.
- Examples of randomized algorithms.
- Methods of game theory.
- Main types of randomized algorithms.
- Randomized complexity classes.
- Chernoff's bounds.
- Moments and deviations.
- Probabilistic methods.
- Markov chains and random walks.
- Algebraic methods.
- Linear programming.
- Parallel and distributed algoritms.
- Randomization in cryptography.
- Randomized methods in theory of numbers.
- Teaching methods
- Assessment methods
- oral exam
- Language of instruction
- Further Comments
- Study Materials
The course is taught annually.
- Enrolment Statistics (recent)
- Permalink: https://is.muni.cz/course/fi/spring2020/IA062