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í |
Způsob výuky: |
prezenční |
|
|
|
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (07.12.2018)
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: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (07.12.2018)
Pravděpodobnostní metoda:
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
- probabilistically checkable proofs
Pseudonáhodnost a derandomizace:
- pravděpodobnostní třídy jako BPP
- Nisan-Wigderson PRG a derandomizace
|