I062 Randomized Algoritms and Computations

Faculty of Informatics
Spring 1999
Extent and Intensity
2/0. 3 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Jozef Gruska, DrSc. (lecturer)
Guaranteed by
Contact Person: prof. RNDr. Jozef Gruska, DrSc.
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
Syllabus
  • 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.
  • 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.
Language of instruction
Czech
Further Comments
The course is taught annually.
The course is taught: every week.
The course is also listed under the following terms Spring 1998, Spring 2000, Spring 2002.
  • Enrolment Statistics (Spring 1999, recent)
  • Permalink: https://is.muni.cz/course/fi/spring1999/I062