Statna skuska zo Spolocneho zakladu

Table of Contents

Matematika.......................................................................................................................................................................1

Matematicka analyza............................................................................................................................................1
Algebra..................................................................................................................................................................1
Diskretna matematika...........................................................................................................................................2
Kombinatoricka analyza.......................................................................................................................................2
Teoria grafov.........................................................................................................................................................2
Logika pre informatikov.......................................................................................................................................3
Numericka matematika.........................................................................................................................................3
Pravdepodobnost a matematicka statistika...........................................................................................................3

Zaklady informatiky........................................................................................................................................................4

Programovanie......................................................................................................................................................4
Principy tvorby software.......................................................................................................................................4
Teoria programovania...........................................................................................................................................4
Principy pocitacov................................................................................................................................................4
Operacne systemy.................................................................................................................................................4
Databazove systemy..............................................................................................................................................5
Specifikacia a verifikacia programov...................................................................................................................5
Formalne jazyky a automaty.................................................................................................................................5
Efektivne algoritmy..............................................................................................................................................6
Algoritmy a datove struktury................................................................................................................................6

Statna skuska zo Spolocneho zakladu

i

Matematika

Matematicka analyza

Limita realnej funkcie realnej premennej. Nutna a postacujuca podmienka existencie limity funkcie v bode.
Zakladne vety o limitach. Limita monotonnych funkcii a postupnosti.

1.

Spojitost funkcie. Zakladne vety o spojitych funkciach v bode. Spojite funkcie na mnozine a ich vlastnosti.
[Rovnomerne spojite funkcie.]

2.

Limita funkcie viac premennych. Limita zobrazenia z R^n do R^m. Spojitost funkcie viac premennych.
Spojitost zobrazenia z R^n do R^m. Kompaktne a suvisle mnoziny. Vlastnosti spojitych zobrazeni na
kompaktnych mnozinach.

3.

Diferencovatelnost funkcie jednej a viacerych premennych. Diferencovatelnost zobrazenia z R^n do R^m.
Suvis medzi diferencovatelnostou a parcialnymi derivaciami. Spojitost a diferencovatelnost. Derivacia
zlozeneho zobrazenia. Vety o strednej hodnote. Parcialne derivacie vyssich radov, podmienky pre zamennost
ich derivovania. Taylorov vzorec. Extremy funkcii. Nutne a postacujuce podmienky pre existenciu extremu.

4.

Riemannov integral. Zakladne vlastnosti R−integralu. Nutna a postacujuca podmienka integrovatelnosti.
Niektore mnoziny R−integrovatelnych funkcii. Veta o strednej hodnote. Metody vypoctu R−integralu.
Newton−Leibnizov vzorec.

5.

[Nevlastne integraly. Cauchyho−Bolzanova podmienka konvergencie nevlastneho integralu. Kriteria
konvergencie nevlastneho integralu.]

6.

Ciselne rady. Kriteria konvergencie. Absolutne a relativne konvergentne rady.

7.

Funkcionalne rady a postupnosti. Bodova a rovnomerna konvergencia. Kriteria pre rovnomernu konvergenciu
postupnosti a radov funkcii. Vety o derivovani a integrovani rovnomerne konvergentnych postupnosti a radov.

8.

Mocninove rady. Abelova veta, polomer konvergencie. Vlastnosti mocninovych radov v intervale
konvergencie. Taylorov rad.

9.

Linearna diferencialna rovnica 1.a n−teho radu. Zakladne vlastnosti rieseni. Linearna diferencialna rovnica
2.radu s konstantnymi koeficientami.

10.

Algebra

Uvodne pojmy: zakladne pojmy z teorie mnozin, relacie, funkcie, binarne operacie. Pojem grupy, najzakladnejsie
vlastnosti a priklady, pojem pola, najzakladnejsie vlastnosti, priklady.

Vektorove priestory, linearne zobrazenia: priestor, podpriestor, linearna zavislost, baza a dimenzia.
Steinitzova veta, sucty podpriestorov, linearne zobrazenia, kompozicia linearnych zobrazeni, inverzne
linearne zobrazenia, matica linearneho zobrazenia, jadro a obraz linearneho zobrazenia.

1.

Matice a riesenia linearnych rovnic nad polom F: matice, operacie s maticami (nasobenie, scitanie),
elementarne riadkove operacie, trojuholnikovy a redukovany trojuholnikovy tvar matice, systemy linearnych
rovnic nad polom F, mnozina rieseni homogennych a nehomogennych systemov linearnych rovnic, existencia
a tvary rieseni.

2.

Determinanty, determinant linearneho zobrazenia a matice. Vlastnosti determinantov. Vypocty determinantov
a ich pouzitie pri rieseni linearnych rovnic a hladani inverznej matice.

3.

Euklidovske vektorove priestory, kvadraticke formy: skalarny sucin, [matica skalarneho sucinu], vlastnosti
skalarneho sucinu, dlzka vektora, uhol medzi vektormi, ortonormalna baza euklidovskeho vektoroveho
priestoru, ortogonalny doplnok, kvadraticke formy, matica kvadratickej formy, kanonicky tvar kvadratickej
formy, Sylvestrov zakon zotvrvacnosti. Kladne (semi−)definitne matice. Sylvestrova podmienka.

4.

Podobnost matic, ortogonalna podobnost matic: matica linearneho zobrazenia pri danej baze, definicia
podobnosti matic a vztah k linearnym zobrazeniam, kedy je matica podobna s diagonalnou maticou,
ortogonalna podobnost, charakteristicky polynom matice, vlastne cisla realnej symetrickej matice.

5.

1

Grupy: grupy, podgrupy, izomorfizmus a homomorfizmus grup, cyklicke grupy (s klasifikaciou) a ich
podgrupy, grupy permutacii, rozklad grupy podla podgrupy, Lagrangeova veta, homomorfizmus a
izomorfizmus grup, normalna podgrupa, faktorizacia grupy podla podgrupy.

6.

Okruhy: zakladne vlastnosti operacii v okruhoch, podokruh, ideal (hlavny, maximalny, prvoideal),
faktorizacia okruhu podla idealu, vztah medzi vysledkom faktorizacie a vlastnostami idealu, podla ktoreho sa
faktorizuje, obor integrity a veta o podielovom poli.

7.

Okruhy hlavnych idealov, existencia jednotky, najvacsi spolocny delitel, vlastnosti delitelnosti, ireducibilne
prvky, veta o jednoznacnom rozklade.

8.

Okruhy polynomov: pojem algebraickeho a transcendentneho prvku pre dany okruh, okruh polynomov R[x],
okruh polynomov F[x] nad polom F ako okruh hlavnych idealov, veta o jednoznacnom rozklade polynomov
nad danym polom, substitucny homomorfizmus (veta o substitucii), korene, viacnasobne korene, Hornerova
schema, derivacia, [Taylorov rozvoj].

9.

Rozsirenia poli: jednoduche, viacnasobne a konecne rozsirenie pola, vztah medzi nimi, minimalny polynom
daneho algebraickeho prvku, transcendentne rozsirenie.

10.

[Teoria konecnych poli: charakteristika pola, rozkladove pole daneho polynomu nad danym polom, veta o
existencii a izomorfizmus rozkladovych poli, konecne polia − veta o existencii a izomorfizme konecnych
poli.]

11.

Diskretna matematika

Vyroky, logicke operacie, formuly, vyrokove funkcie, kvantifikacia vyrokov, tautologie, matematicky dokaz,
zakladne typy matematickych dokazov, logicky dosledok. Zakladne pojmy a oznacenia, intuitivny pojem
mnoziny.

1.

Operacie s mnozinami, zjednotenie, prienik, symetricka diferencia mnozin, mnozinove identity, karteziansky
sucin mnozin a jeho vlastnosti, relacie, relacie ekvivalencie a rozklad mnoziny, ciastocne usporiadanie a
usporiadanie, zobrazenie. Mohutnosti mnozin. Ekvivalencia mnozin a kardinalne cisla, pocitanie s
kardinalnymi cislami, sucet, sucin a mocnina kardinalnych cisel, nerovnosti medzi kardinalnymi cislami.
Cantorova−Bernsteinova veta a jej dosledky. Cantorova veta a jej dosledky. Konecne mnoziny. Nekonecne
mnoziny. Aritmetika celych nezapornych cisel. Spocitatelne mnoziny, nespocitatelne mnoziny.

2.

Zakladne pojmy kombinatoriky. Pravidlo suctu a sucinu. Variacie a kombinacie s opakovanim a bez
opakovania. Permutacie a permutacie s poctom cyklov danej dlzky. Zakladne kombinatoricke identity.
Polynomicka veta a jej dosledky. Princip zapojenia a vypojenia, jeho zovseobecnenia a pouzitie. Pocet
surjektivnych zobrazeni a pocet predpisanych surjekcii na konecnych mnozinach. Spernerova veta a jej
pouzitie. Dirichletov princip. Konigova lema. Ramseyova veta. Ramseyove cisla. Systemy reprezentantov,
Hallova veta, Hallov algoritmus, Knigova veta pre binarne matice. Rozklady (particie) prirodzenych cisel
(usporiadane a neusporiadane). Metoda diagramov. Eulerova veta.

3.

Kombinatoricka analyza

Zakladne metody vypoctu sum. Sumy a rekurentne vztahy. Viacnasobne sumy. Konecny kalkul. Celociselne funkcie
(dolna a horna cela cast, div, mod). Sumy obsahujuce cele casti. Kombinacne cisla a ich vlastnosti. Binomicka veta.
Kombinatoricke identity.

Teoria grafov

Zaklady: stromy, lesy, bipartitne grafy, eulerovske grafy, cyklovy priestor grafu.

1.

Parenie: Konigova teorema a maximalnom pareni, Hallova teorema (o manzelstvach) a ich dosledky. Tuttova
teorema o 1−faktore a jej zovseobecnenie. Petersenova teorema o 1−faktore v kubickych grafoch.

2.

2

Suvislost: charakterizacia dvoj− a trojsuvislych grafov, Mengerova teorema a jej dosledky, hranovo
disjunktne kostry v grafe.

3.

Planarne grafy: Reprezentacia grafov v rovine a v priestore, stereograficka projekcia, Eulerova rovnost,
dualita v rovine, Kuratowskeho teorema.

4.

Farbenie: Heawoodova teorema o 5 farbach, teorema o 4 farbach, algoritmus postupneho farbenia (greedy a.),
Brooksova teorema o hornom odhade chromatickeho cisla, Knigova teorema o hranovom farbeni bipartitnych
grafov, Vizingova teorema o hranovych farbeniach. Zoznamove chromaticke cislo (vyberove cislo).

5.

Hamiltonovske grafy: Diracova postacujuca podmienka, hamiltonovske kruznice a postupnosti stupnov,
Chvatalova teorema.

6.

Toky v grafoch: Kirchhoffov zakon, Fordova a Fulkersonova teorema o maximalnom toku a reze minimalnej
kapacity, jej vyuzitie. Fordov a Fulkersonov algoritmus na hladanie maximalneho toku. Grupove toky, k−toky
pre male k, suvislost s farbeniami.

7.

Extremalne problemy, Turanova teorema, Erdsova−Stonova teorema, Ramseyova teorema.

8.

Nahodne grafy − zakladne pojmy a vlastnosti.

9.

Logika pre informatikov

Aritmetizacia

Prirodzene cisla. Reprezentacie prirodzenych cisel: monadicka, binarna, dyadicka, parova.

♦

Primitivna rekurzia. Rekurzia s mierou. Binarna a dyadicka aritmetika.

♦

Zoznamy. Triedenie zoznamov. Kombinatoricke funkcie. Aritmetizacia pomocou zoznamov.

♦

Binarne stromy. Binarne prehladavacie stromy. Perfektne vyvazene stromy.

♦

Symbolicke vyrazy. Aritmeticke vyrazy. Vyrokova logika.

♦

1.

Uvod do logiky prveho radu.
Tautologie. Vyrokovologicke vyplyvanie a veta o kompaktnosti. Kvazitautologie. Logicka platnost a logicke
vyplyvanie. Zakladna veta logiky prveho radu. Godelova veta o uplnosti pre tablovy dokazovaci system.
Peanova aritmetika.

2.

Numericka matematika

Odhady nepresnosti vypoctov. Aproximacie funkcii polynomami. Interpolacia. Numericka kvadratura. Metoda
najmensich stvorcov. Newtonova metoda. Metoda regula falsi. [Systemy linearnych algebraickych rovnic. Gaussova
eliminacia.] Numericke riesenie nelinearnych rovnic, systemy nelinearnych rovnic.

Pravdepodobnost a matematicka statistika

Definicia a vlastnosti pravdepodobnosti. Pojem nahodnej premennej. Diskretne a spojite nahodne premenne. Stredna
hodnota nahodnej premennej a jej vypocet. Disperzia. Nezavislost. Bernoulliho schema. [Zakon velkych cisel.
Centralna limitna veta.] Podmienena pravdepodobnost. Bayesov vzorec. Definicia podmienenej pravdepodobnosti.
Pojem nahodneho vyberu. Regresne priamky, koeficient korelacie. Testovanie statistickych hypotez. Intervalove
odhady.

3

Zaklady informatiky

Programovanie

Podprogramy, odovzdavanie parametrov, rekurzia. Metoda vyhladavania s navratom (backtracking). Vstup a vystup,
(standardne) V/V subory, textove a binarne subory. Realizacia datovych struktur (zasobnik, front, spajane zoznamy,
stromy, vyhladavacie stromy, grafy, mnoziny, ...) Rozne triediace algoritmy, vyhladavanie. Objekty v jazyku Pascal
(dedicnost, zapuzdrenie, polymorfizmus).

Principy tvorby software

Diagram datovych tokov. Entitno−relacny diagram a diagram tried. Strukturovane metody analyzy (Yourdonova
metoda). Objektovo−orientovane metody analyzy (metoda OMT). Metoda riadenia projektov (metoda PRINCE).

Teoria programovania

Programove schemy. Zakladne pojmy (standardna schema, interpretacia schem, vlastnosti schem).
(Ne)rozhodnutelnost vlastnosti standardnych schem. Podtriedy standardnych schem s rozhodnutelnymi vlastnostami
(volne, Janovove schemy). Porovnavanie a preklad tried schem − vztahy medzi triedami standardnych a rekurzivnych
schem. Ciastocne interpretovane schemy.

Spravnost programov. Ciastocna a totalna spravnost programov. Invarianty a induktivne formuly. Metody
dokazovania ciastocnej a totalnej spravnosti − indukcne techniky. Najslabsia vstupna a najsilnejsia vystupna
podmienka. Systematicky vyvoj korektnych programov.

Semantika programov a jazykov. Vyznam programu. Principy operacnej, denotacnej a axiomatickej semantiky.
Semanticke domeny a ich konstrukcia. Formalna definicia (operacneho a denotacneho) vyznamu imperativnych a
rekurzivnych programov. Porovnanie operacnej a denotacnej semantiky imperativnych a rekurzivnych programov.
Korektnost vypoctovych pravidiel a kriteria ich korektnosti.

Principy pocitacov

Kodovanie informacii v pocitaci, Booleovske funkcie a ich realizacia pomocou DNF, minimalizacia DNF, navrh
kombinacnych a sekvencnych obvodov, digitalne systemy.

Zakladne principy cinnosti pocitaca von Neumannovskeho typu. Mikroinstrukcny subor, mnozina registrov, ALU,
spracovanie instrukcii, osetrenie preruseni, mikroprogramovanie, RISC versus CISC. Pamat, operacna, pomocna,
cache, virtualna. I/O zariadenia, metody I/O udajov, periferne zariadenia.

Operacne systemy

Vyznam pouzivania jazyka assemblera. Assembler: typy instrukcii, zakladne sposoby adresovania (registrovy
mod, nepriamy registrovy mod, autoinkrement, autodekrement, relativny mod).

1.

Makra − definicia, rozvoj, volanie. Assembler − ulohy, jedno− a dvojprechodovy assembler. Makroprocesor −

2.

4

ulohy, jedno− a dvojprechodovy makroprocesor, makroassembler.
Struktura operacneho systemu, funkcie a sluzby operacneho systemu − systemove volania, zakladne prvky
pocitacoveho systemu − procesy a subory.

3.

Procesy − vytvaranie, hierarchia procesov, zivotny cyklus procesu, komunikacia medzi procesmi.

4.

Synchronizacia procesov − casova zavislost procesov, vzajomne vylucenie a sposoby jeho dosiahnutia,
klasicke problemy synchronizacie procesov.

5.

Uviaznutie − kriteria pre jeho vznik, metody riesenia problemu uviaznutia.

6.

Sprava procesov a procesora − planovace a ich funkcie, algoritmy planovania procesov.

7.

Sprava pamate − funkcie, transformacia adries, modely realnej pamate (typy spravy pamate: holy pocitac,
jeden suvisly usek, staticke suvisle useky, dynamicke suvisle useky, strankovanie, segmentacia).

8.

Sprava pamate − modely virtualnej pamate, strankovanie − vypadok stranky, nahradzovacie algoritmy,
strankovanie na ziadost a pracovna mnozina, niektore problemy pri implementacii − zalohovanie instrukcii,
zamykanie stranok v pamati, zdielanie stranok.

9.

Sprava suborov − funkcie, subory, adresare (typy, organizacia, implementacia), sprava volneho diskoveho
priestoru, sprava priestoru prideleneho suboru (DOS, UNIX), zdielane subory (linky).

10.

Sprava zariadeni − funkcie spravy zariadeni, technicke charakteristiky perifernych zariadeni (delenie V/V
zariadeni, pojem riadiaca jednotka, priamy pristup do pamate), techniky pridelovania V/V zariadeni, V/V
software, sprava diskovych poziadaviek.

11.

Databazove systemy

Datove modely. Entitno−relacny model. [Bachmanove diagramy.] Relacny model.

1.

Architektura DBMS a modelovanie reality. Trojschemova architektura (ANSI sparc).

2.

Relacny model. Relacna algebra. Tabulkova a predikatova interpretacia relacnej algebry. Negacia, domenovo
nezavisle a bezpecne formuly. Relacny kalkul (domenovy). Relacny jazyk SQL. Programovanie v SQL. Ine
dotazove jazyky (QBE, Datalog).

3.

Teoria navrhovania relacnych baz dat. Funkcne zavislosti, vyplyvanie, Armstrongove axiomy, efektivne
odvodenie. Normalne formy 3NF, BCNF. Algoritmy pre upravu do normalnych foriem.

4.

Transakcie a spracovanie transakcii. Seriovatelnost, test seriovatelnosti. Zamky a zamykacie protokoly.
Journal, commit a rollback. Optimisticke a pesimisticke riadenie transakcii, casove razitka.

5.

Bezpecnost v databazovych systemoch. Autorizacia, metody ochrany pred neopravnenym pristupom. Ochrana
dat pred poskodenim a znicenim − backup.

6.

Fyzicka organizacia. Dvojurovnovy model pamati a organizacie dat. Indexove subory. B a B^*−stromy.
Hasovane subory. Dotazy na ciastocnu zhodu. Realizacia relacnych operacii. Kompresia dat (staticke metody,
Ziv−Lempel).

7.

Specifikacia a verifikacia programov

Specifikacia a verifikacia programov v Peanovej aritmetike. Odvodene induktivne principy. Indukcia s mierou a
strukturalna indukcia. Ich redukcia do matematickej indukcie. Binarna a dyadicka aritmetika, zoznamy, polia, stromy,
symbolicke vyrazy.

Formalne jazyky a automaty

Regularne jazyky. Deterministicke a nedeterministicke konecne automaty, regularne gramatiky, regularne vyrazy,
ekvivalencia popisov regularnych jazykov, Nerodova veta, pumpovacia lema, uzaverove vlastnosti. Bezkontextove
jazyky. Bezkontextove gramatiky, normalne tvary, nedeterministicke zasobnikove automaty, ekvivalencia
zasobnikovych automatov a bezkontextovych gramatik, uzaverove vlastnosti. Kontextove jazyky. Kontextove

5

gramatiky, linearne ohranicene automaty, ich ekvivalencia, uzaverove vlastnosti. Rekurzivne vycislitelne a rekurzivne
jazyky. Turingove stroje, frazove gramatiky, ich ekvivalencia, uzaverove vlastnosti, univerzalny Turingov stroj,
Turingova hypoteza. Nerozhodnutelne problemy. Diagonalizacia, problem zastavenia, Postov problem,
nerozhodnutelne problemy pre bezkontextove jazyky, rozhodnutelne problemy pre bezkontextove jazyky, metody
dokazovania nerozhodnutelnosti.

Efektivne algoritmy

Problem slovnika (2−3 stromy). Union/Find−Set problem. Algoritmy pre hladanie najkratsich ciest a najlacnejsej
kostry grafu. Principy tvorby efektivnych algoritmov (vratane konkretnych aplikacii). Rozdeluj a panuj. Dynamicke
programovanie. "Greedy" algoritmy, vyvazenost a volba vhodnej datovej struktury. Triedy P a NP, polynomialna
redukovatelnost, [Cookova veta] a NP−uplne problemy.

Algoritmy a datove struktury

Matematicke zaklady. Asymptoticke oznacenia pre rast funkcii. Porovnanie funkcii na baze asymptotickych
oznaceni. Iterativna logaritmicka funkcia (log^*). Riesenie rekurencii substituciou, iterativne, rekurzivne
stromy − master metoda.

1.

Algoritmy triedenia. Elementarne, Heapsort, BottomUp Heapsort, Quicksort, znahodneny Quicksort −
analyza algoritmu. Halda, prioritna fronta. Dolny odhad pre triedenia porovnavanim.

2.

Linearne triedenia. Counting−sort, Radix−sort, Bucket−sort.

3.

Elementarne datove struktury. Elementarne datove struktury, ich implementacia, zasobnik, rad, zoznam,
strom.

4.

Hasovane tabulky. Tabulky s priamou adresaciou, hasovanie so zretazenim, s otvorenou adresaciou,
univerzalne hasovanie.

5.

Vyspelejsie datove struktury. Binarne prehladavacie stromy a problem vyvazenosti, cervenocierne stromy.

6.

Vyspelejsie techniky tvorby algoritmov. Dynamicke programovanie, nasobenie retazca matic; greedy
algoritmy, knapsack problem, Huffmanovo kodovanie.

7.

6