Pravděpodobnostní algoritmy - NDMI025

• Anglický název: Randomized Algorithms
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: letní
• E-Kredity: 5
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Další informace: http://iuuk.mff.cuni.cz/~sgall/vyuka/PALG/
• Garant: prof. RNDr. Jiří Sgall, DrSc.
• Vyučující: prof. RNDr. Jiří Sgall, DrSc.; Mgr. Pavel Veselý, Ph.D.
• Třída: Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Je neslučitelnost pro: NTIN054, NDMX025
• Je záměnnost pro: NDMX025, NTIN054

Anotace

čeština

Přenáška o použití náhodnosti v algoritmech a protokolech. Náhodnost umožňuje řešit některé úlohy, které jsou bez jejího použití neřešitelné nebo řešitelné méně efektivně. Probereme metody pro návrh a analýzu takových algoritmů a protokolů, ilustrované na konkrétních problémech. Předpokládá se znalost na úrovni předmětů NDMI084 Úvod do aproximačních a pravděpodobnostních algoritmů a NTIN022 Pravděpodobnostní techniky.

Poslední úprava: IUUK (11.05.2015)

angličtina

The course covers the use of randomness in design of efficient algorithms. Use of randomness allows to solve problems more efficiently or even to solve problems that are otherwise intractable. The course covers techniques for design of randomized algorithm, demonstrated on concrete problems. We assume knowledge on the level of the courses NDMI084 Introduction to approximation and randomized algorithms and NTIN022 Probabilistic Techniques.

Poslední úprava: IUUK (11.05.2015)

Cíl předmětu

čeština

Získat přehled o metodách použití náhodnosti v algoritmech a schopnost takové algoritmy analyzovat.

Poslední úprava: IUUK (11.05.2015)

angličtina

Teach the students selected techniques of use of randomness in algorithms and of analysis of such algorithms.

Poslední úprava: IUUK (11.05.2015)

Podmínky zakončení předmětu

čeština

Pro získání je zápočtu je nutné získat polovinu z celkového počtu bodů za domácí úkoly zadané během semestru za podmínky účasti studenta na cvičeních. Při neúčasti jsou potřeba dvě třetiny z celkového počtu bodů. Povaha kontroly studia neumožňuje opakování zápočtu.

Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.

Poslední úprava: Sgall Jiří, prof. RNDr., DrSc. (26.02.2019)

angličtina

To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester conditioned on regular attendance. If the student does not attend the tutorials regularly, two thirds of total points will be required. Due to the requirements, additional attempts to pass the tutorial are not allowed.

The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.

Poslední úprava: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)

Literatura

čeština

• M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press, 2005.

• R. Motwani, P. Raghavan: Randomized algorithms. Cambridge Univ. Press, 1995.

Poslední úprava: IUUK (11.05.2015)

Požadavky ke zkoušce

čeština

Zkouška je ústní s písemnou přípravou. Požadavky odpovídají sylabu v míře pokryté přednáškami. Zápočet je nutnou podmínkou účasti u zkoušky.

Poslední úprava: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)

angličtina

The exam is oral with time for written preparation. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.

Poslední úprava: Sgall Jiří, prof. RNDr., DrSc. (22.06.2019)

Sylabus

čeština

• Příklady pravděpodobnostních algoritmů a protokolů

• Třídy pravděpodobnostních algoritmů a jejich vztahy

• Věty o minimaxu (von Neumann, Yao)

• Techniky pro omezení počtu náhodných bitů: po dvou nezávislé proměnné, expandery

• Markovovy řetězce a jejich použití: náhodné procházky a testování souvislosti grafů, algoritmy pro splnitelnost, přibližné počítání (splňující ohodnocení, párování v hustých grafech), coupling (počítání obarvení grafů)

• Základy teorie front

• Algoritmy pro proudy dat

• Pravděpodobnostní protokoly a verifikace: testování linearity funkcí, PCP věta (důkaz exponenciální verze)

Poslední úprava: IUUK (11.05.2015)

angličtina

• Examples of randomized algorithms and protocols

• Classes of languages defined by randomized algorithms and their relations

• Minimax theorems (von Neumann, Yao)

• Methods of derandomization: pairwise independent variables, expanders

• Markov chains and their applications: random walks and connectivity, satisfiability algorithms, approximate counting (satisfying assignments, matchings in dense graphs), coupling (counting of graph colorings)

• Introduction into queuing theory

• Streaming algorithms

• Randomized protocols and verification: linearity testing, PCP theorem (the proof of the exponential version)

Poslední úprava: IUUK (11.05.2015)