Informatika se zaměřením na vzdělávání

Doporučený průběh studia

Předměty povinné jsou vytištěny tučně, povinně volitelné předměty normálním písmem, doporučené volitelné předměty kurzívou.

Hlavní studijní plán (maior)

1. rok studia

¹ Místo jednoho z předmětů NTVY014, NTVY015, NTVY016, NTVY017 je možné si zapsat letní výcvikový kurz NTVY018 nebo zimní výcvikový kurz NTVY019. Tyto kurzy může student absolvovat kdykoli v průběhu studia.

² Výuka anglického jazyka NJAZ070, NJAZ072 v rozsahu 0/2 v každém semestru je určena pro středně pokročilé a pokročilé. Pro začátečníky a mírně pokročilé jsou určeny předměty NJAZ071, NJAZ073 s rozsahem výuky 0/4 v každém semestru.

2. rok studia

¹ Místo jednoho z předmětů NTVY014, NTVY015, NTVY016, NTVY017 je možné si zapsat letní výcvikový kurz NTVY018 nebo zimní výcvikový kurz NTVY019. Tyto kurzy může student absolvovat kdykoli v průběhu studia.

² Výuka anglického jazyka NJAZ074, NJAZ090 v rozsahu 0/2 v každém semestru je určena pro středně pokročilé a pokročilé. Pro začátečníky a mírně pokročilé jsou určeny předměty NJAZ075, NJAZ089 s rozsahem výuky 0/4 v každém semestru.

³ Povinnou zkoušku z anglického jazyka NJAZ091 je možné absolvovat v ZS nebo v LS.

⁴ Posluchači, kteří absolvovali předmět NSWI177 Úvod do Linuxu v 1. roce svého studia v akademickém roce 2019/20, si místo něj zapíší v akademickém roce 2020/21 předmět NDIN019 Dětské programovací jazyky, který byl ve vzorovém průchodu přesunut do 1. ročníku.

3. rok studia

Povinně volitelné předměty (minimálně 4 kredity)

Doporučené volitelné předměty

Přidružený studijní plán (minor)

1. rok studia

2. rok studia

^* Posluchači, kteří absolvovali předmět NSWI177 Úvod do Linuxu v 1. roce svého studia v akademickém roce 2019/20, si místo něj zapíší v akademickém roce 2020/21 předmět NDIN019 Dětské programovací jazyky, který byl ve vzorovém průchodu přesunut do 1. ročníku.

3. rok studia

Doporučené volitelné předměty

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ů.