BI-TI.21
Teoretická informatika
platnost od SZZ v červnu 2024, aktualizace 31.1.2024
| Číslo TO BI | CZ verze TO | Předmět |
|---|---|---|
| BI-TI.21-1 | Př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-2 | Transformace bezkontextových gramatik a jejich normální formy. Algoritmus CYK. | BI-AAG.21 |
| BI-TI.21-3 | Implementace konečného automatu, lexikální analyzátor. | BI-AAG.21 + BI-PJP.21 |
| BI-TI.21-4 | Vyšší souvislost grafů, vrcholová, hranová a jejich vztahy, Mengerova věta. Mosty, silně souvislé komponenty orientovaného grafu a jejich hledání. Toky v sítích, 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-5 | Rovinné grafy, Eulerova formule a její důsledky, Kuratowského věta. Barevnost grafu, barevnost rovinných grafů. 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-6 | Fibonacciho haldy a složitost jejich operací amortizovaná a v nejhorším případě. (a,b)-stromy. | BI-AG2.21 |
| BI-TI.21-7 | Eulerovský tah, charakterizace eulerovských grafů, minimální pokrytí tahy. Hamiltonovská kružnice, Chvátalův uzávěr, Bondyho-Chvátalova věta. Problém obchodní cestující, aproximační algoritmus. | BI-AG2.21 |
| BI-TI.21-8 | 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í, datové a řídicí hazardy při zřetězeném zpracování instrukcí a způsoby jejich ošetření. | BI-APS.21 |
| BI-TI.21-9 | Paměťová hierarchie se skrytou pamětí (cache memory), principy lokality a fungování skryté paměti. Architektura přímé, částečně asociativní, plně asociativní skryté paměti. | BI-APS.21 |
| BI-TI.21-10 | HW podpora virtualizace hlavní paměti stránkováním, funkce MMU (Memory Management Unit) a překlad virtuálníchch adres na fyzické adres pomocí TLB (Translation Lookaside Buffer), ošetření výpadku stránky. | BI-APS.21 |
| BI-TI.21-11 | Biná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-12 | Lineární zobrazení: definice a vlastnosti (hodnost, jádro, defekt, injektivita, surjektivita), matice lineárního zobrazení. | BI-LA2.21 |
| BI-TI.21-13 | Skalární součin a norma vektoru: definice, vlastnosti a příklady. | BI-LA2.21 |
| BI-TI.21-14 | Ortogonalita 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-15 | LU rozklad matic, řešení soustavy lineárních rovnic pomocí LU rozkladu. | BI-LA2.21 |
| BI-TI.21-16 | Logický 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-17 | Teorie, model, logický důsledek. Axiomatický systém logiky. Korektnost, úplnost, bezespornost. Gödelova věta o neúplnosti. | BI-LOG.21 |
| BI-TI.21-18 | OOP polymorphismus – subtyping, generics, bounds a variance. | BI-OOP.21 |
| BI-TI.21-19 | 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.21 |
| BI-TI.21-20 | 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.21 |
| BI-TI.21-21 | Vnitřní formy programu, syntaktický strom, překlad základních jazykových konstrukcí. | BI-PJP.21 |
| BI-TI.21-22 | 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.21 |
| BI-TI.21-23 | Funkcionální programování, funkce vyšších řádů, Lisp: atomy, seznamy, funkce, cons buňky, rekurze, mapovací funkcionály. | BI-PPA.21 |
| BI-TI.21-24 | Logické programování, Prolog: fakta, pravidla, dotazy, způsob vyhodnocení dotazů, unifikace, operátor řezu. | BI-PPA.21 |
| BI-TI.21-25 | Heuristické prohledávání stavového prostoru, heuristiky pro odhad ceny cesty, hladové prohledávání, algoritmus A*. | BI-ZUM.21 |
📄 Tabulka je dostupná také v CSV (hodnoty oddělené středníkem).
🔙 Historii změn najdete na GitLabu.