Učitelství informatiky pro střední školy

Garantující pracoviště: Katedra softwaru a výuky informatiky
Oborový garant: 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

¹ 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 1. nebo ve 2. roce svého studia.

2. rok studia

¹ 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 1. nebo ve 2. roce svého studia.

Doporučené volitelné předměty

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

1. rok studia

¹ 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 1. nebo ve 2. roce svého studia.

2. rok studia

¹ 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 1. nebo ve 2. roce svého studia.

Doporučené volitelné předměty

Požadavky znalostí ke státní závěrečné zkoušce z informatiky a didaktiky informatiky (zahájení studia před rokem 2022)

Odborná témata

1. Zobrazení dat v počítači
Zobrazení celých a reálných čísel v počítači, algoritmy základních početních operací. Reprezentace znaků a řetězců. Implementace datových struktur (pole, záznamy, množiny).

2. Principy počítačů, operačních systémů a počítačových sítí
Architektury počítačů. Typické instrukce strojového kódu. Přerušovací systémy. Paměťové systémy. Sběrnice, způsob připojení a programové obsluhy typických periférií. Role a základní úkoly operačního systému, příklady konkrétních operačních systémů (Windows, Unix). Správa prostředků, algoritmy prevence uváznutí. Popis paralelismu a synchronizace procesů. Počítačové sítě, standard ISO, TCP/IP, Internet, elektronická pošta.

3. Datové a řídicí struktury programovacích jazyků (programátorský a implementační pohled)
Jednoduché a strukturované datové typy. Podprogramy, komunikace podprogramu s okolím (globální proměnné, parametry, typy předávání parametrů, moduly a separátní kompilace). Porovnání vybraných programovacích jazyků z hlediska jejich datových a řídicích struktur. Principy překladu programovacích jazyků, překlad a interpretace, podprogramy a makra. Formální popisy syntaxe programovacích jazyků.

4. Metodika programování
Vývoj metodiky programování. Strukturované programování, modulární a objektové programování, abstraktní datové typy. Událostmi řízené programy. Logické a funkcionální programování. Dětské programovací jazyky.

5. Správnost a složitost algoritmů
Částečná správnost algoritmu, konečnost algoritmu, invarianty. Časová, paměťová, asymptotická složitost algoritmu - nejhorší, nejlepší, průměrný případ (definice jednotlivých pojmů). Odhad asymptotické složitosti jednoduchých algoritmů. Časová a prostorová složitost - vztah determinismu a nedeterminismu. Polynomiální převeditelnost, P- a NP-problémy, NP-úplnost.

6. Základní programovací techniky a návrh datových struktur
Různé reprezentace abstraktních datových typů (množina, zásobník, fronta, prioritní fronta). Složitost vyhledávání, vkládání a vypouštění prvků, hledání minimálního a k-tého nejmenšího, průchod všemi prvky. Reprezentace faktorové množiny. Hashování. Reprezentace aritmetických výrazů a algoritmy pro výpočet jejich hodnoty. Obecnější metody návrhu efektivních algoritmů (metoda rozděl a panuj, dynamické programování atd.).

7. Algoritmy vnitřního a vnějšího třídění
Dolní odhady časové složitosti úlohy vnitřního třídění pro nejhorší a průměrný případ. Jednoduché algoritmy kvadratické složitosti. Třídění sléváním, heapsort, quicksort, přihrádkové třídění. Odlišnost vnějšího třídění od vnitřního třídění, základní myšlenky, přirozené slučování, polyfázové třídění.

8. Základní numerické algoritmy
Řešení soustav lineárních rovnic - metody přímé a iterační, metody řešení nelineárních rovnic. Interpolace funkcí polynomy, jiné metody aproximace funkcí. Numerická integrace.

9. Teorie automatů a jazyků
Chomského hierarchie, charakterizace jejich tříd pomocí gramatik a automatů. Různé ekvivalentní definice regulárních jazyků. Nerodova věta. Uzávěrové vlastnosti regulárních jazyků. Bezkontexové gramatiky, derivační stromy, normální tvary gramatik, zásobníkové automaty, uzávěrové vlastnosti, deterministické jazyky.

10. Kombinatorika a teorie grafů
Základní pojmy teorie grafů, různé možnosti datové reprezentace grafu. Základní kombinatorické pojmy a metody. Základní kombinatorické a grafové algoritmy (např. nejkratší cesta v grafu, minimální kostra, prohledávání grafu, určování různých typů souvislosti, acykličnost grafu, toky v sítích, maximální párování v grafech).

11. Vyčíslitelnost
Algoritmicky vyčíslitelné funkce, jejich vlastnosti, Churchova teze. Rekursivní a rekursivně spočetné množiny a jejich vlastnosti. Algoritmicky neřešitelné problémy. Gödelova věta o neúplnosti.

12. Informační systémy
Organizace souborů - sekvenční, indexsekvenční, indexované, hashovací metody, B-stromy. Databázové systémy - problematika návrhu, konceptuální, logické a fyzické schéma. Relační datový model. Pojem dotazu, dotazovací jazyky (SQL).

13. Počítačová geometrie a grafika
Algoritmy 2D grafiky: kreslení čar, vyplňování, půltónování a rozptylování barev. Barevné systémy, zobrazování barev na počítači. Transformace a projekce. 3D grafika: metody reprezentace 3D scén, zobrazovací algoritmy, výpočet viditelnosti.

14. Umělá inteligence
Heuristické metody řešení úloh. Neuronové sítě. Programování her - algoritmus minimaxu, alfa-beta prořezávání.

15. Vybrané oblasti použití počítačů
Databázové systémy, programy pro přípravu textů, programy pro přípravu prezentací, tabulkové kalkulátory, počítačová grafika a animace, formáty multimediálních souborů (grafika, audio, video). WWW - vyhledávání informací. Počítačové modelování a simulace. Kryptografie s veřejným klíčem, elektronický podpis.

Didaktická témata

Metodicky zajímavý krátký výklad jednoho z předem známých témat. Hodnotí se především metodický přístup k výkladu a vystižení podstaty problematiky.

– Vyhledávání v poli (sekvenční, binární, pomocí zarážky)

– Výpočet hodnoty polynomu Hornerovým schématem

– Generování všech permutací v lexikografickém uspořádání

– Jednoduchý třídicí algoritmus

– Quicksort

– Heapsort

– Vnější třídění

– Rekurzivní podprogramy

– Reflexívní, symetrický a tranzitivní uzávěr

– Práce s lineárním spojovým seznamem, srovnání s polem

– Průchod stromem do hloubky a do šířky (rekurze, zásobník, fronta)

– Prohledávání s návratem (backtracking)

– Vyhledávání, vkládání a vypouštění v binárním vyhledávacím stromu

– Problém stabilních manželství

– Algoritmus minimaxu

– Algoritmy vyčíslení hodnoty aritmetického výrazu

– Nalezení minimální kostry grafu

– Dijkstrův algoritmus

– Určení délky nejdelší rostoucí vybrané podposloupnosti

– Způsoby předávání parametrů procedur a funkcí

– Statické a virtuální metody a jejich srovnání

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

Odborná témata

1. Počítačová geometrie a grafika
Barvy v počítačové grafice, barevné systémy, rastrová a vektorová grafika, průhlednost, kreslicí algoritmy a anti-aliasing. Matematika pro 3D grafiku (homogenní transformace, projekce), reprezentace a zobrazení 3D scén. Principy zobrazování 3D scén na GPU (jen základy). Základy realistického renderingu, základy stínování.

2. Základy tvorby webu
Umístění stránek na internetu, zobrazení v prohlížeči, webhosting, doména; cache, cookies. Přehled základních webových technologií a příklady jejich použití (HTML5, CSS3, JavaScript, AJAX, server-side jazyky, databáze, API), responsivní layout. Přístupnost webu, SEO optimalizace. Frameworky, systémy pro správu obsahu. Statické vs. dynamické stránky, průběh zpracování formuláře. Bezpečnost webových aplikací - certifikáty, HTTP/HTTPS, same-origin policy. Digitální stopa, cookies.

3. Základy složitosti a vyčíslitelnosti
Časová a prostorová složitost – vztah determinismu a nedeterminismu. Polynomiální převeditelnost, P– a NP–problémy, NP–úplnost. Algoritmicky vyčíslitelné funkce, jejich vlastnosti, Churchova teze. Rozhodnutelné a částečně rozhodnutelné jazyky a jejich vlastnosti. Algoritmicky neřešitelné problémy.

4. Informační technologie
Ztrátová a bezztrátová komprese dat, metody a využití. Formáty multimediálních souborů (grafika, audio, video). Vyhledávání informací na webu, centralizované vyhledávače, PageRank, decentralizované vyhledávání, sítě typu P2P. Kryptografie s veřejným klíčem, elektronický podpis, kryptoměny. Neuronové sítě (základy).

Didaktická témata

Metodicky zajímavý krátký výklad některého z předem známých témat. Hodnotí se především metodický přístup k výkladu a vystižení podstaty problematiky. Student si téma připraví pro žáky druhého stupně základní školy nebo gymnázia.

Výklad pro 2. stupeň ZŠ

– Proměnná

– Podmínka

– Cyklus s pevným počtem opakování

– Cyklus s podmínkou

– Podprogram

– Dvojková soustava a její význam pro digitální svět

– O čem je „umělá inteligence“ - stručný úvod pro dvanáctileté

– Princip ukládání dat na počítači; trvalé úložiště vs. operační paměť; alokační tabulka souborů, mazání dat z počítače

– Principy fungování internetu a struktura internetu; pojmy server, router, uživatelský počítač, IP adresa, útok DoS (Denial of service)

– Posílání dat po internetu; koncepty stahování (download), nahrávání na internet (upload) a streamování

– Koncept digitální stopy a identity na internetu – pro dvanáctileté

Výklad pro gymnázium

– Základy objektově orientovaného programování, rozdíl mezi jednoduchou proměnnou a objektem, objekt a jeho vlastnosti, metody

– Vyhledávání v poli (sekvenční, binární, pomocí zarážky)

– Výpočet hodnoty polynomu Hornerovým schématem

– Generování všech permutací v lexikografickém uspořádání

– Jednoduchý třídicí (řadicí) algoritmus

– Quicksort

– Heapsort

– Rekurzivní podprogramy

– Průchod stromem do hloubky a do šířky (rekurze, zásobník, fronta)

– Prohledávání s návratem (backtracking)

– Vyhledávání, vkládání a vypouštění v binárním vyhledávacím stromu

– Algoritmus minimaxu

– Algoritmy vyčíslení hodnoty aritmetického výrazu

– Grafy a jejich reprezentace

– Nalezení minimální kostry grafu

– Dijkstrův algoritmus

– Určení délky nejdelší rostoucí vybrané podposloupnosti

– Gaussova eliminace

– Viditelnost proměnných, způsoby předávání parametrů procedur a funkcí

– Reprezentace 2D obrázků na počítači (vektor vs. rastr a důležité pojmy s tím související)

– Reprezentace barev v počítači (RGB, CMYK, HSV)

– Z čeho se skládá 3D scéna a jak se zobrazuje na GPU

– Základní formáty pro ukládání rastrových obrázků (JPEG, GIF, PNG, BMP, TIFF,...), jejich možnosti a výhody; vysvětlení principu ztrátové a bezztrátové komprese

– O čem je „umělá inteligence“ - stručný úvod pro sedmnáctileté

– Co znamená „šifrování dat“ - stručný úvod; princip šifry, podpisu, klíče, certifikátu

– Co je to operační systém; kernel, ovladače, plánovač, jádra procesoru

– Posílání emailů, vysvětlení cesty od odesílatele k příjemci, zabezpečení, spam a spamové filtry, útoky vedené pomocí emailů

– Koncept digitální stopy a identity na internetu – pro sedmnáctileté

– Zadání skupinového úkolu na téma evidence dat do sdílené tabulky (úlohu vymyslí student)

– Vysvětlení pojmu informační systém na jednoduchém konkrétním příkladu

– Pojem dotazu v relační databázi, dotazovací jazyky typu SQL

– Návrh počítačové hry: sestavení návrhu nějaké (obecně známé) hry