SZZ Státní závěrečná zkouška
Jdi na navigaci předmětu

BI-TI.21

Teoretická informatika

Tyto okruhy jsou určené pro studenty se studijním plánem v akreditaci Informatika 2021. Platí pouze v červnu/sprnu 2023.

OznačeníOtázkaPředmět
BI-TI.21-1Lineární zobrazení: definice a vlastnosti (hodnost, jádro, defekt, injektivita, surjektivita), matice lineárního zobrazení.BI-LA2.21
BI-TI.21-2Skalární součin a norma vektoru: definice, vlastnosti a příklady.BI-LA2.21
BI-TI.21-3Ortogonalita a ortogonální báze: definice, vlastnosti, využití při počítání vzdáleností lineárních variet.BI-LA2.21
BI-TI.21-4LU rozklad matic, řešení soustavy lineárních rovnic pomocí LU rozkladu.BI-LA2.21
BI-TI.21-5Logický důsledek a ekvivalence ve výrokové a v predikátové logice. Disjunktivní a konjunktivní normální tvary. Rezoluční metoda. Metoda sémantických stromů.BI-LOG.21
BI-TI.21-6Teorie, model, logický důsledek. Axiomatický systém logiky. Korektnost, úplnost, bezespornost. Gödelova věta o neúplnosti.BI-LOG.21
BI-TI.21-7Binární relace: jejich vlastnosti a reprezentace, relace ekvivalence a rozklady množin, částečné a úplné uspořádání.BI-DML.21
BI-TI.21-8Přehled Chomského hierarchie formálních jazyků a gramatik. Turingovy stroje. Třídy problémů P, NP, NP-těžký, NP-úplný.BI-AAG.21
BI-TI.21-9Transformace bezkontextových gramatik a jejich normální formy. Algoritmus CYK.BI-AAG.21
BI-TI.21-10Implementace konečného automatu, lexikální analyzátor.BI-AAG.21 + BI-PJP.21
BI-TI.21-11Vyšší 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.21
BI-TI.21-12Toky 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.21
BI-TI.21-13Rovinné grafy a barevnost grafů: Eulerova formule. Kuratowského věta. Barevnost grafu, barevnost rovinných grafů.BI-AG2.21
BI-TI.21-14Pokročilé datové struktury: Fibonacciho haldy a složitost jejich operací v nejhorším případě. (a,b)-stromy.BI-AG2.21
BI-TI.21-15Eulerovské 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.21
BI-TI.21-16Vzdálenosti v grafech: Floydův-Warshallův algoritmus. Problém obchodního cestujícího, definice a aproximační algoritmus.BI-AG2.21
BI-TI.21-17Geometrické 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.21
BI-TI.21-18Instrukč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.21
BI-TI.21-19Paměť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.21
BI-TI.21-20Virtualizace 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.21
BI-TI.21-21OOP 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.21
BI-TI.21-22OOP polymorphismus - subtyping, generics, bounds a variance.BI-OOP.21
BI-TI.21-23OOP 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.21
BI-TI.21-24Syntaktický 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.21
BI-TI.21-25Prostř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.21
BI-TI.21-26Vnitřní formy programu, syntaktický strom, překlad základních jazykových konstrukcí.BI-PJP.21
BI-TI.21-27Rozdě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.21
BI-TI.21-28Lambda kalkul: definice pojmů, operací, reprezentace čísel.BI-PPA.21
BI-TI.21-29Funkcionální programování, funkce vyšších řádů, Lisp: atomy, seznamy, funkce, cons buňky, rekurze, mapovací funkcionály.BI-PPA.21
BI-TI.21-30Logické programování, Prolog: fakta, pravidla, dotazy, způsob vyhodnocení dotazů, unifikace, operátor řezu.BI-PPA.21
BI-TI.21-31Heuristické prohledávání stavového prostoru, heuristiky pro odhad ceny cesty, hladové prohledávání, algoritmus A*.BI-ZUM.21
BI-TI.21-32Principy lokálního prohledávání, metody typu hill-climbing. Problém lokálního minima a metody jeho zmírnění (tabu search, simulované žíhání).BI-ZUM.21

📄 Tabulka je dostupná také v CSV (hodnoty oddělené středníkem).
🔙 Historii změn najdete na GitLabu.