FI:IA062 Randomized Algorithms - Course Information
IA062 Randomized Algorithms and Computations
Faculty of InformaticsAutumn 2023
- 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. Daniel Kráľ, Ph.D., DSc. (lecturer)
Mgr. Daniel Iľkovič (seminar tutor)
prof. RNDr. Daniel Kráľ, Ph.D., DSc. (seminar tutor)
Marcin Briański (assistant), prof. RNDr. Daniel Kráľ, Ph.D., DSc. (deputy) - Guaranteed by
- prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics - Timetable
- Tue 8:00–9:50 A217
- Timetable of Seminar Groups:
- Prerequisites
- General algorithmic and mathematical knowledge is expected.
- 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
- Image Processing and Analysis (programme FI, N-VIZ)
- Applied Informatics (programme FI, N-AP)
- Information Technology Security (eng.) (programme FI, N-IN)
- Information Technology Security (programme FI, N-IN)
- Bioinformatics and systems biology (programme FI, N-UIZD)
- Bioinformatics (programme FI, N-AP)
- Computer Games Development (programme FI, N-VIZ_A)
- Computer Graphics and Visualisation (programme FI, N-VIZ_A)
- Computer Networks and Communications (programme FI, N-PSKB_A)
- Cybersecurity Management (programme FI, N-RSSS_A)
- Discrete algorithms and models (programme FI, N-TEI)
- Formal analysis of computer systems (programme FI, N-TEI)
- Graphic design (programme FI, N-VIZ)
- Graphic Design (programme FI, N-VIZ_A)
- Hardware Systems (programme FI, N-PSKB_A)
- Hardware systems (programme FI, N-PSKB)
- Image Processing and Analysis (programme FI, N-VIZ_A)
- Information security (programme FI, N-PSKB)
- Information Systems (programme FI, N-IN)
- Information Security (programme FI, N-PSKB_A)
- Quantum and Other Nonclassical Computational Models (programme FI, N-TEI)
- Parallel and Distributed Systems (programme FI, N-IN)
- Computer graphics and visualisation (programme FI, N-VIZ)
- Computer Graphics (programme FI, N-IN)
- Computer Networks and Communication (programme FI, N-IN)
- Computer Networks and Communications (programme FI, N-PSKB)
- Computer Systems (programme FI, N-IN)
- Principles of programming languages (programme FI, N-TEI)
- Embedded Systems (eng.) (programme FI, N-IN)
- Embedded Systems (programme FI, N-IN)
- Cybersecurity management (programme FI, N-RSSS)
- Services development management (programme FI, N-RSSS)
- Software Systems Development Management (programme FI, N-RSSS)
- Services Development Management (programme FI, N-RSSS_A)
- Service Science, Management and Engineering (eng.) (programme FI, N-AP)
- Service Science, Management and Engineering (programme FI, N-AP)
- Social Informatics (programme FI, B-AP)
- Software Systems Development Management (programme FI, N-RSSS_A)
- Software Systems (programme FI, N-PSKB_A)
- Software systems (programme FI, N-PSKB)
- Machine learning and artificial intelligence (programme FI, N-UIZD)
- Theoretical Informatics (programme FI, N-IN)
- Upper Secondary School Teacher Training in Informatics (programme FI, N-SS) (2)
- Artificial Intelligence and Natural Language Processing (programme FI, N-IN)
- Computer Games Development (programme FI, N-VIZ)
- Processing and analysis of large-scale data (programme FI, N-UIZD)
- Image Processing (programme FI, N-AP)
- Natural language processing (programme FI, N-UIZD)
- 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
- recommended literature
- MOTWANI, Rajeev and Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
- Teaching methods
- IA062 is taught in weekly 2-hour lectures accompanied by 2-hour tutorials.
- Assessment methods
- The resulting grade will based on the final oral exam.
- Language of instruction
- English
- Further Comments
- Study Materials
The course is taught annually. - Teacher's information
- https://www.fi.muni.cz/~dkral/ia062.html
- Enrolment Statistics (recent)
- Permalink: https://is.muni.cz/course/fi/autumn2023/IA062