|
|
|
||
|
Last update: Mgr. Dina Novotná Obeidová (17.08.2021)
Požadavky znalostí ke státní závěrečné zkoušce
1. ALGORITMY A DATOVÉ STRUKTURY
Časová složitost algoritmů: čas a~prostor výpočtu pro konkrétní vstup, časová a~prostorová složitost algoritmu, složitost v~nejlepším, nejhorším a~průměrném případě, asymptotická notace. Třídy složitosti: třídy P a~NP, převoditelnost problémů, NP-těžkost a~NP-úplnost, příklady NP-úplných problémů a~převodů mezi nimi. Metoda "rozděl a~panuj": princip rekurzivního dělení problému na podproblémy, výpočet složitosti pomocí rekurentních rovnic, kuchařková věta (Master theorem), aplikace (Mergesort, násobení dlouhých čísel, Strassenův algoritmus). Dynamické programování. Binární vyhledávací stromy: definice vyhledávacího stromu, operace s~nevyvažovanými stromy, AVL stromy (jen definice). Haldy: binární halda. Hešování: hešování s~přihrádkami, otevřená adresace. Třídění: primitivní třídicí algoritmy (Bubblesort, Insertsort apod.), třídění haldou (Heapsort), Quicksort, dolní odhad složitosti porovnávacích třídicích algoritmů, přihrádkové třídění čísel a~řetězců. Grafové algoritmy: prohledávání do šířky a~do hloubky, detekce komponent souvislosti, topologické třídění orientovaných grafů, nejkratší cesty v~ohodnocených grafech (Dijkstrův algoritmus), minimální kostra grafu (Kruskalův, Jarníkův a~Borůvkův algoritmus), toky v~sítích (algoritmus Fordův-Fulkersonův). Algoritmy vyhledávání v~textu. Algebraické algoritmy: Eukleidův algoritmus.
2. PROGRAMOVACÍ JAZYKY
Typické prostředky programovacích jazyků. Pojmy a~principy objektového návrhu: třídy, rozhraní, metody, atributy, dědičnost, vícenásobná dědičnost a~její problémy, polymorfismus, primitivní typy vs. objekty (implementace primitivních typů, paměťová reprezentace složených typů a~objektů), implementace virtuálních metod (tabulka virtuálních metod), životnost objektů (alokace objektů statická, na zásobníku, na haldě), konstruktory, explicitní delete/dispose, garbage collector, výjimky (šíření a~odchytávání výjimek: try-catch-finally). Oddělený překlad, sestavení, řízení překladu: kompilace vs. interpretace, role sestavení. Neprocedurální programování, logické programování.
3. AUTOMATY A JAZYKY
Regulární jazyky: konečný automat, jazyk přijímaný konečným automatem, deterministický, nedeterministický, lambda přechody, regulární výrazy, Kleeneho věta, iterační (pumping) lemma pro konečné automaty, Nerodova věta, regulární gramatiky. Bezkontextové jazyky: bezkontextová gramatika, jazyk generovaný gramatikou, zásobníkový automat, třídy jazyků přijímaných nedeterministickými a~deterministickými zásobníkovými automaty. Turingův stroj: gramatika typu 0, diagonální jazyk, univerzální jazyk. Chomského hierarchie: určení ekvivalence či inkluze tříd jazyků generovaných výše uvedenými automaty a~gramatikami, schopnost zařazení konkrétního jazyka do Chomského hierarchie (zpravidla sestrojení odpovídajícího automatu či gramatiky a~důkaz iteračním lemmatem, že jazyk není v~nižší třídě).
4. DATABÁZE Podstata a~architektury databázových systémů. Konceptuální, logická a~fyzická úroveň pohledů na data, B-stromy a~jejich varianty. Relační datový model, relační algebra, normální formy, referenční integrita. Základy jazyka SQL. Transakční zpracování, vlastnosti transakcí.
5. ARCHITEKTURY POČÍTAČŮ, OPERAČNÍCH SYSTÉMŮ A SÍTÍ
Reprezentace dat: kódování a~způsob uložení dat v~paměti, bitové operace a~jejich využití. Organizace počítače: von Neumannova a~harvardská architektura, operační a~sekundární paměti, adresové prostory, vstupně/výstupní zařízení. Architektura počítače: typické architektury, instrukce procesoru, běžné konstrukce vyššího programovacícho jazyka a~jejich reprezentace pomocí instrukcí, základní představa o~SMP multiprocesoru se sdílenou pamětí. Operační systémy: boot počítače a~operačního systému, jádro OS, ovladače zařízení, privilegovaný a~neprivilegovaný režim CPU, rozhraní mezi OS a~programovacím jazykem, správa uživatelů a~jejich oprávnění. Rozhraní HW a~OS: ovladače zařízení a~driver stack, obsluha přerušení na úrovni CPU a~OS, výjimky procesoru a~jejich obsloužení a~vazba na runtime programovacího jazyka. Procesy a~vlákna: kontext procesu a~vlákna, kooperativní a~preemptivní multitasking, plánování, typické stavy vlákna, aktivní vs. pasivní čekání. Race condition, kritická sekce, vzájemné vyloučení, synchronizační primitiva, deadlock a~livelock (znalost konceptu). Typická rozhraní pro přístup a~práci se soubory a~sockety, file descriptory, použití souborového API pro přístup k~zařízením v~OS, standardní vstup a~výstup a~jejich přesměrování, roury (pipes) jako meziprocesová komunikace. Bezpečnost, autentifikace, autorizace, přístupová práva. ISO/OSI vrstevnatá architektura sítí. TCP/IP. Spojované a~nespojované služby, spolehlivost, zabezpečení protokolů.
|