NI-TI.2023
Teoretická informatika (verze 2023)
Platnost pro SZZ od června 2024.
| Označení | Otázka | Předmět |
|---|---|---|
| NI-TI-1 | Algoritmy přesného a přibližného vyhledávání. | NI-EVY |
| NI-TI-2 | Úplné indexování textu. | NI-EVY |
| NI-TI-3 | Succinct data structures. | NI-EVY |
| NI-TI-4 | Lineární programování, simplexová metoda, dualita lineárního programování, slabá a silná věta o dualitě a její důsledky. | NI-LOM |
| NI-TI-5 | Polynomiální algoritmy řešení lineárního programování. Aplikace lineárního programování v algoritmech. | NI-LOM |
| NI-TI-6 | Celočíselné lineární programování, totálně unimodulární matice, Steinitzovo lemma. | NI-LOM |
| NI-TI-7 | LR(0), SLR(k), LALR(k) a LR(k) syntaktická analýza. | NI-SYP |
| NI-TI-8 | Formální a atributovaný překlad řízený LR analyzátorem. | NI-SYP |
| NI-TI-9 | Barevnost grafů, Brooksova věta, perfektní a chordální grafy, listové barvení a vybíravost, hranové barvení a Vizingova věta, výsledky pro barevnost a vybíravost rovinných grafů. | NI-GAK |
| NI-TI-10 | Ramseyova věta pro grafy a hypergrafy a jejich důsledky a souvislosti, Schurova a Erdösova-Szekeresova věta, extremální kombinatorika a Turánova věta. | NI-GAK |
| NI-TI-11 | Párování v obecných grafech, Tutteova věta, Edmondsův algoritmus, lineárně-algebraický přístup k výpočtu počtu koster grafy pomocí determinantu. | NI-GAK |
| NI-TI-12 | Entropie zprávy (řádu 0 a vyšší), modelování. Statistické metody komprese dat. | NI-KOD |
| NI-TI-13 | Slovníkové metody komprese dat. | NI-KOD |
| NI-TI-14 | Kontextové metody komprese dat. | NI-KOD |
| NI-TI-15 | Třída FPT, parametrizace, omezené prohledávací stromy, kernelizace, iterativní komprese. Neexistence polynomiálních kernelů. | NI-PAM |
| NI-TI-16 | Dynamické programování, stromové rozklady, Courcellova věta, aproximace a minory. Bidimenzionalita. | NI-PAM |
| NI-TI-17 | Parametrizovaná nedostupnost, charakterizace tříd nedostupnosti. ETH a SETH a jejich důsledky pro parametrizované i polynomiálně řešitelné problémy. | NI-PAM + NI-CPX |
| NI-TI-18 | (Nedeterministické) Turingovy stroje a jejich výpočty, Halting problém. Třídy DTIME, P, NP, coNP, EXP a vztahy mezi nimi. NP-úplnost a polynomiální redukce. Cookova věta. | NI-CPX |
| NI-TI-19 | Výpočty s orákulem, polynomiální hierarchie. Prostorová složitost, třídy PSPACE, NPSPACE, L, NL, coNL a vztahy mezi nimy. Savitchova věta. | NI-CPX |
| NI-TI-20 | Neuniformní výpočty. Třída P/poly, AC^k, NC^k a vztahy mezi nimi, P-úplnost. Pravděpodobnostní výpočty, třídy ZPP, RP, coRP, BPP a vztahy mezi nimi. | NI-CPX |
| NI-TI-21 | Aproximační algoritmy. Třídy NPO, APX, PTAS a vztahy mezi nimi. PCP-věta a její důsledky. | NI-CPX |
📄 Tabulka je dostupná také v CSV (hodnoty oddělené středníkem).
🔙 Historii změn najdete na GitLabu.