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. Dana Pardubská, CSc., garantka študijného programu

Úvod

Obsah štátnej skúšky

• Matematická analýza (1) a (2)
• Algebra (1) a (2)
• Diskrétna matematika
• Matematická logika

• 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. Priestory so skalárnym súčinom [skalárny súčin, veľkosť vektora, ortogonálny doplnok, existencia ortonormálnej bázy]
5. Kvadratické formy [kongruentné matice, kvadratické formy, kanonický tvar, Sylvestrov zákon zotrvačnosti, kladná definitnosť]
6. Podobnosť matíc [podobnosť matíc, vlastné hodnoty a vlastné vektory, charakteristický polynóm, podobnosť s diagonálnou maticou, ortogonálna podobnosť]
7. Polynómy a okruhy polynómov nad poľom F [polynómy a operácie s nimi, veta o delení so zvyškom, deliteľnosť, najväčší spoločný deliteľ a Euklidov algoritmus, existencia a jednoznačnosť rozkladu na ireducibilné polynómy, základné výsledky o koreňoch, základné výsledky o ireducibilných polynómoch]

Diskrétna matematika

1. Matematické dôkazy [dôkaz priamy, nepriamy, sporom, rozborom prípadov; prirodzené čísla, matematická indukcia, úplná indukcia; Dirichletov princíp]
2. Intuitívny pojem množiny [základné pojmy a označenia, množinové operácie, množinové identity, karteziánsky súčin množín, usporiadané n-tice]
3. Relácie a zobrazenia [skladanie relácií, inverzná relácia, relácia na množine; relácia ekvivalencie, rozklad množiny; reflexívny a tranzitívny uzáver relácie; definícia zobrazenia pomocou relácií; injektívne, surjektívne a bijektívne zobrazenia; skladanie zobrazení]
4. Usporiadania [čiastočné a úplné usporiadanie množiny; ostré a neostré usporiadanie; minimálny, maximálny, najmenší a najväčší prvok; lexikografické usporiadanie karteziánskeho súčinu]
5. Mohutnosť množiny [konečné a nekonečné množiny - definícia, vlastnosti; porovnávanie mohutností; počítanie s mohutnosťami - súčet, súčin a mocnina; mohutnosť zjednotenia a karteziánskeho súčinu spočítateľných množín; dôkaz existencie nespočítateľných množín; usporiadanie kardinálnych čísel]
6. Enumeratívna kombinatorika [pravidlo súčtu, súčinu, umocňovania; počítanie prvkov množiny dvoma spôsobmi; permutácie; variácie bez opakovania a s opakovaním, enumerácia zobrazení; kombinácie bez opakovania a s opakovaním; enumerácia podmnožín]
7. Kombinatorické identity [binomická a polynomická veta - znenie, dôkaz, dôsledky; identity zahŕňajúce kombinačné čísla a metódy ich dôkazu; princíp zapojenia a vypojenia - formulácia a dôkaz; aplikácie - enumerácia surjektívnych zobrazení, počet permutácií bez pevných bodov]
8. Základy teórie grafov [definície a základné vlastnosti grafových pojmov: orientovaný a neorientovaný graf, vrchol, hrana, cesta, kružnica, strom, les, kostra grafu, stupeň vrchola; charakterizácie stromov a dôkazy ich ekvivalencie]
9. Špeciálne triedy grafov [bipartitné grafy - charakterizácia, algoritmus na testovanie bipartitnosti; eulerovské grafy - charakterizácia, algoritmus na nájdenie eulerovského ťahu; hamiltonovské grafy - definícia, dôkaz Diracovej postačujúcej podmienky]
10. Vzdialenosť a súvislosť v grafoch [vzdialenosť v ohodnotenom a neohodnotenom grafe, vrcholová a hranová súvislosť grafu - definície, ich vzájomný vzťah, artikulácie, mosty, charakterizácia 2-súvislých grafov]

Matematická logika

1. Výroková logika a logika prvého rádu [syntax: jazyk, logické a mimologické symboly, termy, atómy, formuly; sémantika: štruktúra, ohodnotenie, pravdivosť formuly pri danom ohodnotení, tautológia a kontradikcia, splniteľnosť a platnosť formuly, model, teória, logické vyplývanie; definícia a význam kompaktnosti]
2. Formalizácia dôkazov [hilbertovský kalkul pre výrokovú logiku; tablový kalkul pre prvorádovú logiku, dôkaz korektnosti a úplnosti tablového kalkulu pre výrokovú logiku]
3. Rezolvencia v prvorádovej logike [negačná a prenexná normálna forma; skolemizácia; unifikácia; rezolvenčný dôkaz]
4. Problém splniteľnosti (SAT) [disjunktívna a konjunktívna normálna forma, efektívny prepis boolovskej formuly do CNF, transformácia kombinatorických problémov na problém splniteľnosti]

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

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)