BI-TI
Teoretická informatika
platnost od SZZ v červnu 2020
| Označení | Otázka | Předmět |
|---|---|---|
| BI-TI-1 | Transformace bezkontextových gramatik a jejich normální formy. Algoritmus CYK. | BI-AAG |
| BI-TI-2 | Implementace konečného automatu, lexikální analyzátor. | BI-AAG |
| BI-TI-3 | Vyšší souvislost grafů: Vrcholová a hranová k-souvislost, jejich určování a vztahy, Mengerova a Fordova-Fulkersonova věta. Mosty, artikulace a jejich hledání. Silně souvislé komponenty orientovaného grafu a jejich hledání. | BI-AG2 |
| BI-TI-4 | Toky v sítích: Síť, tok, řez, vztah velikosti toku a kapacity řezu, Fordův-Fulkersonův algoritmus. Párování, hledání maximálního párování v bipartitním grafu, Hallova věta a její důsledky. | BI-AG2 |
| BI-TI-5 | Rovinné grafy a barevnost grafů: Eulerova formule. Kuratowského věta. Barevnost grafu, barevnost rovinných grafů. | BI-AG2 |
| BI-TI-6 | Pokročilé datové struktury: Fibonacciho haldy a složitost jejich operací v nejhorším případě. (a,b)-stromy. | BI-AG2 |
| BI-TI-7 | Eulerovské a hamiltonovské grafy: Eulerovský tah, charakterizace eulerovských grafů, minimální pokrytí tahy. Hamiltonovská kružnice, Chvátalův uzávěr, Chvátalova věta. | BI-AG2 |
| BI-TI-8 | Vzdálenosti v grafech: Floydův-Warshallův algoritmus. Problém obchodního cestujícího, definice a aproximační algoritmus. | BI-AG2 |
| BI-TI-9 | Geometrické algoritmy: Konvexní obal bodů v rovině, určování orientace úhlu. Technika sweep-line a rychlý výpočet průsečíků úseček. | BI-AG2 |
| BI-TI-10 | Instrukční cyklus počítače a zřetězené zpracování instrukcí. Mikroarchitektura skalárního procesoru se zřetězeným zpracováním instrukcí, řízení toku instrukcí mezi stupni, datové, řídicí a strukturální hazardy při zpracování instrukcí a způsoby jejich odstranění. | BI-APS.1 |
| BI-TI-11 | Paměťová hierarchie se skrytou pamětí (cache memory) a principy paměťové lokality. Princip fungování skryté paměti. Architektura přímé, částečně asociativní, plně asociativní skryté paměti. Funkce skryté paměti v rámci instrukčního cyklu a vliv skryté paměti na rychlost vykonání programů. | BI-APS.1 |
| BI-TI-12 | Virtualizace hlavní paměti stránkováním a její HW podpora. Funkce MMU (Memory Management Unit) a překlad adres pomocí TLB (Translation Lookaside Buffer). | BI-APS.1 |
| BI-TI-13 | Principy protokolů pro zajištění paměťové koherence datových skrytých pamětí vícejádrového či víceprocesorového systému se sdílenou paměťovou sběrnicí. Instrukce pro synchronizaci přístupů do sdílené paměti. | BI-APS.1 |
| BI-TI-14 | Mikroarchitektura superskalárních procesorů, instrukční paralelismus, vykonávání instrukcí mimo pořadí, spekulativní zpracování instrukcí, přejmenování registrů, statické a dynamické predikce skoků a techniky urychlení vykonávání paměťových operací. | BI-APS |
| BI-TI-15 | Lineární zobrazení a jeho matice: definice a základní vlastnosti (matice složeného/inverzního zobrazení, hodnost matice vs. hodnost zobrazení), matice přechodu (změna báze). | BI-LIN |
| BI-TI-16 | Lineární kódy: základní pojmy teorie kódování, generující a kontrolní matice, kódování a dekódování. | BI-LIN |
| BI-TI-17 | OOP abstrakce a hierarchie tříd - balíčky, třídy, atributy, metody, konstruktory, traity, ekvivalence a identita, nadtřídy, podtřídy, dědičnost, statický a dynamický dispatch. | BI-OOP |
| BI-TI-18 | OOP polymorphismus - subtyping, generics, bounds a variance. | BI-OOP |
| BI-TI-19 | OOP chybový stav a reflexe - signalizování výjimečných stavů, výjimky, stack trace, total functions, design by contract, object model a dynamic code invocation. | BI-OOP |
| BI-TI-20 | Syntaktický analyzátor shora dolů, prostředky pro jeho specifikaci – bezkontextové gramatiky, zásobníkové automaty, vztah mezi nimi. LL(1) gramatiky, transformace gramatik. Programová realizace syntaktického analyzátoru pro LL(1) gramatiky. | BI-PJP |
| BI-TI-21 | Prostředky pro specifikaci syntaxí řízeného překladu – překladové gramatiky, atributové gramatiky, atributové překladové gramatiky. LL-atributové překladové gramatiky, programová realizace rekurzívním sestupem s parametry. | BI-PJP |
| BI-TI-22 | Vnitřní formy programu, syntaktický strom, překlad základních jazykových konstrukcí. | BI-PJP |
| BI-TI-23 | Rozdělení paměti při implementaci programovacích jazyků: statické části, zásobník, halda. Aktivační záznamy, mechanismus implementace volání funkcí. | BI-PPA |
| BI-TI-24 | Lambda kalkul: definice pojmů, operací, reprezentace čísel. | BI-PPA |
| BI-TI-25 | Funkcionální programování, funkce vyšších řádů, Lisp: atomy, seznamy, funkce, cons buňky, rekurze, mapovací funkcionály. | BI-PPA |
| BI-TI-26 | Logické programování, Prolog: fakta, pravidla, dotazy, způsob vyhodnocení dotazů, unifikace, operátor řezu. | BI-PPA |
| BI-TI-27 | Lineární regrese, regularizace pomocí hřebenové regrese. | BI-VZD |
| BI-TI-28 | Metoda nejbližších sousedů, metriky, metody shlukové analýzy (k-nejbližších center, hierarchické shlukování). | BI-VZD |
| BI-TI-29 | Rozhodovací stromy: algoritmus konstrukce stromů, hyperparametry. Náhodné lesy. | BI-VZD |
| BI-TI-30 | Logistická regrese. | BI-VZD |
📄 Tabulka je dostupná také v CSV (hodnoty oddělené středníkem).
🔙 Historii změn najdete na GitLabu.