Obecná informatika

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

Garantující pracoviště: Informatický ústav Univerzity Karlovy a Katedra aplikované matematiky Garant specializace: doc. Mgr. Robert Šámal, Ph.D.

Specializace obecná informatika je určena především studentům se zájmem o důkladné základy informatiky i matematiky, kteří mají v úmyslu po absolvování bakalářského studia pokračovat v navazujícím magisterském studiu. Zároveň je připraví na přímé uplatnění v praxi. Specializace dovoluje studentovi zaměřit se na algoritmy, optimalizaci, na jejich teoretické principy a také na diskrétní matematiku.

Povinné předměty studijního programu Informatika

Povinné předměty společné pro všechny specializace jsou uvedeny v úvodní části.

Povinné předměty specializace

kódPředmětKredityZSLS
NPRG005Neprocedurální programování 52/2 Z+Zk
NOPT048Lineární programování a kombinatorická optimalizace 52/2 Z+Zk
NMAI055Matematická analýza 2 52/2 Z+Zk

Povinně volitelné předměty – skupina 1

Podmínkou pro přihlášení ke státní závěrečné zkoušce je získání 30 kreditů za předměty z této skupiny.

kódPředmětKredityZSLS
NDMI084Úvod do aproximačních a pravděpodobnostních algoritmů 52/1 Z+Zk
NDMI098Algoritmická teorie her 52/2 Z+Zk
NDMI010Grafové algoritmy 32/0 Zk
NDMI012Kombinatorika a grafy 2 52/2 Z+Zk
NDMI009Základy kombinatorické a výpočetní geometrie 52/2 Z+Zk
NOPT046Diskrétní a spojitá optimalizace 52/2 Z+Zk
NMAI062Algebra 1 52/2 Z+Zk
NMAI063Algebra 2 32/0 Zk
NMAI056Matematická analýza 3 52/2 Z+Zk
NMAI042Numerická matematika 52/2 Z+Zk
NMAI073Pravděpodobnost a statistika 2 52/2 Z+Zk
NAIL063Teorie množin 32/0 Zk
NAIL124Cvičení z teorie množin 30/2 Z

Povinně volitelné předměty – skupina 2

Podmínkou pro přihlášení ke státní závěrečné zkoušce je získání 5 kreditů za předměty z této skupiny (tzn. je třeba splnit alespoň jeden předmět z této skupiny).

kódPředmětKredityZSLS
NPRG041Programování v C++ 52/2 Z+Zk
NPRG013Programování v jazyce Java 52/2 Z+Zk
NPRG035Programování v jazyce C# 52/2 Z+Zk

Povinně volitelné předměty – skupina 3

Podmínkou pro přihlášení ke státní závěrečné zkoušce je získání alespoň 45 kreditů za povinně volitelné předměty všech tří skupin. Samostatný limit pro třetí skupinu není.

kódPředmětKredityZSLS
NPFL129Úvod do strojového učení v Pythonu 52/2 Z+Zk
NPFL054Úvod do strojového učení v systému R 52/2 Z+Zk
NPGR035Strojové učení v počítačovém vidění 52/2 Z+Zk
NAIL120Úvod do umělé inteligence 52/2 Z+Zk
NPGR003Základy počítačové grafiky 52/2 Z+Zk
NPGR002Digitální zpracování obrazu 43/0 Zk
NPGR038Základy vývoje počítačových her 52/2 Z+Zk
NPFL124Zpracování přirozeného jazyka 42/1 Z+Zk
NPFL012Úvod do počítačové lingvistiky 32/0 Zk
NSWI004Operační systémy 42/1 KZ
NPRG036Datové formáty 52/2 Z+Zk
NSWI090Počítačové sítě 32/0 Zk
NSWI143Architektura počítačů 32/0 Zk
NDBI007Databázové přístupové metody 42/1 Z+Zk
NDBI040Moderní databázové systémy 52/2 Z+Zk
NSWI098Principy překladačů 62/2 Z+Zk
NPRG042Programování v paralelním prostředí 62/2 Z+Zk
NSWI142Programování webových aplikací 52/2 Z+Zk
NPRG054Vývoj vysoce výkonného software 62/2 Z+Zk
NPRG051Pokročilé programování v C++ 52/2 Z+Zk
NPRG021Pokročilé programování v jazyce Java 52/2 Z+Zk
NPRG038Pokročilé programování v jazyce C# 52/2 Z+Zk

Doporučený průběh studia

Doporučený průběh studia zahrnuje všechny povinné předměty a některé další povinně volitelné nebo volitelné předměty. Posluchač si ho musí sám doplnit dalšími povinně volitelnými a volitelnými předměty podle vlastního výběru. Povinné předměty jsou v tabulkách doporučeného průběhu studia vyznačeny tučně, povinně volitelné běžným písmem a volitelné kurzívou.

1. rok studia

Společné pro všechny specializace, viz předchozí část.

2. rok studia

kódPředmětKredityZSLS
NTIN061Algoritmy a datové struktury 2 52/2 Z+Zk
NAIL062Výroková a predikátová logika 52/2 Z+Zk
NMAI055Matematická analýza 2 52/2 Z+Zk
NDMI011Kombinatorika a grafy 1 52/2 Z+Zk
 Programování v jazyce Java/C++/C# 52/2 Z+Zk
NJAZ074Anglický jazyk pro středně pokročilé III110/2 Z
NTVY016Tělesná výchova III310/2 Z
NTIN071Automaty a gramatiky 52/2 Z+Zk
NPRG005Neprocedurální programování 52/2 Z+Zk
NOPT048Lineární programování a kombinatorická optimalizace 52/2 Z+Zk
NMAI059Pravděpodobnost a statistika 1 52/2 Z+Zk
NPRG045Ročníkový projekt 40/1 Z
NJAZ090Anglický jazyk pro středně pokročilé IV110/2 Z
NJAZ091Anglický jazyk210/0 Zk
NTVY017Tělesná výchova IV310/2 Z
 Povinně volitelný předmět skupiny 1 5 2/2 Z+Zk
 Povinně volitelné předměty    
 Volitelné předměty    

3. rok studia

kódPředmětKredityZSLS
NDBI025Databázové systémy 52/2 Z+Zk
NSZZ031Vypracování a konzultace bakalářské práce 60/4 Z
 Povinně volitelné předměty 35  
 Volitelné předměty 14  

1 Výuka anglického jazyka NJAZ070, NJAZ072, 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 NJAZ071, NJAZ073, NJAZ075, NJAZ089 s rozsahem výuky 0/4 v každém semestru.

2 Zkoušku z anglického jazyka NJAZ091 je možné absolvovat v zimním nebo v letním semestru.

3 Místo jednoho z předmětů NTVY014, NTVY015, NTVY016 a 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 bakalářského studia.

Doporučené povinně volitelné předměty

Pro přípravu ke státním zkouškám, jakož i pro další studium informatiky, doporučujeme zejména následující předměty.
kódPředmětKredityZSLS
NOPT046Diskrétní a spojitá optimalizace 52/2 Z+Zk
NDMI084Úvod do aproximačních a pravděpodobnostních algoritmů 52/1 Z+Zk
NDMI010Grafové algoritmy 32/0 Zk
NDMI009Základy kombinatorické a výpočetní geometrie 52/2 Z+Zk
NDMI012Kombinatorika a grafy 2 52/2 Z+Zk
NAIL063Teorie množin 32/0 Zk
NMAI062Algebra 1 52/2 Z+Zk

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

V první části studijních plánů programu jsou popsány okruhy státní zkoušky společné pro všechny specializace. Studenti specializace Obecná informatika budou navíc zkoušeni podle rozpisu níže z témat 1.-3. a ze dvou témat vybraných z 4.-7. Výběr těchto dvou témat student oznámí při přihlášení ke státní zkoušce. Pro každou oblast je uveden orientační přehled témat a předměty v rámci specializace, které danou oblast pokrývají. V případě tématického překryvu s požadavky ze společné části závěrečné zkoušky se v rámci specializace očekává hlubší pochopení problematiky. Detailnější přehled požadavků odrážející požadovanou hloubku znalostí bude k dispozici v elektronické podobě v dostatečném předstihu před konáním státní závěrečné zkoušky.

1. Základy sítí
Taxonomie počítačových sítí. Architektura ISO/OSI. Přehled síťového modelu TCP/IP. Směrování. Koncept adresy, portu, socketu. Architektura klient/server. Základy fungování protokolů HTTP, FTP a SMTP.

Související předměty:

Úvod do počítačových sítí (NSWI141)

2. Kombinatorika
Vytvořující funkce. Odhady faktoriálů a kombinačních čísel. Ramseyovy věty. Samoopravné kódy.

Související předměty:

Kombinatorika a grafy 1 (NDMI011)
Kombinatorika a grafy 2 (NDMI012)

3. Diferenciální a integrální počet ve více rozměrech
Riemannův integrál. Extrémy funkcí více proměnných. Metrický prostor, otevřené a uzavřené množiny, kompaktnost.

Související předměty:

Matematická analýza 2 (NMAI055)

4. Optimalizace
Mnohostěny, Minkowského-Weylova věta. Základy lineárního programování, věty o dualitě, metody řešení. Edmondsův algoritmus. Celočíselné programování. Aproximační algoritmy pro kombinatorické problémy (splnitelnost, nezávislé množiny, množinové pokrytí, rozvrhování). Použití lineárního programování pro aproximační algoritmy. Využití pravděpodobnosti při návrhu algoritmů.

Související předměty:

Lineární programování a kombinatorická optimalizace (NOPT048)
Diskrétní a spojitá optimalizace (NOPT046)

5. Pokročilé Algoritmy a datové struktury
Výpočetní model RAM. Dynamické programování. Komponenty silné souvislosti orientovaných grafů. Maximální toky: Dinicův a Goldbergův algoritmus. Aplikace toků: disjunktní cesty, párování v bipartitních grafech. Toky a cesty v celočíselně ohodnocených grafech. Vyhledávání v textu: algoritmy Knuth-Morris-Pratt, Aho-Corasicková a Rabin-Karp. Diskrétní Fourierova transformace a její aplikace. Aproximační algoritmy a schémata. Paralelní algoritmy v hradlových a komparátorových sítích.

Související předměty:

Algoritmy a datové struktury 1 (NTIN060)
Algoritmy a datové struktury 2 (NTIN061)
Grafové algoritmy (NDMI010)

6. Geometrie
Základní věty o konvexních množinách (Hellyho, Radonova, o oddělování). Minkowského věta o mřížkách. Konvexní mnohostěny (zákadní vlastnosti, V-mnohostěny, H-mnohostěny, kombinatorická složitost). Geometrická dualita. Voroného diagramy, arrangementy (komplexy) nadrovin, incidence bodů a přímek, základní algoritmy výpočetní geometrie (konstrukce arrangementu přímek v rovině, konstrukce konvexního obalu v rovině).

Související předměty:

Základy kombinatorické a výpočetní geometrie (NDMI009)

7. Pokročilá diskrétní matematika
Barvení grafů (Brooksova a Vizingova věta). Tutteova věta. Extremální kombinatorika (Turánova věta, Erdös-Ko-Radoova věta). Kreslení grafů na plochách. Množiny a zobrazení. Subvalence a ekvivalence množin. Dobré uspořádání. Axiom výběru (Zermelova věta, Zornovo lemma).

Související předměty:

Kombinatorika a grafy 2 (NDMI012)
Teorie množin (NAIL063)