Last update: Mgr. Dina Novotná Obeidová (01.08.2022)
Požadavky znalostí ke státní závěrečné zkoušce
1. Algoritmy a~datové struktury
Časová složitost algoritmů:
Definovat čas a~prostor výpočtu pro konkrétní vstup, časovou a~prostorovou složitost algoritmu (v~nejlepším, nejhorším a~průměrném případě). Vysvětlit, v~jakých jednotkách se čas a~prostor měří.
Umět stanovit časovou a~prostorovou složitost algoritmu.
Definovat asympotickou notaci (O, Omega, Theta) a~použít ji pro zápis složitosti. Vysvětlit motivaci použití asymptotiky.
Základní algoritmy s~čísly:
Vysvětlit Eukleidův algoritmus, Hornerovo schéma a~Eratosthenovo síto.
Vysvětlit algoritmy pro test prvočíselnosti, prvočíselný rozklad a~vyčíslení výrazu.
Třídění:
Vysvětlit primitivní třídicí algoritmy (Bubblesort, Insertsort apod.).
Definovat haldu a~vysvětlit, jak se použije pro třídění (Heapsort).
Vysvětlit rekurzivní třídicí algoritmy Mergesort a~Quicksort.
Srovnat složitost jednotlivých třídicích algoritmů.
Vysvětlit dolní odhad složitosti porovnávacích třídicích algoritmů a~jeho důkaz.
Vysvětlit myšlenku přihrádkového třídění a~ukázat, jak se používá pro čísla a~řetězce.
Grafové algoritmy:
Ukázat různé způsoby reprezentace grafu v~paměti.
Vysvětlit prohledávání grafů do šířky a~do hloubky. Ukázat, jak jejich složitost závisí na reprezentaci grafu. Uvést, jak se prohledáním grafu zjistí komponenty souvislosti.
Definovat topologické uspořádání orientovaného grafu a~ukázat, jak ho efektivně nalézt.
Vysvětlit algoritmy pro nejkratší cesty v~ohodnocených grafech (Dijkstrův algoritmus) a~minimální kostru grafu (Kruskalův, Jarníkův a~Borůvkův algoritmus).
Definovat tok v~síti, vysvětlit algoritmus na nalezení maximálního toku (Fordův-Fulkersonův) a~důkaz jeho korektnosti.
Datové struktury:
Definovat binární vyhledávací strom, vysvětlit operace s~nevyvažovanými stromy a~problémy s~degenerací stromu. Definovat AVL strom a~naznačit, jak pomůže.
Definovat binární haldu a~vysvětlit operace s~ní.
Vysvětlit princip hešování, demonstrovat ho na hešování s~přihrádkami a~otevřené adresaci.
Metoda ”rozděl a~panuj”:
Vysvětlit princip rekurzivního dělení problému na podproblémy.
Vysvětlit metody výpočtu složitosti rekurzivních algoritmů pomocí rekurentních rovnic, úvahou o~stromu rekurze a~kuchařkovou větou (Master theorem).
Ukázat aplikace (Mergesort, násobení dlouhých čísel, Strassenův algoritmus) a~umět spočítat jejich složitost.
Dynamické programování:
Vysvětlit princip řešení podproblémů od nejmenších k~největším.
Ukázat příklady algoritmů založených na dynamickém programování.
Algoritmy vyhledávání v~textu:
Zavést základní pojmy týkající se řetězců: abeceda, slovo, podslovo, prefix a~suffix.
Vysvětlit vyhledávání v~textu pomocí automatu (algoritmy Knuth-Morris-Pratt a~Aho-Corasicková).
Třídy složitosti:
Vysvětlit třídy rozhodovacích problémů P a~NP.
Vysvětlit převoditelnost problémů, NP-těžkost a~NP-úplnost.
Uvést příklady NP-úplných problémů a~převodů mezi nimi.
2. Programování
Programovací jazyky:
vysvětlit, k~čemu potřebujeme programovací jazyky, jaké jsou základní stavební prvky (procedurálního) programovacího jazyka
popsat rozdíl mezi staticky a~dynamicky typovanými jazyky, uvést příklady implicitní a~explicitní konverze typů, určit rozsah viditelnosti a~platnosti konkrétní proměnné v~programu
popsat různé způsoby předávání parametrů a~jejich výhody
navrhnout sadu testů pro funkci zadanou zkoušejícím
určit, které proměnné jsou primitivní (hodnotové typy) a~které objektové (referenční typy) a~vědět, k~jakým chybám může vést jejich nerozlišování (více odkazů na tentýž objekt)
určit, které proměnné v~konkrétním kódu jsou alokovány staticky, které na zásobníku a~které na haldě
navrhnout rozklad řešení úlohy zadané zkoušejícím na funkce, na moduly a~na objekty
popsat význam konstruktoru, destruktoru a~garbage-collectoru
Programování počítačových her:
popsat danou konkrétní hru z~pohledu programátora a~identifikovat v~ní jednotlivé prvky: scény, kamery, světla, herní objekty; popsat vlastnosti herních objektů týkající se jejich zobrazování a~chování (kolize, fyzika, skripty)
porozumět jednoduchému konkrétnímu skriptu pro herní objekt
vypracovat a~vysvětlit návrh pro konkrétní danou hru
3. Základy teoretické informatiky
Konečné automaty:
Definovat konečný automat, jeho výpočet a~jazyk přijímaný automatem.
Vysvětlit princip nedeterministického automatu a~lambda-přechodů. Ukázat ekvivalenci takto rozšířených automatů s~původním deterministickým automatem.
Vysvětlit regulární výrazy a~ukázat, že generují přesně regulární jazyky (Kleeneho věta).
Umět sestrojit automat a~regulární výraz pro zadaný jazyk.
Gramatiky:
Definovat regulární a~bezkontextovou gramatiku a~jazyk generovaný gramatikou.
Vysvětlit algoritmus pro příslušnost slova do bezkontextového jazyka (například algoritmus CYK).
Umět sestrojit gramatiku pro zadaný jazyk.
Turingovy stroje:
Definovat Turingův stroj, jeho výpočet a~jazyk přijímaný a~rozpoznávaný strojem.
Vysvětlit rozhodnutelné a~částečně rozhodnutelné jazyky a~vyčíslitelné funkce.
Vysvětlit univerzální Turingův stroj a~diagonální jazyk.
Ukázat příklady jazyků, které nejsou rozhodnutelné nebo částečně rozhodnutelné (problém zastavení). Ukázat, jak se může lišit rozhodnutelnost jazyka a~jeho doplňku (Postova věta).
Umět sestrojit Turingův stroj rozhodující daný jazyk.
4. Databáze a~práce s~daty
Základy reprezentace dat:
Vysvětlit rozdíl mezi informacemi a~daty.
Vysvětlit rozdíl mezi datovým modelem a~datovým formátem. Znát základní zástupce datových modelů (relační, grafový a~dokumentový) a~datových formátů (CSV, XML, JSON).
Vysvětlit pojem otevřených dat a~roli katalogů dat při vyhledávání existujících dat.
Vysvětlit co je konceptuální model a~ukázat příklad konceptuálního modelu v~podobě ER diagramu nebo UML diagramu tříd. Z~příkladu odvodit schéma relační databáze.
Jazyk SQL:
Pomocí SQL vytvořit dvě tabulky s~několika sloupci a~definovat pro ně základní integritní omezení (primární klíče, cizí klíč v~jedné tabulce na jinou tabulku) a~pomocí SQL naplnit daty.
Pomocí SQL vyfiltrovat řádky a~sloupce z~tabulek dle zadaných kritérií, pomocí SQL umět obě definované tabulky spojit.
Architektury databázových systémů:
Vysvětlit roli databázového systému v~architektuře aplikačního software.
Popsat základní architektury databázových systémů (centralizovaná databáze, distribuovaná databáze), jejich výhody a~nevýhody.
Optimalizace databází:
Vysvětlit na příkladu (např. relační databázové tabulky) co je databázový index a~k~čemu je dobrý.
Vysvětlit na příkladu normální formy v~relačním modelu dat a~k~čemu slouží při návrhu struktury relační databáze.
5. Architektury počítačových systémů a~sítí
Reprezentace dat:
Vysvětlit motivaci používání dvojkové soustavy, převádět celá čísla z~desítkové reprezentace do reprezentace s~dvojkovým doplňkem a~zpět, převádět desetinná čísla do reprezentace IEEE 754 a~zpět, na obou formátech demonstrovat omezení rozsahu a~přesnosti
Vysvětlit motivaci používání šestnáctkové soustavy, převádět celá čísla z~desítkové reprezentace do šestnáctkové soustavy a~zpět
Použít bitové operace (AND, OR, NOT, XOR, posuny) k~manipulaci hodnot bitových polí
Vysvětlit a~s~použitím tabulek převádět text do a~z~ASCII kódování, vysvětlit motivaci kódování UNICODE ve variantách UTF-8 a~UTF-16
Vysvětlit rozdíl mezi rastrovou a~vektorovou grafikou, na příkladech uvést výběr vhodné reprezentace počítačového obrazu. Vysvětlit reprezentaci barev na počítači.
Organizace a~architektura počítače:
Načrtnout strukturu počítače s~procesorem, operační pamětí, základními zařízeními a~sběrnicemi mezi nimi, správně identifikovat tyto komponenty v~reálném počítači a~vysvětlit jejich základní funkci, správně přiřadit názvy aktuálních technologií (jako PCI Express, USB, DDR)
Vysvětlit rozdíl mezi analogovým a~digitálním přenosem.
Na jednoduchých příkladech jednotek instrukcí (na úrovni základních instrukcí: load a~store, aritmetické a~bitové operace, nepodmíněný skok, podmíněné skoky) demonstrovat funkci procesoru, použít tyto instrukce k~implementaci jednoduchých konstrukcí vyššího programovacího jazyka (vyčíslení výrazu, volání funkce s~parametry a~lokálními proměnnými, cyklus s~celočíselným čítačem)
Operační systémy:
Vysvětlit základní abstrakce poskytované operačním systémem (proces a~vlákno jako abstrakce procesoru, adresový prostor jako abstrakce operační paměti, soubor jako abstrakce externí paměti, socket jako abstrakce navázaného spojení), ovladače zařízení
Vysvětlit, jakým způsobem operační systém nabízí služby (API) a~jak se rozdíly v~API odráží na přenositelnosti aplikací mezi operačními systémy
Zdůvodnit privilegovanou pozici jádra operačního systému, správně rozlišit příklady privilegovaných a~neprivilegovaných operací
Procesy a~vlákna:
Vysvětlit základní myšlenku paralelního běhu vláken a~procesů pomocí přepínání kontextu
V~sémantice prokládání instrukcí na jednoduchých příkladech demonstrovat race conditions mezi vlákny
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:
Použít rozhraní operačního systému pro přístup k~obsahu souborů (open, seek, read, write, close) v~jednoduchých programech
Vysvětlit roli standardního vstupu a~výstupu, na jednoduchých příkladech řetězení příkazů (cat, grep, cut, sort, head) demonstrovat skládání procesů a~přesměrování, napsat vlastní program vhodný pro začlenění do podobné sekvence
Elektronický podpis, šifrování, certifikáty:
Vysvětlit roli veřejného a~soukromého klíče ve vytváření elektronického podpisu
Vysvětlit význam end-to-end šifrování pro komunikaci na Internetu; popsat, jakým způsobem jsou standardně šifrované emaily, vysvětlit roli veřejného a~soukromého klíče při asymetrickém šifrování.
Vysvětlit pojmy certifikát a~certifikační autorita.
Základy fungování sítí:
Vysvětlit roli IP adresy při síťové komunikaci, důvody pro zavedení IPv6.
Vysvětlit roli doménových jmen a~způsob převodu na IP adresy.
Vysvětlit strukturu URL jako prostředku adresace služeb v~prostředí internetu
Nakreslit zjednodušené schéma komunikace v~internetu s~hlavními účastníky (klient, sekvence routerů, server) a~pomocí něj vysvětlit paketový přenos, včetně principu spolehlivého doručování paketů pomocí pozitivního potvrzování
Vysvětlit fungování statických i~dynamických HTML stránek na internetu v~krocích od zadání URL do prohlížeče až k~zobrazení HTML dokumentu (struktura URL, DNS, TCP přenos dotazu a~odpovědi, zobrazení HTML)
6. Umělá inteligence
Řešení úloh prohledáváním:
Formulovat, co je dobře definovaná úloha
Vysvětlit principy a~rozdíly stromového a~grafového prohledávání
Popsat základní algoritmy neinformovaného prohledávání (DFS, BFS, uniform-cost search)
Vysvětlit algoritmus A*, definovat přípustné a~konzistentní heuristiky a~popsat jejich vztah k~typu prohledávání
Logické uvažování:
Definovat formuli ve výrokové logice a~popsat konjunktivní a~disjunktivní normální formu
Vysvětlit pojmy model, logický důsledek a~splnitelnost
Vysvětlit algoritmus DPLL a~rezoluční metodu (rezoluční krok)
Pravděpodobnostní uvažování:
Definovat pojmy úplná sdružená distribuce, náhodná proměnná a~nezávislost
Vysvětlit Bayesovo pravidlo
Definovat Bayesovskou síť, popsat její konstrukci a~základní metody odvozování
Teorie rozhodování:
Vysvětlit pojem racionálního agenta a~formuli pro výběr akce (maximální očekávaný užitek)
Definovat Markovský rozhodovací problém (MDP) a~jeho řešení; vysvětlit Bellmanovu rovnici a~popsat metody řešení MDP
Automatické plánování:
Formulovat plánovací problém včetně definice operátoru
Popsat metody dopředného a~zpětného plánování
Hry a~teorie her:
Definovat hru dvou hráčů a~popsat algoritmy Minimax a~alfa-beta prořezávání
Vysvětlit pojmy vězňovo dilema a~Nashovo ekvilibrium
Strojové učení:
Popsat základní druhy učení (s~učitelem, bez učitele, zpětnovazební)
Definovat rozhodovací stromy a~popsat jejich konstrukci
Popsat metodu regrese
Vysvětlit koncept umělé neuronové sítě
Popsat základní techniky zpětnovazebního učení a~rozdíly mezi pasivním a~aktivním učením
|