|
|
Pořadí | Název předmětu |
Tématický okruh 1 (TO1) z nabídky 3 | |
1 | Složitost a kryptografie |
2 | Reprezentace znalostí v binární doméně |
3 | Algoritmy |
4 | Datové struktury |
|
||
Poslední úprava: Mgr. Dina Novotná Obeidová (14.07.2022)
Zkušební požadavky
Student si volí tři okruhy z~následující nabídky, z~nichž dostane po jedné otázce. Otázky k~jednotlivým okruhům vychází z~látky probrané v~rámci povinných předmětů a~předmětů doporučených k~jednotlivým okruhům.
1. Složitost a~kryptografie
Výpočty s~orákuly a~relativizované výpočetní třídy. Polynomiální hierarchie. Pravděpodobnostní výpočetní třídy. Neuniformní modely výpočtu. Interaktivní protokoly. Komunikační složitost. Vztahy a~separace různých tříd složitosti. Kryptografie založená na předpokladech výpočetní obtížnosti. Jednosměrné funkce a~hard-core predikáty. Pseudonáhodné generátory. Integrita dat (message authentication codes). Kryptografické hašovací funkce. Schémata pro commitment. Zero-knowledge důkazové systémy.
2. Reprezentace znalostí v~binární doméně
Rezoluce a~její úplnost. Dualizace. Třídy booleovských funkcí a~formulí se speciálními vlastnostmi. Exponenciální algoritmy pro k-SAT a~obecný SAT. Parametrizované algoritmy pro SAT. Algoritmy pro MAXSAT. Reprezentace znalostí založené na NNF. Řešiče pro SAT založené na DPLL a~CDCL a~jejich využití pro SMT. Parciální krychle a~mediánové grafy. Grayovy kódy. Isoperimetrické nerovnosti a~lineární rozvržení. Turánovské problémy. Obvody, třída P/poly a~její vlastnosti. QBF a~jejich vlastnosti vzhledem k~polynomiální hierarchii a~třídě PSPACE. Algoritmy pro rozhodování QBF. Samo-opravné kódy.
3. Algoritmy
Pokročilé grafové algoritmy, toky v~síti. Lineární a~semidefinitní programování, polynomiální algoritmy pro ně, použití v~grafových a~aproximačních algoritmech. Kombinatorické aproximační algoritmy a~schémata. Pseudopolynomiální algoritmy, silná NP-úplnost. Parametrizované algoritmy - FPT, parametrizované dolní odhady, parametrizované aproximační algoritmy. Pravděpodobnostní algoritmy, přibližné počítání, hašování a~jeho aplikace. Interaktivní protokoly a~verifikace, PCP věta a~její aplikace.
4. Datové struktury
Výpočetní modely (RAM a~jeho varianty). Entropie a~informace. Samoopravné kódy. Komprese dat. Vyhledávací stromy. Hešování. Pokročilé haldy. Datové struktury pro práci s~celými čísly. Vícerozměrné datové struktury. Datové struktury pro práci s~řetězci. Textové algoritmy. Struktury pro práci s~grafy. Dynamizace a~persistence. Práce s~paměťovou hierarchií. Data-streamové problémy. |