Přednášky:
1. Šifrovací algoritmus RSA, problém prvočíselnosti, související algebraické základy.
2. Millerův-Rabinův test prvočíselnosti a jeho korektnost.
3. Randomizované komunikační protokoly a důkazy jejich korektnosti.
4. Interaktivní protokoly, speciálně pro problém #SAT (počet pravdivostních ohodnocení, při nichž je zadaná booleovská formule pravdivá).
5. Důkazy bez úniku informace (zero-knowledge proofs).
6. Pravděpodobnostně ověřitelné důkazy (PCP, probabilistically checkable proofs).
7. Aproximační algoritmy, např. pro Max-3-SAT, množinové pokrytí, (pod)problému TSP (obchodního cestujícího).
8. Plně polynomiální aproximační schémata.
9. Důkazy neaproximovatelnosti konkrétních optimalizačních problémů.
10. Automaty a logika na nekonečných slovech (bězích reaktivních systémů). Užití u verifikace systémů (model checking).
Cvičení (na tabulové učebně):
1. Návrh implementace konkrétních částí algoritmu RSA.Procvičení pojmu grupa a konečné těleso v souvislosti s problémem
prvočíselnosti.
2. Důkazy lemmat pro korektnost Millerova-Rabinova testu prvočíselnosti.
3. Analýza konkrétního randomizovaného komunikačního protokolu.
4. Běhy interaktivního protokolu pro problém #SAT na konkrétních instancích.
5. Analýza protokolů autentizace bez úniku informace.
6. Důkazy částí tzv. PCP teorému.
7. Návrh a analýza konkrétních aproximačních algoritmů.
8. Analýza plně polynomiálního aproximačního schématu pro problém batohu.
9. Diskuse důkazu neaproximovatelnosti problému maximální kliky v grafu.
10. Překlad formulí vyjadřujících vlastnosti běhů konkrétních systémů do formy automatů.
1. Šifrovací algoritmus RSA, problém prvočíselnosti, související algebraické základy.
2. Millerův-Rabinův test prvočíselnosti a jeho korektnost.
3. Randomizované komunikační protokoly a důkazy jejich korektnosti.
4. Interaktivní protokoly, speciálně pro problém #SAT (počet pravdivostních ohodnocení, při nichž je zadaná booleovská formule pravdivá).
5. Důkazy bez úniku informace (zero-knowledge proofs).
6. Pravděpodobnostně ověřitelné důkazy (PCP, probabilistically checkable proofs).
7. Aproximační algoritmy, např. pro Max-3-SAT, množinové pokrytí, (pod)problému TSP (obchodního cestujícího).
8. Plně polynomiální aproximační schémata.
9. Důkazy neaproximovatelnosti konkrétních optimalizačních problémů.
10. Automaty a logika na nekonečných slovech (bězích reaktivních systémů). Užití u verifikace systémů (model checking).
Cvičení (na tabulové učebně):
1. Návrh implementace konkrétních částí algoritmu RSA.Procvičení pojmu grupa a konečné těleso v souvislosti s problémem
prvočíselnosti.
2. Důkazy lemmat pro korektnost Millerova-Rabinova testu prvočíselnosti.
3. Analýza konkrétního randomizovaného komunikačního protokolu.
4. Běhy interaktivního protokolu pro problém #SAT na konkrétních instancích.
5. Analýza protokolů autentizace bez úniku informace.
6. Důkazy částí tzv. PCP teorému.
7. Návrh a analýza konkrétních aproximačních algoritmů.
8. Analýza plně polynomiálního aproximačního schématu pro problém batohu.
9. Diskuse důkazu neaproximovatelnosti problému maximální kliky v grafu.
10. Překlad formulí vyjadřujících vlastnosti běhů konkrétních systémů do formy automatů.