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

Doporučený průběh studia

Předměty povinné ke státní závěrečné zkoušce 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.

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

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