Studenti, kteri prednasku absolvovali v ramci bakalarskeho studia
(a uspesne slozili - u me - zkousku) a maji ji znovu zapsanou
v ramci magisterskeho studia, maji dve moznosti:
(1) Znovu slozit zkousku beznym zpusobem.
(2) Nastudovat tri clanky (v naznacenem rozsahu) nize
a ja je z jednoho z nich - dle nahodneho vyberu - vyzkousim.
Spodni odhady na velikost booleovskych obvodu
konstantni hloubky pro paritu (dukaz aproximacni metodou Razborov-Smolensky).
Clanek Boppana-Sipser'89, sekce 3.8.
Komunikacni slozitost.
Clanek Razborov'11, prvni 3 kapitoly.
"Natural proofs" Razborova a Rudiche a veta o jejich neexistenci.
Clanek Razborov-Rudich'99, kapitoly 1, 2 (mimo
sekce 2.2) a Veta 4.1 (s dukazem!).