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

Studijní plány oblasti vzdělávání INFORMATIKA

Bakalářské studium od akad. roku 2019/20

Garant studijního programu: doc. RNDr. Ondřej Čepek, Ph.D.

1. Základní informace

Studijní specializace

Bakalářský studijní program Informatika má společný první ročník a od druhého ročníku se dělí na šest specializací:

Obecná informatika
Programování a vývoj software
Systémové programování
Databáze a web
Umělá inteligence
Počítačová grafika, vidění a vývoj her

Specializaci si studenti vybírají v souladu se studijními předpisy v průběhu druhého ročníku studia.

Studijní plány

Studium v jednotlivých specializacích je určeno studijními plány. Studijní plány určují skladbu povinných a povinně volitelných předmětů a dále požadavky ke státní zkoušce. Povinně volitelné předměty jsou pro každou specializaci rozděleny do několika skupin. Kromě celkového minimálního počtu kreditů za všechny povinně volitelné předměty může být také pro některé skupiny těchto předmětů určen minimální počet kreditů, který je z dané skupiny třeba získat před přihlášením se ke státní zkoušce. Vedle povinných předmětů a předepsaného množství povinně volitelných předmětů si může každý student podle vlastního výběru zapisovat další předměty vyučované na naší fakultě, v případě zájmu i na jiných fakultách naší univerzity (tzv. volitelné předměty). V souladu s platnou akreditací jsou některé povinně volitelné předměty vyučovány v některých akademických rocích pouze v angličtině.

Všech šest specializací má rozsáhlou společnou část tvořenou povinnými předměty pokrývajícími základy matematiky, teoretické informatiky, programování a softwarových systémů. Většina těchto povinných předmětů spadá do prvního ročníku studia, který je pro celý studijní program Informatika společný. Níže uvedený doporučený průběh studia v 1. ročníku zahrnuje všechny povinné předměty pro 1. ročník vyznačené tučně a několik volitelných předmětů vyznačených kurzívou.

1. rok studia

kódPředmětKredityZSLS
NPRG062Algoritmizace 42/1 Z+Zk
NPRG030Programování 1 52/2 Z
NSWI120Principy počítačů 32/0 Zk
NSWI141Úvod do počítačových sítí 32/0 KZ
NDMI002Diskrétní matematika 52/2 Z+Zk
NMAI057Lineární algebra 1 52/2 Z+Zk
NTVY014Tělesná výchova I110/2 Z
NMAI069Matematické dovednosti220/2 Z
NJAZ070Anglický jazyk pro středně pokročilé I310/2 Z
NTIN060Algoritmy a datové struktury 1 52/2 Z+Zk
NPRG031Programování 2 52/2 Z+Zk
NSWI170Počítačové systémy 52/2 Z+Zk
NSWI177Úvod do Linuxu 41/2 KZ
NMAI054Matematická analýza 1 52/2 Z+Zk
NMAI058Lineární algebra 2 52/2 Z+Zk
NTVY015Tělesná výchova II110/2 Z
NJAZ072Anglický jazyk pro středně pokročilé II310/2 Z

1 Místo jednoho z předmětů NTVY014 a NTVY015 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.

2 Předmět NMAI069 Matematické dovednosti je určen a vřele doporučen studentům, kteří si chtějí osvojit a procvičit základní matematické dovednosti používané v matematických předmětech na MFF. Důraz je kladen na korektní matematické vyjadřování a základní důkazové techniky.

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

Menší počet povinných předmětů společných pro všechny specializace pak spadá do 2. a 3. ročníku. Níže je jejich seznam doplněný o volitelné předměty výuky anglického jazyka.

Společné povinné předměty v 2. a 3. roku studia a výuka angličtiny

kódPředmětKredityZSLS
NTIX061Algoritmy a datové struktury 2 52/2 Z+Zk
NDBX025Databázové systémy 52/2 Z+Zk
NDMX011Kombinatorika a grafy 1 52/2 Z+Zk
NAIX062Výroková a predikátová logika 52/2 Z+Zk
NTVY016Tělesná výchova III410/2 Z
NJAZ074Anglický jazyk pro středně pokročilé III510/2 Z
NTIX071Automaty a gramatiky 52/2 Z+Zk
NMAX059Pravděpodobnost a statistika 1 52/2 Z+Zk
NPRG045Ročníkový projekt640/1 Z
NSZZ031Vypracování a konzultace bakalářské práce 60/4 Z
NTVY017Tělesná výchova IV410/2 Z
NJAZ090Anglický jazyk pro středně pokročilé IV510/2 Z
NJAZ091Anglický jazyk710/0 Zk

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

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

6 Předmět NPRG045 lze zapsat v ZS i v LS, standardně je zapisován v LS.

7 Povinnou zkoušku z anglického jazyka NJAZ091 je možné absolvovat jak v ZS tak v LS.

Pro jednotlivé specializace jsou předepsány další povinné předměty a skupiny povinně volitelných předmětů. Detailní studijní plány pro jednotlivé specializace jsou uvedeny v dalším textu.

Doporučený průběh studia v 2. a 3. roku studia

Doporučený průběh studia je pro každou specializaci vypracován tak, aby na sebe povinné předměty navazovaly, aby student získal včas kredity potřebné pro zápis do dalšího úseku studia a aby včas splnil podmínky pro přihlášení se ke státní zkoušce. Většina povinných předmětů je v doporučeném průběhu studia zařazena do 1. a 2. ročníku studia a jenom minimum z nich je ponecháno do 3. ročníku, ve kterém je větší prostor ponechán na předměty povinně volitelné a volitelné. Doporučený průběh studia je podporován také při tvorbě celofakultního rozvrhu. Doporučené průběhy studia pro jednotlivé specializace jsou uvedeny v další části textu u popisu specializací.

Zaměření

Některé specializace se dále člení na zaměření. Jednotlivá zaměření téže specializace se od sebe liší požadavky posledního okruhu bakalářské státní zkoušky z informatiky. Posluchač má sám možnost přizpůsobit výběr svých povinně volitelných a volitelných předmětů tomu, v jakém zaměření bude studium končit a jaké odborné znalosti k tomu bude potřebovat. Volbu svého zaměření oznámí s přihláškou k bakalářské státní závěrečné zkoušce.

Státní závěrečná zkouška a ukončení studia

Státní závěrečná zkouška se skládá ze dvou částí:

obhajoba bakalářské práce
zkouška z matematiky a informatiky

Každá část státní závěrečné zkoušky je hodnocena známkou. Na základě obou známek je pak určena celková známka státní závěrečné zkoušky. Ke každé části státní závěrečné zkoušky se posluchač může přihlásit samostatně. Studium je úspěšně zakončeno úspěšným absolvováním obou částí. Při neúspěchu opakuje student ty části státní závěrečné zkoušky, ve kterých neuspěl. Opakovat část státní závěrečné zkoušky lze nejvýše dvakrát.

Podmínky pro přihlášení ke státní závěrečné zkoušce nebo její části jsou následující:
získání alespoň 180 kreditů
splnění všech povinných předmětů zvolené specializace
splnění povinně volitelných předmětů zvolené specializace ve stanoveném rozsahu
odevzdání vypracované bakalářské práce ve stanoveném termínu (pro přihlášení k obhajobě bakalářské práce).

Bakalářská práce je zadávána zpravidla na počátku 3. ročníku. Typicky má charakter softwarového díla, které může navazovat na ročníkový projekt (viz studijní plány), nebo odborné teoretické práce. Doporučujeme vybírat si téma především z nabídky pracoviště garantujícího zvolenou specializaci; v případě zájmu o téma z nabídky jiného pracoviště nebo o téma vlastní důrazně doporučujeme konzultovat vhodnost tématu s garantem specializace.

Seznam požadavků ke zkouškám z matematiky a informatiky je rozdělen na část společnou pro všechny specializace a na část specializační. Seznam společných požadavků je uveden níže pod tímto odstavcem, specializační seznamy požadavků jsou specifikovány v textex věnovaných studijním plánům jednotlivých specializací.

Požadavky znalostí ke státní závěrečné zkoušce společné pro všechny specializace

Matematika

1. Základy diferenciálního a integrálního počtu
Posloupnosti reálných čísel a jejich vlastnosti (vlastnosti limit a aritmetických operací). Reálné funkce jedné reálné proměnné. Spojitost, limita funkce v bodě (vlastní i nevlastní). Derivace: definice a základní pravidla. Některé aplikace (průběhy funkcí, Taylorův polynom se zbytkem). Primitivní funkce (definice, jednoznačnost, existence), metody výpočtu.

2. Algebra a lineární algebra
Grupy a podgrupy, definice, příklady, komutativita. Tělesa - definice, charakteristika tělesa, konečná tělesa. Vektorové prostory a podprostory, jejich vlastnosti, základní pojmy (lineární kombinace, lineární obal, generátory, lineární závislost a nezávislost, báze, dimenze, souřadnice) a jejich použití. Praktická dovednost testování lineární závislosti a nezávislosti, nalezení báze, určení dimenze atp. Skalární součin a jeho vlastnosti. Norma a vztah se skalárním součinem, příklady. Kolmost, ortonormální báze, její vlastnosti a použití (např. pro nalezení souřadnic a pro projekci). Soustavy lineárních rovnic a množina řešení. Metody řešení, Gaussova a Gaussova-Jordanova eliminace, odstupňovaný tvar matice a jeho jednoznačnost (bez důkazu). Matice a operace s maticemi (součet, součin, transpozice atp.), interpretace součinu matic pomocí skládání lineárních zobrazení. Hodnost matice a její transpozice. Vlastní čísla a vlastní vektory matice a jejich geometrický význam a vlastnosti, vícenásobná vlastní čísla, spektrální poloměr. Charakteristický polynom, vztah vlastních čísel s kořeny polynomů.

3. Diskrétní matematika
Relace, vlastnosti binárních relací (reflexivita, symetrie, antisymetri, tranzitivita). Ekvivalence a rozkladové třídy. Částečná uspořádání, základní pojmy (minimální a maximální prvky, nejmenší a největší prvky, řetězec, antiřetězec), výška a šířka částečně uspořádané množiny a věta o jejich vztahu (o dlouhém a širokém). Funkce, typy funkcí (prostá, na, bijekce) a počty různých typů funkcí mezi dvěma konečnými množinami. Permutace a jejich základní vlastnosti (počet, pevný bod atd.). Kombinační čísla a vztahy mezi nimi, binomická věta a její aplikace. Princip inkluze a exkluze, obecná formulace (a důkaz) a použití (problém šatnářky, Eulerova funkce pro počet dělitelů, počet surjekcí apod.). Hallova věta o systému různých reprezentantů a její vztah k párování v bipartitním grafu, princip důkazu a algoritmické aspekty (polynomiální algoritmus pro nalezení SRR).

4. Teorie grafů
Základní pojmy (graf, vrcholy a hrany, izomorfismus grafů, podgraf, okolí vrcholu a stupeň vrcholu, doplněk grafu, bipartitní graf), základní příklady grafů (úplný graf a úplný bipartitní graf, cesty a kružnice). Souvislost grafů, komponenty souvislosti, vzdálenost v grafu. Stromy, definice a základní vlastnosti (existence listů, počet hran stromu), ekvivalentní charakteristiky stromů. Rovinné grafy, definice a zákaldní pojmy (rovinný graf a rovinné nakreslení grafu, stěny), Eulerova formule a maximální počet hran rovinného grafu (důkaz a použití). Barevnost grafů, definice dobrého obarvení, vztah barevnosti a klikovosti grafu. Hranová a vrcholová souvislost grafů, hranová a vrcholová verze Mengerovy věty. Orientované grafy, silná a slabá souvislost. Toky v sítích. Definice sítě a toku v ní, existence maximálního toku (bez důkazu), princip hledání max. toku v síti s celočíselnými kapacitami (např. pomocí Ford-Fulkersonova algoritmu).

5. Pravděpodobnost a statistika
Náhodné jevy, podmíněná pravděpodobnost, nezávislost náhodných jevů - definice uvedených termínů, Bayesův vzorec, aplikace. Náhodné veličiny, střední hodnota, rozdělení náhodných veličin, geometrické, binomické a normální rozdělení. Lineární kombinace náhodných veličin - linearita střední hodnoty, aplikace. Bodové odhady, intervaly spolehlivosti, testování hypotéz.

6. Logika
Syntaxe - znalost a práce se základními pojmy syntaxe výrokové a predikátové logiky (jazyk, otevřená a uzavřená formule apod.). Normální tvary výrokových formulí, prenexní tvary formulí predikátové logiky - znalost základních normálních tvarů (CNF, DNF, PNF), převody na normální tvary, použití pro algoritmy (SAT, rezoluce). Sémantika, pravdivost, lživost, nezávislost formule vzhledem k teorii, splnitelnost, tautologie, důsledek, pojem modelu teorie, extenze teorií.

Informatika

1. 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, regulární gramatiky. Bezkontextové jazyky: bezkontextová gramatika, jazyk generovaný gramatikou, zásobníkový automat, třída jazyků přijímaných 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ě).

2. Algoritmy a datové stuktury
Časová složitost algoritmů: čas a prostor výpočtu pro konkrétní vstup, časová a prostorová složitost algoritmu, měření velikosti dat, 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). Binarní 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 a Bellmanův-Fordův algoritmus), minimální kostra grafu (Jarníkův a Borůvkův algoritmus), toky v sítích (algoritmus Ford-Fulkerson). Algebraické algoritmy: Euklidův algoritmus.

3. Programovací jazyky
Pojmy a principy objektového návrhu: třídy, rozhraní, metody, atributy, dědičnost (viditelnost elementů, namespaces, dělení do balíčků/modulů), vícenásobná dědičnost a její problémy (mechanismy k řešení problémů podle jazyka, vícenásobná a virtuální dědičnost v C++, jednoduchá dedičnost a defaultní metody v Javě), implementace rozhraní (interface), polymorfismus (statický vs. dynamický polymorfismus), funkcionální prvky objektových jazyků (funktory, lambdy, podpora standardních knihoven). Implementace objektových jazyků: základní objektové koncepty v konkrétním jazyce (Java, C++, C#), 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 a inicializace objektů (statická, na zásobníku, na haldě), konstruktory, volání zděděných konstruktorů, likvidace objektů, explicitní delete/dispose, garbage collector, automatická likvidace, shared_ptr/unique_ptr, destruktory, finalizátory), vlákna a podpora synchronizace (implementace vláken, základní konstrukce pro synchronizaci, datové typy s atomickým přístupem), ošetření chyb, výjimky (šíření a odchytávání výjimek: try-catch-finally, práce s prostředky: try-with-resources (Java), RAII (C++), using (C#)). Oddělený překlad, sestavení, řízení překladu: kompilace vs. interpretace, role sestavení, JIT.

4. Architektura počítačů a operačních systémů
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.