FI:IA062 Randomized Algorithms - Course Information
IA062 Randomized Algorithms and Computations
Faculty of InformaticsSpring 2017
- Extent and Intensity
- 2/1. 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)
RNDr. Michal Ajdarów (seminar tutor)
Mgr. Luděk Matyska (seminar tutor) - Guaranteed by
- prof. RNDr. Mojmír Křetínský, CSc.
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 10:00–11:50 B410
- Timetable of Seminar Groups:
- Prerequisites
- 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 19 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. 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
- Assessment methods
- oral exam
- Language of instruction
- English
- Further Comments
- Study Materials
The course is taught annually.
- Enrolment Statistics (Spring 2017, recent)
- Permalink: https://is.muni.cz/course/fi/spring2017/IA062