Otázky B-INF Informatika

Jednooborový studijní plán

1. Lineární algebra. Operace s vektory a maticemi, vlastnosti lineárních operací a skalárního součinu. Gaussova eliminace, determinant. Vlastní čísla a vektory, jejich geometrický význam, inverzní matice, vektorové podprostory, vektorové báze, lineární transformace. (MB151)
2. Základy matematické analýzy. Relace a zobrazení, vlastnosti reálných funkcí, polynomy, spojité funkce a limity, derivace, neurčitý a určitý integrál, geometrický význam. Diferenciální počet. (IB000, MB152)
3. Kombinatorika a pravděpodobnost. Elementární kombinatorika (kombinace, permutace, variace), řešení jednoduchých kombinatorických úloh. Pravděpodobnost, podmíněná pravděpodobnost (Bayesova věta). (IB000, MB153)
4. Popisná statistika. Popisná statistika, střední hodnota, medián, rozptyl, korelace. Odhady statistik a jejich spolehlivost. Distribuční funkce, rozdělení náhodných veličin a jejich příklady. (MB153)
5. Elementární teorie čísel. Dělitelnost, Euklidův algoritmus, modulární operace, prvočíselnost a její testování, aplikace teorie čísel (RSA, DSA, lineární a polynomiální kódy). (MB154)
6. Grafy a jejich prohledávání. Typy grafů, stromy, stupně vrcholů, orientované grafy, reprezentace grafů. Algoritmy prohledávání grafu do hloubky a do šířky a jejich využití. Komponenty souvislosti. (IB000, IB002)
7. Grafové algoritmy. Ohodnocené grafy, definice nejkratší cesty, minimální kostry grafu, algoritmy pro hledání nejkratších cest (Dijkstrův, Bellman-Fordův algoritmus) a minimálních koster v grafu. (IB000, IB002)
8. Stromové datové struktury. Binární vyhledávací stromy, B-stromy, červeno-černé stromy, haldy, související operace a jejich složitost. Typické implementace, příklady použití. (IB002)
9. Návrh algoritmů. Metoda rozděl a panuj, výhody a nevýhody použití rekurze, odstranění rekurze. Vysvětlení principů a implementace řadících rekurzivních algoritmů. Vztah rekurze a matematické indukce. (IB002, IB015)
10. Funkcionální programování. Funkcionální programovací paradigma (princip výpočtu, redukční krok, redukční strategie a jejich vlastnosti, příklady). Hodnotové a funkční typy, odvození typu výrazu. Lambda funkce. Funkce vyšších řádů a jejich využití. Nepojmenované (lamda) funkce. Schopnost elementárního programování v Haskellu. (IB015)
11. Regulární jazyky. Chomského hierarchie formálních jazyků. Regulární jazyky, jejich reprezentace a převody mezi nimi. Varianty konečných automatů. Nedeterminismus a determinizace automatů. Uzávěrové vlastnosti regulárních jazyků. (IB005)
12. Bezkontextové jazyky a jejich reprezentace. Varianty zásobníkových automatů (metody akceptování, determinismus a nedeterminismus, rozšířené zásobníkové automaty). Nedeterministická syntaktická analýza. Uzávěrové vlastnosti bezkontextových jazyků. (IB005)
13. Rozhodnutelnost. Pojem algoritmického problému a algoritmu. Turingův stroj a problém zastavení. Rozhodnutelnost a částečná rozhodnutelnost, nerozhodnutelnost. Metoda redukce, diagonalizace. (IB107)
14. Složitost. Složitost algoritmu versus složitost problému. Složitostní třídy (P, NP, PSPACE) a vztahy mezi nimi, příklady problémů z jednotlivých tříd. Těžkost a úplnost problému v dané třídě, polynomiální redukce problémů, NP-úplné úlohy. (IB107)
15. Principy strojového učení. Učení s učitelem, bez učitele, vyhodnocování výsledků. Učení rozhodovacích stromů. Líné učení, metoda k nejbližších sousedů. (naivní) Bayesovský klasifikátor. Detekce anomálií. (IB031)
16. Metody strojového učení. Lineární regrese, metoda nejmenších čtverců, metoda podpůrných vektorů (SVM). Hierarchické shlukování, algoritmus k-means. (IB031)
17. Neuronové sítě. Model umělého neuronu, přenosové funkce. Vícevrstvá síť a zpětná propagace. Limity použití neuronových sítí. (IB031, PB016)
18. Umělá inteligence. Vymezení umělé inteligence, Turingův test. Prohledávání stavového prostoru - neinformované a heuristické. Problémy s omezujícími podmínkami. Hry a základní herní strategie v umělé inteligenci (minimax, alfa-beta, ohodnocovací funkce). (PB016)
19. Matematická logika. Výroková logika, predikátová logika, intenzionální logika. Splnitelnost, pravdivost, dokazatelnost. Důkazové metody, rezoluční metoda. Reprezentace a vyvozování znalostí. (IB000, PB016)

1. Strukturování a řízení běhu programu. Podprogramy, rozsahy jmen, předávání hodnot, výjimky. Objektově orientované programování. Zapouzdření, dědičnost, polymorfismus - principy, použití a implementace. Realizace v jazycích C#, C++ nebo Java (dle vlastní volby). (PB006)
2. Principy nízkoúrovňového programování. Paměťový model programu; správa paměti, dynamická alokace, práce s uživatelskými datovými strukturami. Nízkoúrovňová práce s pamětí, ukazatel, pole a ukazatelová aritmetika. Způsoby ladění programu (debugging). (PB071)
3. Architektury. Číselné soustavy, vztahy mezi soustavami, zobrazení celého čísla v počítači, aritmetika. Kódy, vnitřní, vnější, detekční a opravné. Obvody a paměti: parametry, architektura. Procesor, programování, mikroprogramování. Architektury: RISC/CISC, vyrovnávací paměti. (PB150)
4. Databáze. Relační model dat, relační schéma, klíče relačních schémat, relační algebra (projekce, selekce, agregace, přejmenování), spojování relací. Funkční závislosti, normální formy (1NF, 2NF, 3NF, Boyce-Coddova NF), vztahy mezi normálními formami. Dekompozice relačních schémat, normalizace schématu. (PB154)
5. SQL, transakce a zpracování dotazů. Syntaxe a sémantika příkazů. Příkazy pro dotazování a aktualizaci dat, agregační funkce, triggery a uložené procedury, definici dat, integritní omezení. Transakční zpracování, jeho vlastnosti. Základní principy vyhodnocování dotazů (náklady na vyhodnocení dotazu, využití indexování a hašování). (PB154)
6. Operační systémy. Architektura operačního systému, architektura jádra, základní režimy procesoru. Programovací rozhraní, knihovny. Uživatel, přístupová práva, virtualizace. Virtuální paměť, proces a stránkové tabulky. Vlákno, plánování vláken a procesů. Souběžnost, uváznutí, přidělování zdrojů. Vznik procesu a spuštění programu v systémech POSIX, copy-on-write. (PB152)
7. Souborové systémy. Blokové zařízení, bloková vrstva, I/O plánovač, RAID, šifrování disku. Obyčejné soubory, alokace volného místa, fragmentace. Adresářová struktura a její reprezentace na disku. Vstup a výstup mapovaný do paměti. (PB152)
8. Sítě. Modely vrstev počítačových sítí (ISO/OSI, TCP/IP): funkcionalita a součinnost vrstev, adresace. Fyzická vrstva, signály a jejich kódování, řízení přístupu k médiu. Propojování počítačových sítí. Síťové protokoly, přepínání a směrování, multicast. Zajištěný přenos dat, sestavení a ukončení spojení. Transportní protokoly. (PB156)
9. Síťové aplikace a bezpečnost. Základní aplikační protokoly: doručování pošty, přenos souborů, web, jmenná služba. Principy popisu a zajištění kvality služby, použití pro multimédia. Zabezpečení síťové komunikace, autentizace a šifrování, zabezpečení na jednotlivých protokolových vrstvách. (PB156)
10. Základy informační bezpečnosti. Základní bezpečnostní funkce a jejich zajištění – důvěrnost, integrita, dostupnost, nepopiratelnost původu. Kryptografická primitiva, protokoly. Řízení rizik, audit, bezpečnostní operace, standardy, hodnocení bezpečnosti. (PV080)
11. Informační bezpečnost. Řízení identity a přístupu. Ochrana soukromí – koncepty a metody. Síťové útoky. Bezpečné programování a vývoj SW. Použitelná bezpečnost. (PV080)

Studijní plán Major

• Otázky 1 až 12 z jednooborového studijního plánu.

• Otázky 1 až 11 z jednooborového studijního plánu.

Studijní plán Minor

1. Výroková logika. Syntax, sémantika, odvozovací systém výrokové logiky, důkazy ve výrokové logice, pravdivost a dokazatelnost logických formulí. (IB000)
2. Funkce a rekurze. Rekurzivní definice funkcí, rekurzivní datové typy (seznamy, stromy), funkce nad rekurzivními datovými typy. (IB114)
3. Datové struktury a jejich implementace. Abstraktní datové typy: seznam, pole, zásobník, fronta, binární strom, obecný strom, vyhledávací strom. Implementace binárních a vyhledávacích stromů a operací nad nimi. (IB114)
4. Grafy. Typy grafů, stromy, stupně vrcholů, orientované grafy, reprezentace grafů. Algoritmy prohledávání grafu do hloubky a do šířky a jejich využití. Komponenty souvislosti. (IB114)
5. Třídění. Základní algoritmy, algoritmy řazení haldou, slučováním, rozdělováním. (IB114)
6. Regulární jazyky. Regulární jazyky, regulární gramatiky, regulární výrazy, konečné automaty. Vlastnosti regulárních jazyků, vztah mezi konečnými automaty a regulárními gramatikami. (IB110)
7. Konečné automaty. Definice, konstrukce konečného automatu, minimalizace konečného automatu, převod nedeterministického konečného automatu na deterministický automat. (IB110)
8. Vyčíslitelnost. Turingův stroj jako univerzální výpočetní model. Problém zastavení. Rozhodnutelnost a částečná rozhodnutelnost, nerozhodnutelnost. Diagonalizace. (IB110)
9. Složitost. Složitost algoritmu versus složitost problému. Složitostní třídy (P, NP, PSPACE) a vztahy mezi nimi, příklady problémů z jednotlivých tříd. Těžkost a úplnost problému v dané třídě, polynomiální redukce problémů, NP-úplné úlohy. (IB110)

1. Programování. Strukturované programování v imperativním jazyce, datové a řídicí struktury programovacích jazyků, datové typy, funkce. (IB113).
2. Operační systémy. Architektury operačních systémů, rozhraní operačních systémů. Procesy, synchronizace procesů, uváznutí a metody ochrany proti uváznutí. Práce s pamětí, logický a fyzický adresový prostor, správa paměti a způsoby jejího provádění. Plánování v operačních systémech. (PB153)
3. Počítačové sítě. Topologie, přístupové metody a architektury počítačových sítí (Ethernet, Fast Ethernet, Token-ring, ATM, atd.). Bezdrátové komunikační technologie. Model OSI. Protokol TCP/IP. Propojování počítačových sítí a směrování informací. (PB156)
4. Databáze I. Relační model, relační schéma, klíče relačních schémat, integritní omezení, relační algebra, spojování relací. (PB168)
5. Databáze II. Dotazovací jazyk SQL (příkaz select, spojování relací, agregační funkce). Zpracování dotazů. Základní principy, příklad. Indexování. Transakce. Vlastnosti transakčního zpracování.
6. Softwarové inženýrství. Vývoj software. Specifikace požadavků, analýza a návrh systému, testování, verifikace a validace, provoz systému. Použití UML při vývoje software. (PB007)