PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
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í
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
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)
 
Univerzita Karlova | Informační systém UK