Obsah a organizácia záverečného konania pre I. stupeň štúdia študijného programu v odbore 9.2.1. Informatika na FMFI UK

Doc. RNDr. Daniel Olejár, PhD., garant študijného programu

Úvod

Obsah štátnej skúšky

• Matematická analýza (1) a (2)
• Algebra (1) a (2)
• Úvod do diskrétnych štruktúr
• Úvod do matematickej logiky
• Úvod do kombinatoriky a teórie grafov

• Princípy počítačov
• Programovanie (1)-(3)
• Systémové programovanie
• Operačné systémy
• Počítačové siete (1)
• Úvod do databázových systémov
• Formálne jazyky a automaty (1)
• Algoritmy a dátové štruktúry
• Tvorba efektívnych algoritmov
• Princípy tvorby softvéru

Matematická analýza

1. Limita reálnej funkcie jednej reálnej premennej (definícia vlastnej a nevlastnej limity, vety o výpočte limít, číslo e, Cauchyho-Bolzanovo kritérium konvergencie postupnosti).
2. Spojité funkcie a ich základné vlastnosti (definícia spojitej funkcie, Darbouxova vlastnosť, vlastnosti spojitých funkcií na uzavretých ohraničených intervaloch).
3. Derivácia funkcie a jej využitie na vyšetrovanie priebehu funkcie (definícia derivácie, vety o výpočte derivácií, vety o strednej hodnote, derivácie vyšších rádov, vyšetrovanie monotónnosti, extrémov a konvexnosti pomocou derivácií).
4. Primitívna funkcia a neurčitý integrál (definícia neurčitého integrálu, metóda per partes a substitúcie, univerzálna trigonometrická substitúcia).
5. Riemannov určitý integrál (definícia riemannovsky integrovateľnej funkcie, integrovateľnosť monotónnych a spojitých funkcií, Newtonov-Leibnizov vzorec, integrál ako funkcia hranice).
6. Číselné rady (definícia číselného radu, Cauchyho-Bolzanovo kritérium konvergencie radu, kritériá pre konvergenciu radov s nezápornými členmi, Leibnizovo kritérium, relatívne a absolútne konvergentné rady, prerovnanie radov).
7. Mocninové a Taylorove rady (definícia mocninového radu, polomer a interval konvergencie, derivovanie a integrovanie mocninových radov, definícia Taylorovho radu, pojem analytickej funkcie).

Algebra

1. Vektorové priestory, lineárne zobrazenia [priestor, podpriestor, lineárna závislosť, báza a dimenzia. Steinitzova veta, súčty podpriestorov, lineárne zobrazenia, kompozícia lineárnych zobrazení, inverzné lineárne zobrazenia, matica lineárneho zobrazenia, jadro a obraz lineárneho zobrazenia]
2. Matice a riešenia lineárnych rovníc nad poľom F [matice, operácie s maticami (násobenie, sčítanie), elementárne riadkové operácie, trojuholníkový a redukovaný trojuholníkový tvar matice, systémy lineárnych rovníc nad poľom F, množina riešení homogénnych a nehomogénnych systémov lineárnych rovníc, existencia a tvary riešení]
3. Determinanty [Determinant lineárneho zobrazenia a matice. Vlastnosti determinantov. Výpočty determinantov a ich použitie pri riešení lineárnych rovníc a hľadaní inverznej matice]
4. Grupy [grupy, podgrupy, izomorfizmus a homomorfizmus grúp, cyklické grupy (s klasifikáciou) a ich podgrupy, grupy permutácií, rozklad grupy podľa podgrupy, Lagrangeova veta, homomorfizmus a izomorfizmus grúp, normálna podgrupa, faktorizácia grupy podľa podgrupy]
5. Okruhy [základné vlastnosti operácií v okruhoch, podokruh, ideál (hlavný, maximálny, prvoideál), faktorizácia okruhu podľa ideálu, vzťah medzi výsledkom faktorizácie a vlastnosťami ideálu, podľa ktorého sa faktorizuje, obor integrity a veta o podielovom poli]
6. Okruhy hlavných ideálov [existencia jednotky v okruhu, najväčší spoločný deliteľ, vlastnosti deliteľnosti, ireducibilné prvky, veta o jednoznačnom rozklade]
7. Okruhy polynómov [pojem algebraického a transcendentného prvku pre daný okruh, okruh polynómov R[x], okruh polynómov F[x] nad poľom F ako okruh hlavných ideálov, veta o jednoznačnom rozklade polynómov nad daným poľom, substitučný homomorfizmus (veta o substitúcii), korene, viacnásobné korene, Hornerova schéma]
8. Rozšírenia polí [jednoduché, viacnásobné a konečné rozšírenie poľa, minimálny polynóm daného algebraického prvku]
9. Konečné polia [charakteristika poľa]

Úvod do diskrétnych štruktúr

1. Základy matematickej logiky [logické operácie, formuly, výrokové funkcie, kvantifikácia výrokov, tautógia, kontradikcia]
2. Matematický dôkaz [logický dôsledok, základné typy matematickych dôkazov]
3. Intuitívny pojem množiny [základné pojmy a označenia, množinové operácie. Množinové identity]
4. Karteziánsky súčin množín a jeho vlastnosti
5. Relácie [skladanie relácií, inverzná relácia, relácie na množinách. Relácia ekvivalencie, rozklad množiny. Tranzitívny uzáver relácie, reflexívno-tranzítivny uzáver. Definicia, vlastnosti.]
6. Čiastočné usporiadanie a usporiadanie množiny (ostré a neostré) [Definícia, vlastnosti usporiadania, minimálny, maximálny, prvý a posledný prvok množiny]
7. Zobrazenia
8. Mohutnosť množiny [Základné vlastnosti mohutnosti a nerovnosti. Počítanie s mohutnosťami, súčet, súčin a mocnina.]
9. Cantor-Bernsteinova veta a jej dôsledky
10. Konečné a nekonečné množiny
11. Spočítateľné a nespočítateľné množiny
12. Aritmetika celých nezáporných čísel

Úvod do matematickej logiky

1. Výstavba logickej teórie [Jazyk logiky, formálne systémy logiky]
2. Výroková logika [Syntax a sémantika výrokovej logiky. Formálny systém výrokovej logiky]
3. Základné vety výrokovej logiky [Veta o kompaktnosti a jej dôsledok, veta o dedukcii. Základné teorémy výrokovej logiky]
4. Postova veta [slabá forma, silná forma]
5. Bezospornosť formálneho systému.
6. Pravidlá odvodenia vo výrokovej logike [Veta o nahradení podformúl ekvivalentnými formulami. De Morganove pravidlá. Veta o dôkaze rozborom prípadov. Veta o substitúcii prvotných formúl.]
7. Disjunktívna a konjunktívna normálna forma formuly.
8. Predikátová logika. [Jazyk predikátovej logiky. Sémantika a syntax predikátovej logiky. Substitúcia termov za premenné. Voľné a viazané premenné.]
9. Axiómy a pravidlá odvodenia predikátovej logiky. [Pravidlá zavedenia kvantifikátorov. Veta o uzávere. Lema o distribúcii kvantifikatorov. Veta o ekvivalencii. Veta o variantoch. Veta o dedukcii. Dôsledky vety o dedukcii. Veta o konštantach. Zovšeobecnená veta o dedukcii a jej dôsledok.]
10. Prenexný a Skolemov tvar formuly.
11. Rovnosť [Axiómy rovnosti. Základné vlastnosti rovnosti. Príklady teórií s rovnosťou.]

Úvod do kombinatoriky a teórie grafov

1. Prirodzené čísla a matematická indukcia
2. Dirichletov princíp
3. Pravidlo súčtu a pravidlo súčinu
4. Variácie a enumerácia zobrazení
5. Kombinácie bez opakovania a enumerácia podmnožín
6. Binomická veta s prirodzeným aj reálnym exponentom
7. Rovnosti a nerovnosti s kombinačnými číslami
8. Kombinácie s opakovaním
9. Polynomická veta
10. Princíp zapojenia a vypojenia
11. Odhady čísla n!
12. Hierarchia rastu funkcií
13. Stromy, lesy a kostry
14. Súvislé grafy, komponenty a meranie vzdialeností v grafe
15. Eulerovské grafy
16. Bipartitné grafy
17. Meranie vrcholovej a hranovej súvislosti grafu
18. Hamiltonovské grafy

Princípy počítačov

1. Kódovanie informácie v počítači (číselná, textová, obrazová, riadiaca a i.)
2. Formáty a aritmetika celých čísel (celé čísla bez znamienka a so znamienkom, jednotkový a binárny doplnkový kód, excess kód, Golayov zrkadlový kód, osmičkový, šestnástkový kód, BCD kód; sčítanie, odčítanie násobenie a delenie, identifikácia a ošetrenie chýb (pretečenie, delenie nulou))
3. Formáty a aritmetika reálnych čísel (pevná rádová čiarka, pohyblivá rádová čiarka, normalizovaný tvar, technika skrytého bitu, základné aritmetické operácie s reálnymi číslami vo formáte pohyblivá rádová čiarka)
4. Booleovské funkcie a operátory (definícia, základné vlastnosti BF, skladanie BF, formuly, uzáver množiny BF, uzavreté množiny BF, úplnosť množiny BF, realizácie BF formulami)
5. Realizácia Booleovských funkcií a operátorov disjunktívnymi normálnymi formami (DNF)
6. Minimalizácia DNF (úplnosť systému AND, OR, NOT, úplná DNF, princíp minimalizácie. Karnaughove mapy, Quine-McCluskey-ova metóda minimalizácie DNF. Neúplne určené BF a ich realizácia pomocou DNF.)
7. Fyzikálne aspekty logických obvodov (signál, modulácia signálu (amplitúdová, frekvenčná, fázová), odchýlky od ideálnych hodnôt, vstupné, výstupné vetvenie obvodu, preklápanie obvodu a i.)
8. Kombinačné obvody (základné kombinačné obvody, návrh kombinačných obvodov, časová a priestorová zložitosť kombinačných obvodov; sčítačka, sčítačka so zrýchleným prenosom, ALU)
9. Sekvenčné obvody (základné pamäťové členy, statická a dynamická analýza SR člena, konečný automat, návrh sekvenčného obvodu, registre, čítač, pamäť)
10. Digitálne systémy (jazyk RTL, riadiace jednotky, návrh digitálneho systému, násobenie a delenie)
11. Architektúra a princíp činnosti počítača (s von Neumannovského a Harvardskou architektúrov).
12. Inštrukcie počítača (inštrukčný súbor, formát inštrukcií, spracovanie inštrukcie, CPU cykly, RTL, spôsoby adresovania).
13. CPU (Central Processing Unit) – hlavné časti CPU a ich základné funkcie, makroinštrukcie a mikroinštrukcie, konfigurácie CPU, spracovanie prerušení).
14. ALU (Arithmetic and Logic Unit) – aritmetické operácie, logické funkcie, podmienkové bity.
15. Mikroprogramovanie – napevno zdrôtovaná vs. mikroprogramovo riadená CLU, horizontálne vs. vertikálne mikroinštrukcie.
16. RISC a CISC – východiská a motivácia, princípy návrhu RISC, porovnanie RISC vs. CISC, špecifiká registrov pri RISC architektúre (rozdelenie do okien).
17. Spracovanie vstupu a výstupu – vstupno-výstupné zariadenia, formáty a spôsoby prenosu údajov, memory mapped I/O vs. I/O mapped I/O, riadenie vstupu a výstupu (programom riadený I/O, I/O využívajúci prerušenia, DMA prenos, I/O kanál).
18. Konfigurácie multiprocesorových systémov – so spoločnou zbernicou, s duálnou zbernicou, NUMA, switching (crossbar) matrix interconnection scheme.
19. Pamäť– hierarchia pamätí, delenie pamätí (RAM, ROM, ...), asociatívna pamäť, cache, zásobníková pamäť.
20. Pipelining – aritmetický a inštrukčný, jednofunkčný a polyfunkčný, statický a dynamický, sušenie rúry.

Programovanie

1. Objektovo orientované programovanie (zapúzdrenie, dedičnosť, polymorfizmus, trieda, modifikátory prístupu, konštruktory, abstraktné triedy a rozhrania), vnorené triedy (nested classes), garbage collection.
2. Výnimky (exceptions) - vyhodenie výnimky, zachytenie a spracovanie výnimiek (try, catch, finally), vlastné triedy výnimiek, checked a unchecked výnimky.
3. Vlákna (threads) – stav vlákna (new, runnable, blocked, waiting, timed_waiting, terminated), životný cyklus vlákna (vytvorenie, spustenie, zastavenie, ...), plánovanie vlákien (fixed-priority scheduling, yield, time-slicing). Synchronizácia vlákien (kritické úseky, wait a notify, explicitné zámky a podmienkové premenné).
4. Generics (formálne typové parametre, parametrizovaný typ, wildcards, ohraničené wildcards, generic methods).
5. Návrhové vzory: Composite, Strategy
6. Návrhové vzory: Decorator, Abstract Factory
7. Návrhové vzory: Bridge, Memento
8. Návrhové vzory: Iterator, Visitor

Systémové programovanie

1. Jazyk assemblera – prvky jazyka, typy inštrukcií, operandy, adresné módy.
2. Práca so zásobníkom – volacie konvencie C a Pascal a ich vlastnosti.
3. Assembler a makroprocesor – úloha, spôsob práce, jednoprechodové a dvojprechodové.
4. Linker a loader – úloha, spôsob práce, knižnice, dynamické linkovanie.
5. Systémové volania – procesy a spracovanie signálov – vytváranie a ukončovanie procesu, spúšťanie programu, signály.
6. Systémové volania – vstupno-výstupné operácie so súbormi a terminálmi.
7. Systémové volania – sieťová komunikácia.

Operačné systémy

1. Koncepcia OS (procesy, súbory, funkcie a služby OS, systémové volania, interpreter príkazov) a štruktúra OS (monolitický kernel, mikrokernel, …).
2. Procesy (hierarchia procesov, vytváranie, swapovanie procesov, životný cyklus procesu) a komunikácia medzi procesmi (synchronizácia, adresovanie).
3. Synchronizácia procesov (časová závislosť procesov /race conditions/, vzájomné vylúčenie /mutual exclusion/ a spôsoby jeho dosiahnutia – hardvérové aj softvérové) a klasické problémy synchronizácie procesov (producent/konzument, problém obedujúcich filozofov, problém čitateľov a zapisovateľov).
4. Uviaznutie – podmienky pre vznik uviaznutia, metódy riešenia uviaznutia (ignorovanie, detekcia a vyvedenie, prevencia, vyhýbanie sa). Rozdiel medzi uviaznutím a vyhladovaním.
5. Správa procesov a procesora – plánovače a ich funkcie. Algoritmy plánovania procesov (FCFS, SJF, HRN, SRT, RR, ...).
6. Správa pamäte – jej funkcie, typy správy pamäte (jeden súvislý úsek, statické súvislé úseky, dynamické súvislé úseky, stránkovanie, segmentovanie).
7. Správa pamäte – virtuálna pamäť, výpadok stránky, nahradzovacie algoritmy (FIFO, NRU, LRU, NFU), stránkovanie na žiadosť, model s pracovnou množinou, implementačné problémy (zálohovanie inštrukcií, zamykanie stránok v pamäti, zdieľanie stránok).
8. Správa súborov – funkcie, typy súborov, štruktúra súboru, hierarchické systémy adresárov, správa voľného priestoru na disku (spájaný zoznam voľných blokov, indexové bloky, bitová mapa), správa priestoru prideleného súboru (FAT, i-node), zdieľané súbory.
9. Správa zariadení – funkcie, klasifikácia V/V zariadení, pojem riadiaca jednotka, DMA, techniky prideľovania V/V, V/V softvér, správa diskových požiadaviek (SSTF, SCAN, C-SCAN, N-step SCAN).

Počítačové siete

1. Základné pojmy zo sietí – topológia a geografia siete, spôsoby prenosu údajov v sieťach (prepínanie paketov, prepínanie okruhov, prepínanie virtuálnych okruhov), kategorizácia sietí, typy liniek v sieťach.
2. Sieťová architektúra, vrstvové modely, služby – vrstva, rozhranie, protokol, fyzický a logický tok údajov, zásobník protokolov, typy služieb.
3. Kľúčové problémy pri návrhu sietí – adresácia, pravidlá komunikácie, správa chýb, následnosť správ, problém rýchleho odosielateľa a pomalého príjemcu, obmedzené dĺžky správ, príklady riešení.
4. Referenčný model ISO OSI a model TCP/IP.
5. Fyzická vrstva – metalické a optické káble, elektromagnetické spektrum a bezdrôtové prenosy.
6. Linková vrstva – Ethernet – adresácia, spôsob prenosu, obmedzenia, rozširovanie.
7. Linková vrstva – WiFi – adresácia, spôsob prenosu, BSS, ESS, access point, distribučný systém, portál.
8. Sieťová vrstva TCP/IP (IPv4) – adresácia, služby, protokol IP, smerovanie, ARP, NAT, ICMP.
9. Transportná vrstva TCP/IP – služby, protokoly UDP a TCP.
10. Aplikačná vrstva – DNS, DHCP.
11. Aplikačná vrstva – web – organizácia webu, protokoly, proxy servery, bezpečnosť.
12. Aplikačná vrstva – elektronická pošta – organizácia elektronickej pošty, protokoly, MIME, bezpečnosť.
13. Sieťová vrstva TCP/IP – IPv6 – adresácia, služby, protokol IPv6, smerovanie, ICMPv6, Neighbour Discovery Protocol, konfigurácia, 6to4, prepojenie s IPv4.
14. Bezpečnosť sietí – bezpečnostné problémy a mechanizmy na rôznych vrstvách – VLAN, VPN, SSL/TLS, firewall, bezpečnosť na aplikačnej vrstve.

Úvod do databáz

1. Dátové modely. Trojschémová architektúra (ANSI sparc). Entitno-relačný model. Relačný model, relačná algebra. Negácia a rekurzia v relačnej algebre. Súvis relačnej algebry s inými dotazovacími jazykmi.
2. Relačný kalkul. Predikátová interpretácia relačnej algebry. Negácia, doménovo nezávislé a bezpečné formuly. Relačný kalkul (doménový). Súvis relačného kalkulu s inými dotazovacími jazykmi.
3. Datalog. Syntax a sémantika Datalogových programov. Súvis s relačným kalkulom. Výpočet dotazu na Datalogový program. Negácia. Bezpečnosť Datalogových programov.
4. Relačná algebra. Operátory relačnej algebry. Multimnožinová interpretácia relácií. Grupovanie a agregácia. Rekurzia, výpočet pevného bodu. Súvis relačnej algebry s inými dotazovacími jazykmi.
5. Jazyk SQL. Programovanie v SQL (Data Definition Language, Data Manipulation Language). Negácia a rekurzia v SQL. Súvis SQL s inými dotazovacími jazykmi.
6. Teória navrhovania relačných báz dát. Funkčné závislosti, Armstrongove axiómy, uzáver množiny atribútov, uzáver množiny funkčných závislostí. Pokrytie a minimálne pokrytie množiny funkčných závislostí. Nadkľúče a kľúče.
7. Normálne formy. 3NF, BCNF. Algoritmy pre dekompozíciu do normálnych foriem. Bezstratovosť dekompozície.
8. Transakcie. Požiadavky na transakčný systém (ACID). Architektúra transakčného systému. Rozvrhy. Triedy sériovateľnosti a obnoviteľnosti.
9. Implementácia sériovateľnosti a obnoviteľnosti v transakčných systémoch. Testy sériovateľnosti. Algoritmy izolácie, zámky, časové pečiatky, validácia. Uviaznutie (deadlock) a metódy riešenia uviaznutia. Algoritmy onbovy, log-file, checkpointing, backup.
10. Fyzická organizácia. Dvojúrovňový model pamäti a organizácie dát. Indexové stromy, hashovanie. Operátory fyzickej algebry. Implementácia vybraných fyzických operátorov (merge-sort, nested-loop join).

Formálne jazyky a automaty

1. Regulárne jazyky. [Deterministické a nedeterministické konečné automaty, regulárne gramatiky, regulárne výrazy, ekvivalencia popisov regulárnych jazykov, pumpovacia lema, uzáverové vlastnosti.]
2. Bezkontextové jazyky. [Bezkontextové gramatiky, normálne tvary, nedeterministické zásobníkové automaty, ekvivalencia zásobníkových automatov a bezkontextových gramatík, pumpovacia lema, uzáverové vlastnosti.]
3. Rekurzívne vyčísliteľné a rekurzívne jazyky. [Turingove stroje, frázové gramatiky, ich ekvivalencia, uzáverové vlastnosti, univerzálny Turingov stroj, Turingova hypotéza.]
4. Nerozhodnuteľné problémy. [Diagonalizácia, problém zastavenia, metódy dokazovania nerozhodnuteľnosti.]
5. Miery zložitosti pre Turingove stroje [triedy zložitosti, kompresia pásky, zrýchľovanie výpočtov, vplyv redukcie počtu pások na zložitosť]

Efektívne algoritmy a dátové štruktúry

1. Analýza algoritmov. (Definícia časovej zložitosti. O-notácia.)
2. Odhad časovej zložitosti rekurzívnych algoritmov. (Odhad časovej zložitosti algoritmov používajúcich metódu rozdeľ a panuj.)
3. Algoritmy triedenia. (MergeSort, QuickSort, HeapSort. Analýza ich časovej zložitosti.)
4. Triedenia v lineárnom čase. (CountSort, BucketSort, RadixSort.)
5. Zložitosť problému triedenia. (Dolný odhad časovej zložitosti každého triedenia porovnávaním.)
6. Základné dátové štruktúry. (Zásobník, fronta, halda.)
7. Abstraktný dátový typ slovník (resp. množina, asociatívne pole) a jeho implementácia pomocou binárnych vyhľadávacích stromov, vyvážené stromy
8. Hešovanie. (Základné princípy. Kolízie a rôzne spôsoby ich riešenia.)
9. Prioritná fronta.
10. Union/Find-Set problém.
11. Základné grafové algoritmy. (Prehľadávanie do hĺbky a do šírky, topologické triedenie, reprezentácia grafov.)
12. Algoritmy pre hľadanie najkratších ciest v grafe.
13. Algoritmus pre hľadanie najlacnejšej kostry grafu.
14. Strassenov algoritmus na násobenie matíc.
15. Dynamické programovanie (Konkrétne aplikácie. Charakterizácia problémov riešiteľných dynamickým programovaním. Porovnanie iteratívneho prístupu a rekurzie s memoizáciou.)
16. Ďalšie princípy tvorby efektívnych algoritmov vrátane konkrétnych aplikácií (Rozdeľuj a panuj, pažravé (greedy) algoritmy, princíp vyváženosti, voľba vhodnej dátovej štruktúry).
17. Triedy P a NP; polynomiálna redukovateľnosť. Cook-Levinova Veta a ďalšie NP-úplné problémy.

Princípy tvorby softvéru

1. Metódy vývoja softvéru (vodopádový model; I-I vývoj; agilné metodiky; LEAN)
2. Ako popisovať softvér (4+1 view; základné typy diagramov UML)
3. Požiadavky; tvorba špecifikácie (spôsoby zachytenia požiadaviek; typy požiadaviek; use case; scenario; user story; stopovateľnosť; change management)
4. Architektúra a základné dizajnové princípy (architektúra softvéru; architektonicky signifikantné požiadavky; YAGNI; rule of 3; DRY; SOLID)
5. Mechanizmy a návrhové vzory vo viacvláknových aplikáciách (best practices; imutable dátové štruktúry; double-checked locking; BlockingQueue; Futures; Promisses; Executors; Reactor)
6. Testovanie a kvalita softvéru (typy testov; testovateľný kód; dependency injection; techniky na zabezpečenie kvality softvéru)
7. Manažment konfigurácií a softvérové nástroje, ktoré ho podporujú (branch; merge; version; typy VCS; GIT; Issue tracking)
8. Implementácia, integrácia, dokumentácia a údržba (programovacie konvencie; continuous integration; údržba softvéru)
9. Manažment projektov, estimácie a manažment rizík (aktivity softvérového manažmentu; metódy tvorby estimacií, problémy)