Teoretická informatika - NSZI068 (Informatika nMgr. - zaměření Teoretická informatika)

• Anglický název: Theoretical Computer Science
• Zajišťuje: Studijní oddělení (32-STUD)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: oba
• E-Kredity: 0
• Rozsah, examinace: 0/0, SZ [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: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Poznámka: student může plnit i v dalších letech; za splnění nejsou body; předmět lze zapsat v ZS i LS

Požadavky ke zkoušce

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.