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

Tato stránka vychází z podkladů pro tištěné studijní plány (tzv. Karolinku).

Garantující pracoviště: Katedra softwaru a výuky informatiky Garant studijního programu: doc. RNDr. Pavel Töpfer, CSc.

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

kód	Předmět		Kredity	ZS	LS
`NDMI002`	Diskrétní matematika		5	2/2 Z+Zk	—
`NPRG062`	Algoritmizace		4	2/1 Z+Zk	—
`NPRG030`	Programování 1		5	2/2 Z	—
`NTVY014`	Tělesná výchova I	¹	1	0/2 Z	—
	Anglický jazyk		1	0/2 Z	—
`NTIN060`	Algoritmy a datové struktury 1		5	—	2/2 Z+Zk
`NPRG031`	Programování 2		5	—	2/2 Z+Zk
`NUIN022`	Proseminář z matematiky		2	—	0/2 Z
`NMTM110`	Informační technologie pro učitele	²	3	—	1/2 KZ
`NTVY015`	Tělesná výchova II	¹	1	—	0/2 Z
	Anglický jazyk		1	—	0/2 Z

¹ Místo kteréhokoli z předmětů NTVY014, NTVY015, NTVY016, NTVY017 (ale nejvýše jednoho z nich) si lze zapsat buď Letní výcvikový kurz NTVY018, nebo Zimní výcvikový kurz NTVY019. Tyto kurzy může student absolvovat kdykoliv v průběhu studia.

² Předmět je vyučován v ZS i v LS. Pro posluchače studijního programu Informatika se zameřením na vzdělávání v libovolné kombinaci s dalším aprobačním předmětem je určena výuka v letním semestru.

2. rok studia

kód	Předmět		Kredity	ZS	LS
`NUIN021`	Algoritmy a automaty pro učitele		5	2/2 Z+Zk	—
`NSWI120`	Principy počítačů		3	2/0 Zk	—
`NSWI141`	Úvod do počítačových sítí		3	2/0 KZ	—
`NDIN011`	Aplikační software		4	2/1 Z+Zk	—
`NUIN018`	Vývoj počítačových her — pro učitele	¹	4	2/1 KZ	—
`NUIN024`	Proseminář z lineární algebry	²	2	0/2 Z	—
`NTVY016`	Tělesná výchova III	³	1	0/2 Z	—
	Anglický jazyk		1	0/2 Z	—
`NSWI170`	Počítačové systémy		5	—	2/1 Z+Zk
`NSWI177`	Úvod do Linuxu		4	—	0/2 KZ
`NDIN019`	Dětské programovací jazyky		4	—	1/2 Z
`NTVY017`	Tělesná výchova IV	³	1	—	0/2 Z
	Anglický jazyk		1	—	0/2 Z
`NJAZ091`	Anglický jazyk — zkouška pro bakaláře		1	0/0 Zk	0/0 Zk

¹ Předmět není vyučován v každém akademickém roce, je vyučován zpravidla jednou za dva roky. Zapište si jej podle toho v 2. nebo ve 3. roce svého studia.

² Předmět je určen posluchačům učitelských kombinací bez matematiky, tzn. pro kombinace aprobačních předmětů informatika-fyzika a informatika-TV. Předmět je volitelný, ale posluchačům uvedených kombinací jeho absolvování silně doporučujeme.

³ Místo kteréhokoli z předmětů NTVY014, NTVY015, NTVY016, NTVY017 (ale nejvýše jednoho z nich) si lze zapsat buď Letní výcvikový kurz NTVY018, nebo Zimní výcvikový kurz NTVY019. Tyto kurzy může student absolvovat kdykoliv v průběhu studia.

3. rok studia

kód	Předmět		Kredity	ZS	LS
`NDBI025`	Databázové systémy		5	2/2 Z+Zk	—
`NUIN018`	Vývoj počítačových her — pro učitele	¹	4	2/1 KZ	—
`NPEP301`	Úvod do psychologie		3	2/0 Zk	—
`NPEP302`	Pedagogická propedeutika	²	3	0/2 Z	—
`NAIL120`	Úvod do umělé inteligence		5	—	2/2 Z+Zk
`NSZZ031`	Vypracování a konzultace bakalářské práce		6	—	0/4 Z
`NDIN006`	Pedagogická praxe z informatiky 1		2		1 týden Z
	Povinně volitelné předměty		4

¹ Předmět není vyučován v každém akademickém roce, je vyučován zpravidla jednou za dva roky. Zapište si jej podle toho v 2. nebo ve 3. roce svého studia.

Povinně volitelné předměty (alespoň 4 kredity)

kód	Předmět	Kredity	ZS	LS
`NPEP601`	Rétorika a komunikace s lidmi I	2	0/2 Z	—
`NPEP602`	Sociální dovednosti a práce s lidmi I	2	0/2 Z	—
`NPEP603`	Rétorika a komunikace s lidmi II	2	—	0/2 Z
`NPEP604`	Sociální dovednosti a práce s lidmi II	2	—	0/2 Z

Doporučené volitelné předměty

kód	Předmět		Kredity	ZS	LS
`NUIN024`	Proseminář z lineární algebry	¹	2	0/2 Z	—
`NMIN201`	Programování 3		5	2/2 Z+Zk	—
`NPRG013`	Programování v jazyce Java		5	2/2 Z+Zk	—
`NPRG035`	Programování v jazyce C#		5	2/2 Z+Zk	—
`NAIL028`	Úvod do robotiky		5	2/2 Z+Zk	—
`NPFL012`	Úvod do počítačové lingvistiky		3	2/0 Zk	—
`NPRG036`	Datové formáty		5	2/2 Z+Zk	—
`NPED045`	Multimediální vzdělávání v pojetí psychologického výzkumu		3	1/1 KZ	—
`NPRG005`	Neprocedurální programování		5	—	2/2 Z+Zk
`NDBI046`	Úvod do datového inženýrství		5	—	2/2 Z+Zk
`NSWI090`	Počítačové sítě		3	—	2/0 Zk
`NPRG045`	Ročníkový projekt		4	—	0/1 Z

¹ Předmět je určen posluchačům učitelských kombinací bez matematiky, tzn. pro kombinace aprobačních předmětů informatika-fyzika a informatika-TV. Předmět je volitelný, ale posluchačm uvedených kombinací jeho absolvování silně doporučujeme.

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

1. rok studia

kód	Předmět	Kredity	ZS	LS
`NDMI002`	Diskrétní matematika	5	2/2 Z+Zk	—
`NPRG062`	Algoritmizace	4	2/1 Z+Zk	—
`NPRG030`	Programování 1	5	2/2 Z	—
`NTIN060`	Algoritmy a datové struktury 1	5	—	2/2 Z+Zk
`NPRG031`	Programování 2	5	—	2/2 Z+Zk
`NUIN022`	Proseminář z matematiky	2	—	0/2 Z

2. rok studia

kód	Předmět		Kredity	ZS	LS
`NUIN021`	Algoritmy a automaty pro učitele		5	2/2 Z+Zk	—
`NSWI120`	Principy počítačů		3	2/0 Zk	—
`NSWI141`	Úvod do počítačových sítí		3	2/0 KZ	—
`NDIN011`	Aplikační software		4	2/1 Z+Zk	—
`NUIN018`	Vývoj počítačových her — pro učitele	¹	4	2/1 KZ	—
`NUIN024`	Proseminář z lineární algebry	²	2	0/2 Z	—
`NSWI170`	Počítačové systémy		5	—	2/1 Z+Zk
`NSWI177`	Úvod do Linuxu		4	—	0/2 KZ
`NDIN019`	Dětské programovací jazyky		4	—	1/2 Z

¹ Předmět není vyučován v každém akademickém roce, je vyučován zpravidla jednou za dva roky. Zapište si jej podle toho v 2. nebo ve 3. roce svého studia.

² Předmět je určen posluchačům učitelských kombinací bez matematiky, tzn. pro kombinace aprobačních předmětů informatika-fyzika a informatika-TV. Předmět je volitelný, ale posluchačm uvedených kombinací jeho absolvování silně doporučujeme.

3. rok studia

kód	Předmět		Kredity	ZS	LS
`NDBI025`	Databázové systémy		5	2/2 Z+Zk	—
`NUIN018`	Vývoj počítačových her — pro učitele	¹	4	2/1 KZ	—
`NAIL120`	Úvod do umělé inteligence		5	—	2/2 Z+Zk
`NDIN006`	Pedagogická praxe z informatiky 1		2		1 týden Z

¹ Předmět není vyučován v každém akademickém roce, je vyučován zpravidla jednou za dva roky. Zapište si jej podle toho v 2. nebo ve 3. roce svého studia.

Doporučené volitelné předměty

Doporučujeme stejné volitelné předměty jako u plánu maior.

Požadavky znalostí ke státní závěrečné zkoušce z informatiky (zahájení studia v roce 2022 nebo později)

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