Předmět Vybrané partie teoretické informatiky (VPTI)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu VPTI - Vybrané partie teoretické informatiky, Vysoká škola báňská - Technická univerzita Ostrava (VŠB-TU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Student po úspěšném absolvování předmětu např.:- umí vyhodnotit vhodnost a rozsah možného nasazení aproximačních algoritmů a pravděpodobnostních algoritmů při řešení praktických problémů a umí příslušné algoritmy navrhovat, analyzovat a srovnávat- umí exaktně vysvětlit další pojmy a metody vybraných pokročilých partií teoretických základů informatiky
Osnova
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 Sharp-SAT. (počet pravdivostních ohodnocení, při nichž je zadaná booleovská formulepravdivá).5. Důkazy bez úniku informace (zero-knowledge proofs).6. Pravděpodobnostně ověřitelné důkazy (PCP, probabilistically checkableproofs).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íchsysté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émemprvočí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 Sharp-SAT na konkrétníchinstancí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émbatohu. 9. Diskuse důkazu neaproximovatelnosti problému maximální kliky vgrafu.10. Překlad formulí vyjadřujících vlastnosti běhů konkrétních systémů do formyautomatů.
Literatura
- P. Jančar: pracovní text ke kursu "Vybrané partie teoretické informatiky"(dostupný z web-stránky předmětu)
Požadavky
Žádné
Garant
prof. RNDr. Petr Jančar, CSc.
Vyučující
prof. RNDr. Petr Jančar, CSc.