Náhodnost a výpočty - NMMB432

• Anglický název: Randomness and Calculations
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 4
• Rozsah, examinace: letní s.:2/1, 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í
• Garant: Mgr. Pavel Hubáček, Ph.D.
• Vyučující: Mgr. Pavel Hubáček, Ph.D.
• Třída: M Mgr. MMIB; M Mgr. MMIB > Povinně volitelné
• Kategorizace předmětu: Matematika > Algebra
• Záměnnost : NMMB407
• Je záměnnost pro: NMMB407

Anotace

Pravděpodobnostní metoda. Náhodné procházky. Aplikace náhodnosti v interaktivních důkazových systémech: polynomial identity testing. Pseudonáhodnost a derandomizace:

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (07.12.2018)

Sylabus

Pravděpodobnostní metoda:

• local Lovazs lemma

• linearity of expectation

• the second moment method

Náhodné procházky:

• zajímavé aplikace pro Markovovy řetězce

• undirected S-T connectivity v logspace

Aplikace náhodnosti v interaktivních důkazových systémech:

• polynomial identity testing

• IP=PSPACE

• probabilistically checkable proofs

Pseudonáhodnost a derandomizace:

• pravděpodobnostní třídy jako BPP

• pseudonáhodné generátory

• Nisan-Wigderson PRG a derandomizace

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (07.12.2018)