Pravděpodobnost a kryptografie - NMMB407
Anglický název: Probability and Cryptography
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:4/0, 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: nevyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Je zajišťováno předmětem: NMMB432
Další informace: http://dostanou moje poznamky na konci semestru
Garant: Mgr. Pavel Hubáček, Ph.D.
Třída: M Mgr. MMIB
Kategorizace předmětu: Matematika > Algebra, Pravděpodobnost a statistika
Neslučitelnost : NMIB051
Záměnnost : NMIB051, NMMB432
Je záměnnost pro: NMMB432, NMIB051
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace
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:
Sylabus
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (07.12.2018)

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