Obsah a organizácia záverečného konania pre I. stupeň štúdia študijného programu v odbore 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 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, 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]
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í [konečné rozšírenie poľa, stupeň rozšírenia, algebraické rozšírenie, minimálny polynóm daného algebraického prvku]
9. Konečné polia [charakteristika poľa, možné počty prvkov konečných polí, počítanie v poli F[x]/(p(x)) pre ireducibilný polynóm p(x), rozkladové pole polynómu, existencia poľa s p^n prvkami]

Ú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 [definícia usporiadanej dvojice, karteziánsky súčin dvoch a viacerých množín, množinové identity s karteziánskym súčinom, použitie karteziánskeho súčinu]
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-tranzitívny uzáver – definície, vlastnosti.]
6. Usporiadania [definícia čiastočného a úplného usporiadania množiny, ostré a neostré usporiadanie, minimálny, maximálny, prvý a posledný prvok množiny, lexikografické usporiadanie karteziánskeho súčinu]
7. Zobrazenia [definícia pomocou relácií, injektívne, surjektívne a bijektívne zobrazenia a ich skladanie]
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 [formulácia vety, idea dôkazu, usporiadanie kardinálnych čísel]
10. Konečné a nekonečné množiny [definícia konečnej množiny, definícia nekonečnej množiny, existencia nekonečných množín, vlastnosti konečných a nekonečných množín]
11. Spočítateľné a nespočítateľné množiny [zjednotenie a karteziánsky súčin spočítateľných množín, existencia nespočítateľných množín, Cantorova diagonálna metóda]
12. Potenčná množina a jej kardinalita [formulácia Cantorovej vety o potenčnej množine, idea dôkazu, dôsledky pre nekonečné množiny]

Úvod do matematickej logiky

1. Syntax a sémantika výrokovej logiky a logiky prvého rádu
2. Tablový kalkul pre výrokovú logiku, korektnosť a úplnosť tablového kalkulu
3. Tablový kalkul pre logiku prvého radu a jeho korektnosť
4. SAT solvery, algoritmus CDDL, rezolvencia vo výrokovej logike
5. Normálne formy formúl vo výrokovej logike, transformácia do CNF, veta o dedukcii, veta o kompaktnosti pre výrokovú logiku
6. Normálne formy formúl v logike prvého radu, skolemizácia, rezolvencia v prvorádovej logike

Úvod do kombinatoriky a teórie grafov

1. Prirodzené čísla a matematická indukcia, Dirichletov princíp [definícia prirodzených čísiel, vlastnosť dobrého usporiadania, dôkaz matematickou indukciou]
2. Základné pravidlá kombinatorického počítania [pravidlo súčtu, súčinu, mocnenia, počítanie prvkov množiny dvoma spôsobmi]
3. Variácie a enumerácia zobrazení [variácie s opakovaním a bez opakovania, permutácie, určenie ich počtu]
4. Kombinácie a enumerácia podmnožín [kombinácie bez opakovania a s opakovaním a určenie ich počtu, príklady kombinácií s opakovaniami]
5. Binomická a polynomická veta [znenie a dôkaz, dôsledky]
6. Rovnosti a nerovnosti s kombinačnými číslami [identity zahŕňajúce kombinačné čísla, metódy dokazovania identít]
7. Princíp zapojenia a vypojenia [formulácia, dôkaz a aplikácie: enumerácia surjektívnych zobrazení, počet permutácií bez pevných bodov]
8. Hierarchia rastu funkcií, odhady čísla n! O-symbolika, rádová rovnosť, asymptotická rovnosť, odhady
9. Stromy a lesy, kostry, súvislé grafy, meranie vzdialeností v grafe [definície, vlastnosti, rozličné charakterizácie stromov]
10. Eulerovské a bipartitné grafy [charakterizácie eulerovských a bipartitných grafov, algoritmus na nájdenie eulerovského ťahu]
11. Meranie vrcholovej a hranovej súvislosti grafu [definície, vzájomný vzťah, artikulácie, mosty, charakterizácia 2-súvislých grafov]
12. Hamiltonovské grafy [definícia, postačujúce podmienky, zložitosť problému]

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. Vrstvové modely, služby - vrstva, rozhranie, protokol, služba, typy služieb, referenčný model ISO OSI a model TCP/IP.
2. Fyzická vrstva – metalické a optické káble, elektromagnetické spektrum a bezdrôtové prenosy.
3. Linková vrstva – Ethernet a WiFi – adresácia, spôsob prenosu, obmedzenia, rozširovanie, BSS, ESS, access point, distribučný systém, portál.
4. Sieťová vrstva TCP/IP (IPv4) – adresácia, služby, protokol IP, smerovanie, ARP, NAT, ICMP.
5. Transportná vrstva TCP/IP – služby, protokoly UDP a TCP.
6. Aplikačná vrstva – DNS, DHCP.
7. Aplikačná vrstva – web – organizácia webu, protokoly, proxy servery, bezpečnosť.
8. Aplikačná vrstva – elektronická pošta – organizácia elektronickej pošty, protokoly, MIME, bezpečnosť.
9. Sieťová vrstva TCP/IP – IPv6 – adresácia, služby, protokol IPv6, smerovanie, ICMPv6, Neighbour Discovery Protocol, konfigurácia, 6to4, prepojenie s IPv4.
10. 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. Účel databázových systémov. Charakteristika databázových aplikácií. Trojstupňová architektúra ANSI SPARC. Dátové modely.
2. Relačný kalkul. Syntax predikátových formúl. Formulácia dotazov v relačnom kalkule. Negácia, doménovo nezávislé a bezpečné formuly. Súvis s inými dotazovacími jazykmi.
3. Datalog. Syntax a sémantika Datalogových programov. Negácia. Bezpečnosť Datalogových programov. Výpočet dotazu na Datalogový program. Súvis s inými dotazovacími jazykmi.
4. Relačná algebra. Operátory relačnej algebry. 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. Grupovanie a agregácia. Rekurzia. Súvis SQL s inými dotazovacími jazykmi.
6. Teória navrhovania relačných databáz. 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 relácie.
7. Normálne formy. Účel normalizácie databáz. Tretia normálna forma, Boyce-Coddova normálna forma. Algoritmy pre dekompozíciu do normálnych foriem. Bezstratovosť dekompozície, zachovanie funkčných závislostí.
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 obnovy. Log-file, checkpointing.
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ť]
6. Triedy P a NP [polynomiálna redukovateľnosť. Cook-Levinova veta a ďalšie NP-úplné problémy]

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

1. Analýza časovej zložitosti algoritmov. (Definícia časovej zložitosti. O-notácia. Odhad časovej zložitosti rekurzívnych algoritmov používajúcich metódu rozdeľ a panuj.)
2. Algoritmy pre triedenie. (Efektívne algoritmy triedenia porovnávaním. Triedenie v lineárnom čase. Dolný odhad časovej zložitosti každého triedenia porovnávaním.)
3. Dátové štruktúry v poli. (Pole s dynamickou veľkosťou – vektor. Zásobník, fronta. Binárna halda a implementácia prioritnej fronty pomocou nej.)
4. Usporiadané dátové štruktúry. (Binárne vyhľadávacie stromy. Usporiadaná množina, usporiadané asociatívne pole – slovník. Vyvažovanie binárnych stromov.)
5. Hešovanie. (Kolízie a rôzne spôsoby ich riešenia. Narodeninový paradox. Množina, asociatívne pole.)
6. Základné grafové algoritmy. (Reprezentácie grafu v pamäti. Prehľadávanie do hĺbky a do šírky. Topologické triedenie.)
7. Najkratšie cesty v grafe. (Dijkstrov algoritmus, Floydov-Warshallov algoritmus.)
8. Najlacnejšia kostra grafu. (Algoritmus Union-FindSet. Kruskalov algoritmus.)
9. Násobenie matíc. (Naivný algoritmus. Strassenov algoritmus. Efektívne umocňovanie matice. Tranzitívny uzáver grafu pomocou umocňovania matíc.)
10. Dynamické programovanie (Konkrétne príklady použitia. Charakterizácia problémov riešiteľných dynamickým programovaním. Porovnanie iteratívneho prístupu a rekurzie s memoizáciou.)
11. Ďalšie princípy tvorby efektívnych algoritmov. (Rozdeľuj a panuj, pažravé algoritmy, princíp vyváženosti, voľba vhodnej dátovej štruktúry. Konkrétne príklady použitia.)

Princípy tvorby softvéru (platné od začiatku AR 2023/2024, teda už od štátnic v septembri 2023)

1. Metódy vývoja softvéru, softvérové kontrakty (vodopádový model; I-I vývoj; agile; softvérové kontrakty)
2. Manažment konfigurácií (ciele manažmentu konfigurácií; typy VCS; git; commit; branch; merge; rebase)
3. Modelovanie domény (model; želané vlastnosti modelu; ciele modelovania domény; typy vzťahov medzi triedami v UML diagrame tried; abstrakcia atribútov, abstrakcia typov, abstrakcia závislostí)
4. Dizajn (ciele dizajnu; dizajnové princípy; SOLID)
5. Návrhové vzory a UML diagramy (návrhové vzory; UML diagram tried; UML sekvenčný diagram; code smells; refaktorizácia)
6. Testovanie a kvalita softvéru (zabezpečovanie, plánovanie a kontrola kvality; techniky na zabezpečenie kvality softvéru; testovacia pyramída; testovateľný kód; dependency injection)
7. Implementácia a integrácia (programovacie konvencie; continious integration; test driven development)