FI:IA062 Randomized Algorithms - Informace o předmětu

IA062 Randomized Algorithms and Computations

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

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

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

• Aplikovaná informatika (program FI, N-AP)
• Bezpečnost informačních technologií (program FI, N-IN)
• Bioinformatika (program FI, N-AP)
• Informační systémy (program FI, N-IN)
• Informatika (program FI, M-IN)
• Informatika (program FI, N-IN)
• Paralelní a distribuované systémy (program FI, N-IN)
• Počítačová grafika (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-IN)
• Počítačové systémy (program FI, N-IN)
• Programovatelné technické struktury (angl.) (program FI, N-IN)
• Teoretická informatika (program FI, N-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
• Učitelství výpočetní techniky pro střední školy (program FI, M-TV)
• Učitelství výpočetní techniky pro střední školy (program FI, N-SS) (2)
• Umělá inteligence a zpracování přirozeného jazyka (program FI, N-IN)
• Zpracování obrazu (program FI, N-AP)

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

Metody hodnocení

ustna skuska

Vyučovací jazyk

Angličtina

Další komentáře

Předmět je vyučován každoročně.

• Statistika zápisu (jaro 2009, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2009/IA062