Randomness and Calculations - NMMB432
Title: |
Náhodnost a výpočty |
Guaranteed by: |
Department of Algebra (32-KA) |
Faculty: |
Faculty of Mathematics and Physics |
Actual: |
from 2020 |
Semester: |
summer |
E-Credits: |
4 |
Hours per week, examination: |
summer s.:2/1, Ex [HT] |
Capacity: |
unlimited |
Min. number of students: |
unlimited |
4EU+: |
no |
Virtual mobility / capacity: |
no |
State of the course: |
taught |
Language: |
English, Czech |
Teaching methods: |
full-time |
Teaching methods: |
full-time |
|
|
|
Last update: 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:
|
|
Last update: 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
|