Informační systém Masarykovy univerzity 

Informace o předmětu

IA062 Randomized Algorithms and Computations

Fakulta informatiky
jaro 2018

Rozsah

2/2. 4 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í)
Bc. Michal Ajdarów (cvičící)
Mgr. Luděk Matyska (cvičící)

Garance

prof. RNDr. Mojmír Křetínský, CSc.
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 B410

• Rozvrh seminárních/paralelních skupin:

IA062/01: Čt 16:00–17:50 B410, M. Pivoluska

Předpoklady

No special requiremnts are neede.

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory

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

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. 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

• 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

Výukové metody

lectures

Metody hodnocení

ustna skuska

Vyučovací jazyk

Angličtina

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 2019.

---

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