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

IA062 Randomized Algorithms and Computations

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í)
RNDr. 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 21. 2. až Čt 16. 5. Čt 12:00–13: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/plány

• 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é 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)
• 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)
• 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

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

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