FI:IA062 Randomized Algorithms - Course Information
IA062 Randomized Algorithms and Computations
Faculty of InformaticsSpring 2022
- 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).
- Teacher(s)
- 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 - Timetable
- Wed 16. 2. to Wed 11. 5. Wed 10:00–11:50 B410
- Timetable of Seminar Groups:
- Prerequisites
- No special requirements are needed.
- 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.
- Syllabus
- 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.
- Aplications:
- Linear programming.
- Parallel and distributed algoritms.
- Randomization in cryptography.
- Randomized methods in theory of numbers.
- Literature
- Teaching methods
- Lectures and tutorials
- Assessment methods
- oral exam
- Language of instruction
- English
- Further Comments
- Study Materials
The course is taught annually. - Teacher's information
- https://www.fi.muni.cz/usr/gruska/random19/
- Enrolment Statistics (Spring 2022, recent)
- Permalink: https://is.muni.cz/course/fi/spring2022/IA062