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

• Title: Teoretická informatika
• Guaranteed by: Student Affairs Department (32-STUD)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2021
• Semester: both
• E-Credits: 0
• Hours per week, examination: 0/0, STEX [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Note: can be fulfilled in the future; no points awarded for fulfilment; you can enroll for the course in winter and in summer semester

Requirements to the exam

Last update: 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.