PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
Pravděpodobnostní algoritmy - NDMI025
Anglický název: Randomized Algorithms
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2021 do 2021
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: nevyuč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.
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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: IUUK (11.05.2015)
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.
Cíl předmětu -
Poslední úprava: IUUK (11.05.2015)

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

Podmínky zakončení předmětu -
Poslední úprava: prof. RNDr. Jiří Sgall, DrSc. (26.02.2019)

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.

Literatura -
Poslední úprava: IUUK (11.05.2015)
  • 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.

Požadavky ke zkoušce -
Poslední úprava: prof. RNDr. Jiří Sgall, DrSc. (22.06.2019)

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.

Sylabus -
Poslední úprava: IUUK (11.05.2015)
  • 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)

 
Univerzita Karlova | Informační systém UK