IA062 Náhodnostní algoritmy a výpočty

Fakulta informatiky
jaro 2007
Rozsah
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í)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Jozef Gruska, DrSc.
Rozvrh
St 10:00–11:50 B410
Předpoklady
! I062 Náhodnostní algoritmy
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
Cíle předmětu
Náhodnostní algoritmy a metody se stávají klíčovými prostředky pro efektivní řešení problémů v informatice i prakticky ve všech teoretických a aplikačních oblastech.
Osnova
  • Náhodnostní algoritmy a metody.
  • Příklady náhodnostních algoritmů.
  • Základní typy náhodnostních algoritmů.
  • Náhodnostní třídy složitosti.
  • Metody teorie her.
  • Chernoffovy odhady.
  • Momenty a deviace.
  • Pravděpodobnostní metody.
  • Markovovy řetězce a náhodné cesty.
  • Algebraické metody.
  • Aplikace
  • Lineární programování.
  • Paralelní a distribuované algoritmy.
  • Náhodnostní metody v kryptografii.
  • Náhodnostní metody v teorii čísel.
Literatura
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
  • MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
Další komentáře
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 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, podzim 2023.