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

IA062 Randomized Algorithms and Computations

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

• Analýza a zpracování obrazu (program FI, N-VIZ)
• 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 a systémová biologie (program FI, N-UIZD)
• Bioinformatika (program FI, N-AP)
• Computer Games Development (program FI, N-VIZ_A)
• Computer Graphics and Visualisation (program FI, N-VIZ_A)
• Computer Networks and Communications (program FI, N-PSKB_A)
• Cybersecurity Management (program FI, N-RSSS_A)
• Diskrétní algoritmy a modely (program FI, N-TEI)
• Formální analýza počítačových systémů (program FI, N-TEI)
• Grafický design (program FI, N-VIZ)
• Graphic Design (program FI, N-VIZ_A)
• Hardware Systems (program FI, N-PSKB_A)
• Hardwarové systémy (program FI, N-PSKB)
• Image Processing and Analysis (program FI, N-VIZ_A)
• Informační bezpečnost (program FI, N-PSKB)
• Informační systémy (program FI, N-IN)
• Information Security (program FI, N-PSKB_A)
• Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
• Paralelní a distribuované systémy (program FI, N-IN)
• Počítačová grafika a vizualizace (program FI, N-VIZ)
• Počítačová grafika (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-PSKB)
• Počítačové systémy (program FI, N-IN)
• Principy programovacích jazyků (program FI, N-TEI)
• Programovatelné technické struktury (angl.) (program FI, N-IN)
• Programovatelné technické struktury (program FI, N-IN)
• Řízení kyberbezpečnosti (program FI, N-RSSS)
• Řízení vývoje služeb (program FI, N-RSSS)
• Řízení vývoje softwarových systémů (program FI, N-RSSS)
• Services Development Management (program FI, N-RSSS_A)
• 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)
• Software Systems Development Management (program FI, N-RSSS_A)
• Software Systems (program FI, N-PSKB_A)
• Softwarové systémy (program FI, N-PSKB)
• Strojové učení a umělá inteligence (program FI, N-UIZD)
• 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)
• Vývoj počítačových her (program FI, N-VIZ)
• Zpracování a analýza rozsáhlých dat (program FI, N-UIZD)
• Zpracování obrazu (program FI, N-AP)
• Zpracování přirozeného jazyka (program FI, N-UIZD)

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

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