IA062 Randomized Algorithms and Computations

Fakulta informatiky
podzim 2023
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. Daniel Kráľ, Ph.D., DSc. (přednášející)
Mgr. Daniel Iľkovič (cvičící)
prof. RNDr. Daniel Kráľ, Ph.D., DSc. (cvičící)
Marcin Briański (pomocník), prof. RNDr. Daniel Kráľ, Ph.D., DSc. (zástupce)
Garance
prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Út 8:00–9:50 A217
  • Rozvrh seminárních/paralelních skupin:
IA062/01: St 8:00–9:50 A218, D. Iľkovič, D. Kráľ
Předpoklady
General algorithmic and mathematical knowledge is expected.
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á 49 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
    doporučená literatura
  • MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
Výukové metody
IA062 is taught in weekly 2-hour lectures accompanied by 2-hour tutorials.
Metody hodnocení
The resulting grade will based on the final oral exam.
Vyučovací jazyk
Angličtina
Informace učitele
https://www.fi.muni.cz/~dkral/ia062.html
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2003, jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, jaro 2020, jaro 2021, jaro 2022, jaro 2023.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/podzim2023/IA062