Obecná informatika

1. Obecná informatika

Garantující pracoviště: Informatická sekce
Oborový garant: doc. Mgr. Robert Šámal, 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ód Předmět Kredity ZS LS
NMAI054 Matematická analýza I   5 2/2 Z+Zk
NMAI055 Matematická analýza II   5 2/2 Z+Zk
NMAI057 Lineární algebra I   5 2/2 Z+Zk
NMAI058 Lineární algebra II   5 2/2 Z+Zk
NMAI062 Algebra I   6 2/2 Z+Zk
NDMI002 Diskrétní matematika   5 2/2 Z+Zk
NDMI011 Kombinatorika a grafy I   5 2/2 Z+Zk
NOPT048 Lineární programování a kombinatorická optimalizace 1 6 2/2 Z+Zk
NMAI059 Pravděpodobnost a statistika   6 2/2 Z+Zk
NAIL062 Výroková a predikátová logika   6 2/2 Z+Zk
NTIN071 Automaty a gramatiky   6 2/2 Z+Zk
NTIN060 Algoritmy a datové struktury I   5 2/2 Z+Zk
NTIN061 Algoritmy a datové struktury II   6 2/2 Z+Zk
NPRG030 Programování I   6 3/2 Z
NPRG031 Programování II   5 2/2 Z+Zk
NPRG005 Neprocedurální programování   6 2/2 Z+Zk
NSWI120 Principy počítačů   3 3/0 Zk
NSWI141 Úvod do počítačových sítí   2 1/0 Zk
NSWI095 Úvod do UNIXu   5 2/2 Z+Zk
NDBI025 Databázové systémy   6 2/2 Z+Zk
NPRG045 Ročníkový projekt 2 4 0/1 Z
NSZZ031 Vypracování a konzultace bakalářské práce   6 0/4 Z
NJAZ091 Anglický jazyk 3 1 0/0 Zk
NTVY014 Tělesná výchova I 4 1 0/2 Z
NTVY015 Tělesná výchova II 4 1 0/2 Z
NTVY016 Tělesná výchova III 4 1 0/2 Z
NTVY017 Tělesná výchova IV 4 1 0/2 Z

1 Předmět NOPT048 se do akademického roku 2017/18 nazýval Optimalizační metody, jedná se o stejný předmět.

2 Předmět NPRG045 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 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.

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ód Předmět Kredity ZS LS
NPRG041 Programování v C++   6 2/2 Z+Zk
NPRG013 Java   6 2/2 Z+Zk
NPRG035 Jazyk C# a platforma .NET   6 2/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ód Předmět Kredity ZS LS
NMAI056 Matematická analýza III   6 2/2 Z+Zk
NDMI012 Kombinatorika a grafy II   6 2/2 Z+Zk
NMAI063 Algebra II   3 2/0 Zk
NDMI009 Kombinatorická a výpočetní geometrie I   6 2/2 Z+Zk
NDMI084 Úvod do aproximačních a pravděpodobnostních algoritmů   5 2/1 Z+Zk
NOPT046 Diskrétní a spojitá optimalizace   6 2/2 Z+Zk
NMAI042 Numerická matematika   6 2/2 Z+Zk
NAIL063 Teorie množin   3 2/0 Zk
NPFL054 Úvod do strojového učení   5 2/2 Z+Zk
NPFL012 Úvod do počítačové lingvistiky   3 2/0 Zk
NPFL063 Úvod do obecné lingvistiky   5 2/1 Z+Zk
NPRG051 Pokročilé programování v C++   6 2/2 Z+Zk
NPRG021 Pokročilé programování na platformě Java   6 2/2 Z+Zk
NPRG038 Pokročilé programování pro .NET I   6 2/2 Z+Zk
NSWI090 Počítačové sítě   3 2/0 Zk
NSWI143 Architektura počítačů   3 2/0 Zk
NSWI004 Operační systémy   5 2/1 Z+Zk
NDBI007 Organizace a zpracování dat I   4 2/1 Z+Zk
NDBI026 Databázové aplikace   4 1/2 KZ
NSWI098 Principy překladačů   6 2/2 Z+Zk
NPGR003 Základy počítačové grafiky   5 2/2 Z+Zk
NPGR004 Počítačová grafika II   5 2/1 Z+Zk
NPGR020 Geometrie pro počítačovou grafiku   3 2/0 Zk
NPGR002 Digitální zpracování obrazu   5 3/0 Zk
NPRG036 Technologie XML   6 2/2 Z+Zk
NSWI089 Ochrana informací I   3 2/0 Zk
NSWI015 Unix/Linux Programming in C   5 2/1 Z+Zk
NSWI036 Programování pro Windows I   3 2/0 Zk
NSWI106 Administrace Unixu   6 2/2 Z+Zk
NSWI045 Rodina protokolů TCP/IP   3 2/0 Zk
NPRG003 Metodika programování a filozofie programovacích jazyků   3 2/0 Zk
NSWI041 Úvod do softwarového inženýrství   5 2/2 Z+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ód Předmět Kredity ZS LS
NMAI054 Matematická analýza I   5 2/2 Z+Zk
NMAI057 Lineární algebra I   5 2/2 Z+Zk
NDMI002 Diskrétní matematika   5 2/2 Z+Zk
NPRG030 Programování I   6 3/2 Z
NSWI120 Principy počítačů   3 3/0 Zk
NSWI141 Úvod do počítačových sítí   2 1/0 Zk
NMAI069 Matematické dovednosti 1 2 0/2 Z
NSWI165 Počítačové dovednosti 2 1 0/1 Z
NJAZ070 Anglický jazyk pro středně pokročilé a pokročilé I 3 1 0/2 Z
NTVY014 Tělesná výchova I 5 1 0/2 Z
NMAI055 Matematická analýza II   5 2/2 Z+Zk
NMAI058 Lineární algebra II   5 2/2 Z+Zk
NDMI011 Kombinatorika a grafy I   5 2/2 Z+Zk
NPRG031 Programování II   5 2/2 Z+Zk
NTIN060 Algoritmy a datové struktury I   5 2/2 Z+Zk
NSWI095 Úvod do UNIXu   5 2/2 Z+Zk
NJAZ072 Anglický jazyk pro středně pokročilé a pokročilé II 3 1 0/2 Z
NTVY015 Tělesná výchova II 5 1 0/2 Z

2. rok studia

kód Předmět Kredity ZS LS
NTIN061 Algoritmy a datové struktury II   6 2/2 Z+Zk
NAIL062 Výroková a predikátová logika   6 2/2 Z+Zk
NMAI059 Pravděpodobnost a statistika   6 2/2 Z+Zk
  Povinně volitelný předmět ze skupiny 1   6 2/2 Z+Zk
NMAI056 Matematická analýza III   6 2/2 Z+Zk
NJAZ074 Anglický jazyk pro středně pokročilé a pokročilé III 3 1 0/2 Z
NTVY016 Tělesná výchova III 5 1 0/2 Z
NOPT048 Lineární programování a kombinatorická optimalizace   6 2/2 Z+Zk
NPRG005 Neprocedurální programování   6 2/2 Z+Zk
NTIN071 Automaty a gramatiky   6 2/2 Z+Zk
NDBI025 Databázové systémy   6 2/2 Z+Zk
NPRG045 Ročníkový projekt   4 0/1 Z
NJAZ090 Anglický jazyk pro středně pokročilé a pokročilé IV 3 1 0/2 Z
NJAZ091 Anglický jazyk 4 1 0/0 Zk
NTVY017 Tělesná výchova IV 5 1 0/2 Z
  Povinně volitelné předměty ze skupiny 2        
  Volitelné předměty        

3. rok studia

kód Předmět Kredity ZS LS
NMAI062 Algebra I   6 2/2 Z+Zk
NMAI063 Algebra II   3 2/0 Zk
NSZZ031 Vypracování a konzultace bakalářské práce   6 0/4 Z
  Povinně volitelné předměty ze skupiny 2        
  Volitelné předměty        

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

2 Předmět NSWI165 Počítačové dovednosti je určen a vřele doporučen studentům, kteří si chtějí osvojit a procvičit základní informatické úlohy související s principy fungování počítačů používané v informatických předmětech na MFF. Důraz je kladen na jasné chápání funkce počítačů v podstatných souvislostech.

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

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

5 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 jednotlivá zaměření

Algoritmy a optimalizace

kód Předmět Kredity ZS LS
NOPT046 Diskrétní a spojitá optimalizace   6 2/2 Z+Zk
NDMI084 Úvod do aproximačních a pravděpodobnostních algoritmů   5 2/1 Z+Zk
NDMI009 Kombinatorická a výpočetní geometrie I   6 2/2 Z+Zk

Diskrétní modely a struktury

kód Předmět Kredity ZS LS
NDMI012 Kombinatorika a grafy II   6 2/2 Z+Zk
NAIL063 Teorie množin   3 2/0 Zk

Matematická lingvistika

kód Předmět Kredity ZS LS
NPFL054 Úvod do strojového učení   5 2/2 Z+Zk
NPFL012 Úvod do počítačové lingvistiky   3 2/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, silná souvislost v orientovaných grafech, 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í.