FI:IA062 Randomized Algorithms - Informace o předmětu
IA062 Randomized Algorithms and Computations
Fakulta informatikyjaro 2021
- Rozsah
- 2/2/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
- Vyučující
- prof. RNDr. Jozef Gruska, DrSc. (přednášející)
RNDr. Matej Pivoluska, Ph.D. (cvičící) - Garance
- prof. RNDr. Jozef Gruska, DrSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Jozef Gruska, DrSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky - Rozvrh
- St 10:00–11:50 Virtuální místnost
- Rozvrh seminárních/paralelních skupin:
- Předpoklady
- No special requirements are needed.
- Omezení zápisu do předmětu
- Předmět je nabízen i studentům mimo mateřské obory.
- Mateřské obory/plány
- předmět má 48 mateřských oborů, zobrazit
- Cíle předmětu
- 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.
- Výstupy z učení
- 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.
- Osnova
- 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.
- Literatura
- Výukové metody
- Lectures and tutorials
- Metody hodnocení
- oral exam
- Vyučovací jazyk
- Angličtina
- Informace učitele
- https://www.fi.muni.cz/usr/gruska/random19/
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně.
- Statistika zápisu (jaro 2021, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2021/IA062