Obecná informatika

Garantující pracoviště: Informatická sekce
Odpovědný učitel: Doc. Mgr. Petr Kolman, Ph.D.

Studijní obor Obecná informatika nabízí následující zaměření:

Algoritmy a optimalizace
Diskrétní modely a struktury
Matematická lingvistika

Pro všechna zaměření platí stejné podmínky studia, stejné povinné a povinně volitelné předměty i stejné požadavky k bakalářské státní závěrečné zkoušce s výjimkou posledního zkušebního okruhu v požadavcích ke státní závěrečné zkoušce z informatiky.

Povinné předměty

kódPředmětKredityZSLS
NMAI054Matematická analýza I 52/2 Z+Zk
NMAI055Matematická analýza II 52/2 Z+Zk
NMAI057Lineární algebra I 52/2 Z+Zk
NMAI058Lineární algebra II 52/2 Z+Zk
NMAI062Algebra I 62/2 Z+Zk
NDMI002Diskrétní matematika 52/2 Z+Zk
NDMI011Kombinatorika a grafy I 52/2 Z+Zk
NOPT048Optimalizační metody 62/2 Z+Zk
NMAI059Pravděpodobnost a statistika 62/2 Z+Zk
NAIL062Výroková a predikátová logika 62/2 Z+Zk
NTIN071Automaty a gramatiky 62/2 Z+Zk
NTIN060Algoritmy a datové struktury I 52/2 Z+Zk
NTIN061Algoritmy a datové struktury II 62/2 Z+Zk
NPRG030Programování I 63/2 Z
NPRG031Programování II152/2 Z+Zk
NPRG005Neprocedurální programování 62/2 Z+Zk
NSWI120Principy počítačů 32/0 Zk
NSWI141Úvod do počítačových sítí 21/0 Zk
NSWI095Úvod do UNIXu 52/2 Z+Zk
NDBI025Databázové systémy 62/2 Z+Zk
NPRG045Ročníkový projekt240/1 Z
NSZZ031Vypracování a konzultace bakalářské práce 60/4 Z
NJAZ091Anglický jazyk310/0 Zk
NTVY014Tělesná výchova I 10/2 Z
NTVY015Tělesná výchova II 10/2 Z
NTVY016Tělesná výchova III 10/2 Z
NTVY017Tělesná výchova IV410/2 Z

1 Zkoušku z předmětu NPRG031 lze skládat ještě před získáním zápočtu.

2 Předmět lze zapsat v zimním i v letním semestru, standardně je zapisován v letním semestru.

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

4 Místo předmětu NTVY017 lze zapsat výcvikový kurz NTVY002 nebo NTVY003.

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í 6 kreditů za předměty z této skupiny (tzn. je třeba splnit aspoň jeden předmět z této skupiny).

kódPředmětKredityZSLS
NPRG041Programování v C++ 62/2 Z+Zk
NPRG013Java 62/2 Z+Zk
NPRG035Jazyk C# a platforma .NET 62/2 Z+Zk

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í alespoň 34 kreditů za předměty z této skupiny.

kódPředmětKredityZSLS
NMAI056Matematická analýza III 62/2 Z+Zk
NDMI012Kombinatorika a grafy II 62/2 Z+Zk
NMAI063Algebra II 32/0 Zk
NDMI009Kombinatorická a výpočetní geometrie I 62/2 Z+Zk
NDMI084Aproximační a pravděpodobnostní algoritmy 52/1 Z+Zk
NOPT046Základy spojité optimalizace 62/2 Z+Zk
NMAI042Numerická matematika 62/2 Z+Zk
NAIL063Teorie množin 32/0 Zk
NPFL063Úvod do obecné lingvistiky 52/1 Z+Zk
NPFL012Úvod do počítačové lingvistiky 32/0 Zk
NPRG051Pokročilé programování v C++ 62/2 Z+Zk
NPRG021Pokročilé programování na platformě Java 30/2 Z
NPRG038Pokročilé programování pro .NET I 62/2 Z+Zk
NSWI090Počítačové sítě I 32/0 Zk
NSWI143Architektura počítačů 32/0 Zk
NDBI007Organizace a zpracování dat I 42/1 Z+Zk
NDBI026Databázové aplikace 41/2 KZ
NSWI098Principy překladačů 42/1 Z+Zk
NPGR003Počítačová grafika I 62/2 Z+Zk
NPGR004Počítačová grafika II 52/1 Z+Zk
NPGR020Geometrie pro počítačovou grafiku 32/0 Zk
NPGR002Digitální zpracování obrazu 53/0 Zk
NPRG036Technologie XML 62/2 Z+Zk
NSWI089Ochrana informací I 32/0 Zk
NSWI015Programování v Unixu 52/1 Z+Zk
NSWI036Programování pro Windows I 32/0 Zk
NSWI099Administrace systémů Windows*62/2 Z+Zk
NSWI106Administrace Unixu 62/2 Z+Zk
NSWI045Rodina protokolů TCP/IP 32/0 Zk
NSWE002Úvod do spolehlivých systémů 11/0 Z
NPRG003Metodika programování a filozofie programovacích jazyků 32/0 Zk

* Předmět je vyučován v zimním i v letním semestru.

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

kódPředmětKredityZSLS
NMAI054Matematická analýza I 52/2 Z+Zk
NMAI057Lineární algebra I 52/2 Z+Zk
NDMI002Diskrétní matematika 52/2 Z+Zk
NPRG030Programování I 63/2 Z
NSWI120Principy počítačů 32/0 Zk
NSWI141Úvod do počítačových sítí 21/0 Zk
NTVY014Tělesná výchova I 10/2 Z
NMAI069Matematické dovednosti020/2 Z
NJAZ070Anglický jazyk110/2 Z
NMAI055Matematická analýza II 52/2 Z+Zk
NMAI058Lineární algebra II 52/2 Z+Zk
NDMI011Kombinatorika a grafy I 52/2 Z+Zk
NPRG031Programování II252/2 Z+Zk
NTIN060Algoritmy a datové struktury I 52/2 Z+Zk
NSWI095Úvod do UNIXu 52/2 Z+Zk
NTVY015Tělesná výchova II 10/2 Z
NJAZ072Anglický jazyk110/2 Z

2. rok studia

kódPředmětKredityZSLS
NTIN061Algoritmy a datové struktury II 62/2 Z+Zk
NAIL062Výroková a predikátová logika 62/2 Z+Zk
NMAI059Pravděpodobnost a statistika 62/2 Z+Zk
 Povinně volitelný předmět ze skupiny 1 62/2 Z+Zk
NMAI056Matematická analýza III 62/2 Z+Zk
NTVY016Tělesná výchova III 10/2 Z
NJAZ074Anglický jazyk110/2 Z
NOPT048Optimalizační metody 62/2 Z+Zk
NPRG005Neprocedurální programování 62/2 Z+Zk
NTIN071Automaty a gramatiky 62/2 Z+Zk
NDBI025Databázové systémy 62/2 Z+Zk
NPRG045Ročníkový projekt 40/1 Z
NTVY017Tělesná výchova IV310/2 Z
NJAZ090Anglický jazyk110/2 Z
NJAZ091Anglický jazyk410/0 Zk
 Povinně volitelné předměty ze skupiny 2    
 Volitelné předměty    

3. rok studia

kódPředmětKredityZSLS
NMAI062Algebra I 62/2 Z+Zk
NMAI063Algebra II 32/0 Zk
NSZZ031Vypracování a konzultace bakalářské práce 60/4 Z
 Povinně volitelné předměty ze skupiny 2    
 Volitelné předměty    

0 Předmět NMAI069 Matematické dovednosti je určen a vřele doporučen studentům, kteří si chtějí více osvojit základní matematické dovednosti používané v matematických předmětech na MFF. Velký důraz je kladen na osvojování si logického myšlení.

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 předmětu NPRG031 lze skládat ještě před získáním zápočtu.

3 Místo předmětu NTVY017 lze zapsat letní výcvikový kurz NTVY018 nebo zimní výcvikový kurz NTVY019; tyto kurzy je možné absolvovat kdykoli v průběhu bakalářského studia.

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

Doporučené povinně volitelné předměty pro jednotlivá zaměření

Algoritmy a optimalizace

kódPředmětKredityZSLS
NDMI084Aproximační a pravděpodobnostní algoritmy 52/1 Z+Zk
NDMI009Kombinatorická a výpočetní geometrie I 62/2 Z+Zk

Diskrétní modely a struktury

kódPředmětKredityZSLS
NDMI012Kombinatorika a grafy II 62/2 Z+Zk
NAIL063Teorie množin 32/0 Zk

Matematická lingvistika

kódPředmětKredityZSLS
NPFL063Úvod do obecné lingvistiky 52/1 Z+Zk
NPFL012Úvod do počítačové lingvistiky 32/0 Zk

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

Matematika

1. Čísla
Vlastnosti přirozených, celých, racionálních, reálných a komplexních čísel. Posloupnosti a řady čísel. Cauchyovské posloupnosti.

2. Základy diferenciálního počtu
Reálné funkce jedné reálné proměnné. Spojitost, limita funkce v bodě (vlastní i nevlastní). Některé konkrétní funkce (polynomy, racionální lomené funkce, goniometrické a cyklometrické funkce, logaritmy a exponenciální funkce). Derivace: definice a základní pravidla, věty o střední hodnotě, derivace vyšších řádů. Některé aplikace (průběhy funkcí, Taylorův polynom se zbytkem).

3. Integrál
Primitivní funkce, metody výpočtu. Určitý (Riemannův) integrál, užití určitého integrálu. Vícerozměrný integrál a Fubiniho věta.

4. Základy teorie funkcí více proměnných
Parciální derivace a totální diferenciál, věty o střední hodnotě, extrémy funkcí více proměnných, věta o implicitních funkcích.

5. Metrické prostory
Definice metrického prostoru, příklady. Spojitost, otevřené a uzavřené množiny. Kompaktnost.

6. Základní algebraické struktury
Grupa, okruh, těleso - definice a příklady. Malá Fermatova věta. Dělitelnost a ireducibilní rozklady polynomů. Rozklady polynomů na kořenové činitele pro polynom s reálnými, racionálními, komplexními koeficienty. Násobnost kořenů a jejich souvislost s derivacemi mnohočlenu.

7. Vektorové prostory
Grupa, těleso. Základní vlastnosti vektorových prostorů, podprostory, generování, lineární závislost a nezávislost. Věta o výměně. Konečně generované vektorové prostory, báze. Lineární zobrazení.

8. Skalární součin
Vlastnosti v reálném i komplexním případě. Norma. Cauchy-Schwarzova nerovnost. Kolmost. Ortogonální doplněk a jeho vlastnosti.

9. Řešení soustav lineárních rovnic
Lineární množiny ve vektorovém prostoru, jejich geometrická interpretace. Řešení soustavy rovnic je lineární množina. Frobeniova věta. Řešení soustavy úpravou matice. Souvislost soustavy řešení s ortogonálním doplňkem.

10. Matice
Matice a jejich hodnost. Operace s maticemi a jejich vlastnosti. Inverzní matice. Regulární matice, různé charakteristiky. Matice a lineární zobrazení, resp. změny souřadných soustav.

11. Determinanty
Definice a základní vlastnosti determinantu. Úpravy determinantů, výpočet. Geometrický smysl determinantu. Minory a inversní matice. Cramerovo pravidlo.

12. Vlastní čísla a vlastní hodnoty
Vlastní čísla a vlastní hodnoty lineárního operátoru, resp. čtvercové matice. Jejich výpočet, základní vlastnosti. Uvedení matice na diagonální tvar v případě různých vlastních čísel. Informace o Jordanově tvaru v obecném případě.

13. Diskrétní matematika
Uspořádané množiny. Množinové systémy, párování, párování v bipartitních grafech (systémy různých reprezentantů). Kombinatorické počítání. Princip inkluze a exkluze.

14. Teorie grafů
Základní pojmy teorie grafů, reprezentace grafu. Stromy a jejich základní vlastnosti, kostra grafu. Eulerovské grafy. Rovinné grafy, barvení grafů. Mengerova věta, dualita toků a řezů.

15. Pravděpodobnost a statistika
Náhodné jevy, podmíněná pravděpodobnost, nezávislost náhodných jevů. Náhodné veličiny, střední hodnota, rozdělení náhodných veličin, normální a binomické rozdělení. Lineární kombinace náhodných veličin. Bodové odhady, intervaly spolehlivosti, testování hypotéz, t-test, chí-kvadrát test, lineární regrese.

16. Logika
Jazyk, formule, sémantika, tautologie. Rozhodnutelnost, splnitelnost, pravdivost, dokazatelnost. Věty o kompaktnosti a úplnosti výrokové a predikátové logiky. Normální tvary výrokových formulí, prenexní tvary formulí predikátové logiky.

17. Algebra
Podgrupa, normální podgrupa, faktorgrupa, ideál. Homomorfismy grup a dalších struktur. Podílová tělesa.

Informatika

1. Automaty a jazyky
Chomského hierarchie, třídy automatů a gramatik, determinismus a nedeterminismus. Uzávěrové vlastnosti tříd jazyků.

2. Algoritmy a datové struktury
Časová složitost algoritmů, složitost v nejhorším a průměrném případě. Třídy složitosti P a NP, převoditelnost, NP-úplnost. Metoda ,,rozděl a panuj'' - aplikace a analýza složitosti, dynamické programování. Binární vyhledávací stromy, vyvažování, haldy. Hašování. Sekvenční třídění, porovnávací algoritmy, přihrádkové třídění, třídící sítě. Grafové algoritmy - prohledávání do hloubky a do šířky, souvislost, topologické třídění, nejkratší cesta, kostra grafu, toky v sítích. Tranzitivní uzávěr. Algoritmy vyhledávání v textu. Algebraické algoritmy - DFT, Euklidův algoritmus. RSA. Aproximační algoritmy.

3. Databáze
Architektury databázových systémů. Konceptuální, logická a fyzická úroveň pohledů na data. Algoritmy návrhu schémat relací, normální formy, referenční integrita. Transakční zpracování, vlastnosti transakcí, uzamykací protokoly, zablokování. ER-diagramy, metody návrhů IS. Přehled SQL.

4. Programovací jazyky
Principy implementace objektově orientovaných jazyků, běhová podpora. Oddělený překlad, sestavení, řízení překladu. Pojmy a principy objektového návrhu. Generické programování a knihovny šablony a generika, kompilační polymorfismus. Neprocedurální programování.

5. Architektura počítačů a operačních systémů
Architektury počítače. Procesory, multiprocesory. Sběrnice, protokoly. Vstupní a výstupní zařízení. Architektury OS. Vztah OS a HW, obsluha přerušení. Procesy, vlákna, plánování. Synchronizační primitiva, vzájemné vyloučení. Zablokování a zotavení z něj. Organizace paměti, alokační algoritmy. Principy virtuální paměti, stránkování, algoritmy pro výměnu stránek, výpadek stránky, stránkovací tabulky. Systémy souborů, adresářové struktury.

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

7. Optimalizační metody
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í.

8. Pro zaměření Algoritmy a optimalizace
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ů. Voroného diagramy, aranžmá (komplexy) nadrovin, incidence bodů a přímek, základní algoritmy výpočetní geometrie. Samoopravné kódy. Pravděpodobnostní metoda - příklady použití.

8. Pro zaměření Diskrétní modely a struktury
Množiny a zobrazení. Subvalence a ekvivalence množin. Dobré uspořádání. Axiom výběru (Zermelova věta, Zornovo lemma). Barvení grafů (Brooksova a Vizingova věta). Tutteova věta. Extremální kombinatorika (Ramseyovy věty, Erdös-Ko-Radoova věta). Samoopravné kódy. Pravděpodobnostní metoda - příklady použití.

8. Pro zaměření Matematická lingvistika
Formální jazyky a automaty, základní formalismy pro popis přirozených jazyků, morfologická, syntaktická a sémantická analýza přirozeného jazyka, základy teorie informace, jazykové modelování.

© 2013–2016 Univerzita Karlova, Matematicko-fyzikální fakulta. Design noBrother.
Za obsah odpovídá Studijní oddělení.