FI:IA062 Randomized Algorithms - Course Information

IA062 Randomized Algorithms and Computations

Extent and Intensity

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. Ivan Fialík, Ph.D. (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Jozef Gruska, DrSc.

Timetable

Wed 10:00–11:50 B410

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

• Applied Informatics (programme FI, N-AP)
• Information Technology Security (programme FI, N-IN)
• Bioinformatics (programme FI, N-AP)
• Information Systems (programme FI, N-IN)
• Informatics (programme FI, M-IN)
• Informatics (programme FI, N-IN)
• Parallel and Distributed Systems (programme FI, N-IN)
• Computer Graphics (programme FI, N-IN)
• Computer Networks and Communication (programme FI, N-IN)
• Computer Systems (programme FI, N-IN)
• Embedded Systems (eng.) (programme FI, N-IN)
• Theoretical Informatics (programme FI, N-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-TV)
• Upper Secondary School Teacher Training in Informatics (programme FI, N-SS) (2)
• Artificial Intelligence and Natural Language Processing (programme FI, N-IN)
• Image Processing (programme FI, N-AP)

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.

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

• GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
• MOTWANI, Rajeev and Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info

Assessment methods

oral exam

Language of instruction

English

Further Comments

The course is taught annually.

• Enrolment Statistics (Spring 2009, recent)
  
• Permalink: https://is.muni.cz/course/fi/spring2009/IA062