m
(nove statnicove bakalarske otazky)
Line 14: Line 14:
 
* skúška z predmetu štátnej záverečnej skúšky Aplikovaná informatika – [[#Obsah štátnej záverečnej skúšky z predmetu Aplikovaná informatika|obsah]].
 
* skúška z predmetu štátnej záverečnej skúšky Aplikovaná informatika – [[#Obsah štátnej záverečnej skúšky z predmetu Aplikovaná informatika|obsah]].
  
Štátna skúška bude '''22.6.''' až '''23.6.2016''' na Katedre aplikovanej informatiky (miestnosť a čas budú upresnené neskôr). Prezentácia bakalárskej práce trvá '''15 minút''' vrátane diskusie, ciže 10-12 minút na prejav. Dodržanie času bude tiež jednou zložkou hodnotenia na obhajobe.
+
Štátna skúška bude '''26.6.''' až '''27.6.2017''' na Katedre aplikovanej informatiky (miestnosť a čas budú upresnené neskôr). Prezentácia bakalárskej práce trvá '''15 minút''' vrátane diskusie, ciže 10-12 minút na prejav. Dodržanie času bude tiež jednou zložkou hodnotenia na obhajobe.
  
 
'''Opravný termin štátnej skúšky bude 30. 8. 2016 o 9h. Obhajované práce je potrebné odovzdať do 3. 8. 2016. Aktuálne štátnicové otázky s vysvetlením: [[Media:Bakalarske_statnice_opravne.pdf|Bakalárske štátnice opravné]]
 
'''Opravný termin štátnej skúšky bude 30. 8. 2016 o 9h. Obhajované práce je potrebné odovzdať do 3. 8. 2016. Aktuálne štátnicové otázky s vysvetlením: [[Media:Bakalarske_statnice_opravne.pdf|Bakalárske štátnice opravné]]
Line 24: Line 24:
 
== Obsah štátnej záverečnej skúšky z predmetu Aplikovaná informatika ==
 
== Obsah štátnej záverečnej skúšky z predmetu Aplikovaná informatika ==
  
Vyberajú sa dve otázky: jedna z oblasti matematiky, druhá z oblasti programovania. Každá otázka (matematika, programovanie) pozostáva z dvoch podotázok.
+
Študent si zvolí jednu otázku, ktorá bude spravidla pozostávať z troch častí, každá z jedného z doleuvedených okruhov.
  
[[State Examinations for Bachelor Program in Applied Informatics - students for students starting in the academic year 2013/2014 or earlier|Štátne záverečné skúšky bakalárskeho programu Aplikovaná informatika - pre šudentov, ktorí začali štúdium v akademickom roku 2013/2014 alebo skôr]]
+
Pozri tiež: [[State Examinations for Bachelor Program in Applied Informatics - students for students starting in the academic year 2013/2014 or earlier|Štátne záverečné skúšky bakalárskeho programu Aplikovaná informatika - pre šudentov, ktorí začali štúdium v akademickom roku 2013/2014 alebo skôr]]
  
=== Matematika I (Analýza) ===
+
=== Matematika a teoretická informatika ===
  
# Funkcie reálnej premennej: reálne čísla, funkcia reálnej premennej ako zobrazenie R —> R, definičný obor a obor hodnôt, graf funkcie; pojem zloženej a inverznej funkcie; elementárne funkcie (mocnina, polynóm, racionálna funkcia, odmocnina, exponenciálna funkcia a logaritmus, goniometrické a cyklometrické funkcie).
+
# Základné kombinatorické konfigurácie. Binomické koeficienty. Princíp zapojenia a vypojenia.
# Limita číselnej postupnosti: pojem limity postupnosti, vlastná a nevlastná limita, základné vlastnosti, pojem číselného radu a jeho súčtu, absolútna a neabsolútna konvergencia, d'Alambertovo a Cauchyho kritérium konvergencie.
+
# Typy dôkazov. Priamy a nepriamy dôkaz. Dôkaz sporom. Matematická indukcia.
# Limita funkcie (vlastná a nevlastná limita, limita v nevlastných bodoch); spojitost funkcie; mocninné rady, polomer konvergencie, mocninné rozvoje niektorých elementárnych funkcií (exponenciálna funkcia, sin x, cos x).
+
# Diskrétne číselné množiny: Z, N. Základy teórie čísel. Deliteľnosť. Prvočísla. Modulárna aritmetika. Rekurzia.
# Pojem derivácie funkcie, geometrický význam derivácie; základné vlastnosti derivácií (lineárna kombinácia funkcií, súčin a podiel funkcií, zložená funkcia); derivácie elementárnych funkcií; l'Hospitalovo pravidlo.
+
# Diskrétna pravdepodobnosť. Experiment. Udalosť̌. Nezávislé udalosti. Podmienená pravdepodobnosť.
# Pojem neurčitého integrálu a primitívna funkcia, primitívne funkcie k niektorým elementárnym funkciám, základné pravidlá integrovania, substitučná metóda a metóda per-partes; určitý integrál a jeho geometrický význam.
+
# Zobrazenia. Injektívne, surjektívne a bijektívne zobrazenia. Inverzné zobrazenia.
 +
# Limita a spojitosť funkcii jednej reálnej premennej.
 +
# Derivácia funkcii jednej reálnej premennej a jej využitie pri vyšetrovaní priebehu funkcii.
 +
# Primitívna funkcia a Riemannov určitý integrál a metódy ich výpočtu.
 +
# Výroková logika: symboly jazyka, formula, vytvárajúci strom formuly, ohodnotenie výrokových premenných, relácia splnenia formuly pri ohodnotení́; tautológia, splniteľnosť formuly; výrokovo logické vyplývanie, (ne)splniteľnosť množiny formúl a ich vzájomný vzťah
 +
# Deterministický konečný automat (definícia, konfigurácia, krok výpočtu, výpočet, jazyk, ktorý akceptuje)
 +
# Nedeterministický konečný automat (definícia, konfigurácia, krok výpočtu, výpočet, jazyk, ktorý akceptuje)
 +
# Turingov stroj, porovnanie s konečným automatom.
 +
# Existuje jazyk, ktorý sa nedá rozpoznať žiadnym TS?
  
=== Matematika II (Algebra a geometria) ===
 
  
# Priestory R^2 a R^3: kartézske súradnice, Euklidovská vzdialenosť (metrika); priamky a roviny; polárne a sférické súradnice. Skalárny súčin jeho vlastnosti, vektorový súčin v R^3, uhol medzi priamkami a rovinami, vzdialenosť bodu od priamky a roviny.
+
=== Programovanie a dátové štruktúry ===
# Vektorové priestory, lineárna nezávislosť, dimenzia, báza; skalárny súčin, norma, vzdialenosť, metrika, ortogonálna báza; lineárne transformácie; ilustrácia na priestoroch R^2 a R^3.
+
# Pojem (reálnej alebo komplexnej) matice, lineárne kombinácie, súčin matíc, transponovaná matica, hodnosť matice; determinant štvorcovej 2x2 a 3x3 matice; vlastnosti determinatov, výpočet determinantov úpravou na triangulárny tvar; inverzná matica a jej výpočet.
+
# Sústavy lineárnych rovníc, maticový zápis, homogénne a nehomegénne sústavy; Cramerovo pravidlo pre riešenie n rovníc pre n neznámych; všeobecné sústavy m rovníc pre n neznámych, metódy riešenia a existencia riešení.
+
  
=== Diskrétna matematika ===
+
# Asymptotická výpočtová zložitosť, notácia veľké O, amortizovaná zložitosť.
 
+
# Úloha abstraktného dátového typu, rozdiely v implementácii v rôznych jazykoch.  
# Typy dôkazov. Priamy a nepriamy dôkaz. Dôkaz sporom. Matematická indukcia.
+
# Ošetrovanie chýb, assert, výnimky, testy, rozdiely v rôznych jazykoch.
# Základné enumeračné pravidlá: pravidlo súčtu a súčinu. Variácie bez a s opakovaním. Odvodenie počtu.
+
# Lineárne dátové štruktúry (zoznam, front, zásobník), efektívna implementácia pomocou dynamických dátových štruktúr. Rozdiely v implementácii v rôznych jazykoch.
# Permutácie bez a s opakovaním. Odvodenie počtu. Multinomická veta.
+
# Stromové dátové štruktúry. Rozdiely v implementácii pomocou dynamických dátových štruktúr v rôznych jazykoch.
# Kombinácie bez a s opakovaním. Odvodenie počtu. Usporiadané partície čísel.
+
# Algoritmy prechádzania stromových dátových štruktúr. Možnosti realizácie pomocou lazy algoritmov v rôznych jazykoch.
# Binomické koeficienty. Ich základné vlastnosti. Pascalova formula a Pascalov trojuholník. Binomická veta.
+
# Efektívne realizácie dátovej štruktúry asociatívneho poľa. Riešenie kolízií. Implementácie asociatívneho poľa v rôznych jazykoch.
# Princíp zapojenia a vypojenia. Problém šatniarky: formulácia a riešenie.
+
# Efektívne realizácie dátových štruktúr Set a Multiset. Porovnanie implementácií v rôznych jazykoch.
# Prirodzené a celé čísla. Neúplný podiel a zvyšok po delení. Najväčší spoločný deliteľ. Euklidov algoritmus.
+
# Rozdeľuj a panuj triediace algoritmy. Využitie rekurzie, možné problémy s rekurziou v rôznych jazykoch. Vlastnosti algoritmu merge-sort zdola nahor.  
# Prvočísla a zložené čísla. Základné vlastnosti prvočísel. Rozklad čísla na prvočinitele. Základná veta aritmetiky.
+
# Efektívna realizácia operácií prioritného frontu PriorityQueue. Porovnanie implementácií v rôznych jazykoch.
# Vybrané číselné postupnosti: aritmetická a geometrická postupnosť, Fibonacciho čísla. Ich základné vlastnosti. Súčet prvých n členov postupnosti.
+
# Rýchle algoritmy hľadania podreťazca v reťazci. Kompresia textov a Huffmanovo kódovanie. Porovnanie implementácií v rôznych jazykoch.
# Rekurentné vzťahy. Lineárne homogénne rekurentné vzťahy s konštantnými koeficientami. Prípady rôznych a rovnakých reálnych koreňov.
+
# Spôsoby prehľadávania stavového priestoru, do hĺbky a do šírky, backtracking. Porovnanie implementácií v rôznych jazykoch.
# Množiny. Paradoxy teórie množín. Základné vzťahy a operácie. Potenčná množina. Karteziánsky súčin.
+
# Efektívne reprezentácie dátovej štruktúry graf. Využitie problému Union-find pri hľadaní kostry grafu.  
# Binárne relácie. Maticová a grafická reprezentácia relácie. Skladanie relácií. Opačná (inverzná) relácia. Obraz a vzor množiny v relácii. Jednoznačné a všade definované relácie.
+
# Relácie na množine. Základné vlastnosti relácií na množine. Reflexivita a ireflexivita. Symetria, antisymetria a asymetria. Tranzitivita.
+
# Relácia ekvivalencie a rozklad množiny. Ich vzájomný vzťah. Systém zvyškových tried podľa modulu.
+
# Čiastočné a lineárne usporiadania. Hasseho diagram usporiadania. Minimálny a maximálny prvok. Najmenší a najväčší prvok. Supremum a infimum. Zväzy.
+
# Zobrazenia. Zúženie a rozšírenie zobrazenia. Zložené zobrazenie. Inverzné zobrazenie. Obraz a vzor množiny v zobrazení.
+
# Injektívne, surjektívne a bijektívne zobrazenia.
+
 
+
=== Algoritmy a dátové štruktúry ===
+
 
+
<ol><li value="1">Operácie '''enqueue''' a '''degueue''' pre dátovú štruktúru front ('''Queue''') sa často realizujú (dynamickým) poľom: pridávaním na koniec, resp. odoberaním prvého prvku poľa. Odoberanie prvého prvku je v niektorých programovacích jazykoch časovo náročná operácia. Navrhnite takú reprezentáciu frontu, aby boli tieto dve metódy čo možno najefektívnejšie, napr. pomocou spájaného zoznamu, resp. asociatívnym poľom. Zapíšte obe operácie.<br/>Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.</li></ol>
+
 
+
<ol><li value="2">Vieme, že '''rekurzívny''' algoritmus pre výpočet n-tého fibonacciho čísla pomocou súčtu dvoch predchodcov tejto postupnosti, je veľmi neefektívny. Prepíšte tento algoritmus tak, aby sa využila '''memoizácia'''. Odhadnite zložitosť takto vylepšeného rekurzívneho algoritmu.<br/>Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.</li></ol>
+
 
+
<ol><li value="3">Algoritmus '''preorder''' prechádza vrcholy binárneho stromu v presnom poradí. Zapíšte funkciu, ktorá umožní získavať vrcholy presne v poradí '''preoreder''': prvé volanie vráti prvý vrchol tejto postupnosti, každé ďalšie volanie vráti nasledovný vrchol postupnosti alebo spôsobí vyvolanie výnimky, ak sa už prešli všetky vrcholy stromu.<br/>Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.</li></ol>
+
 
+
<ol><li value="4">Pre dátovú štruktúru všeobecný strom ('''Tree''') zapíšte tieto dve funkcie:
+
* funkcia hĺbka ('''depth''') pre konkrétny vrchol vráti vzdialenosť tohto vrcholu od koreňa (môžete predpokladať, že v každom vrchole je informácia o otcovi ('''parent'''))
+
* funkcia výška ('''height''') vráti výšku celého stromu, pričom postupne vypočíta hĺbku ('''depth''') všetkých listov stromu – z týchto hĺbok zistí maximum
+
Odhadnite zložitosť (najhoršieho prípadu) algoritmu '''height''' pre strom s '''n''' vrcholmi.<br/>Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.</li></ol>
+
 
+
<ol><li value="5">Algoritmus triedenia '''merge-sort''' sa dá realizovať nerekurzívne zdola nahor. Zapíšte tento algoritmus a porovnajte jeho zložitosť s algoritmom '''quick-sort'''. Môžete predpokladať, že máte k dispozícii funkciu '''merge''', ktorá z dvoch utriedených polí vytvorí nové pole ich zlúčením (zložitosti '''O(n1+n2)''').<br/>Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.</li></ol>
+
 
+
<ol><li value="6">Na realizáciu dátového typu asociatívne pole ('''Map''') sa najčastejšie využívajú hašovacie tabuľky. Zapíšte metódy na:
+
* vloženie do tabuľky dvojice (kľúč, hodnota)
+
* nájdenie hodnoty pre zadaný kľúč
+
* vyhodenie dvojice (kľúč, hodnota)
+
Zvoľte si vhodný spôsob riešenia kolízií. Odhadnite zložitosť vašich metód.<br/>Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.</li></ol>
+
 
+
<ol><li value="7">Navrhnite realizácie dátových typov množina ('''Set''') a tiež množina, v ktorej môžu byť prvky aj viackrát ('''MultiSet'''). Využite existujúci typ asociatívne pole ('''Map'''). Zdôvodnite, ktoré zo základných operácií s týmito dátovými typmi (vloženie, zistenie, vyhodenie) budú mať horšiu zložitosť ako '''O(1)'''.<br/>Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.</li></ol>
+
 
+
<ol><li value="8">Zapíšte operácie vloženia ('''add''') a vybratia najmenšieho prvku ('''remove_min''') pre prioritný front ('''PriorityQueue''') tak, aby zložitosť každej z nich bola lepšia ako '''O(N)'''. Zdôvodnite.<br/>Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.</li></ol>
+
 
+
=== Programovanie ===
+
 
+
# Triedy, ukrývanie implementácie, dedenie, virtuálne dedenie, typy konštruktorov, deštruktory, príklady v Free Pascal, C++, Java alebo Python.
+
# Abstraktný dátový typ a jeho implementácia triedou, príklady v Free Pascal, C++, Java alebo Python.
+
# Parametrický polymorfizmus, preťažovanie, preťažovanie operátorov, príklady v Free Pascal, C++, Java alebo Python.
+
# Šablóny, typy šablón, kontajnery, kolekcie, príklady v Free Pascal, C++ alebo Java.
+
# Smerníky, smerníková aritmetika, dynamická alokácia pamäti, smerníky na smerníky a na funkcie. Príklady v Free Pascal alebo C++.
+
# Procesy a vlákna (thready), konkurentné programovanie, spôsoby komunikácie a synchronizácie procesov, kritické oblasti, semafory a príklad v konkrétnom jazyku.
+
# Ošetrovanie chýb, assert, výnimky, testy,  a príklad v Free Pascal, C++, Java alebo Python.
+
# Lineárne dátové štruktúry (zoznam, front, prioritný front), príklad ich implementácie pomocou dynamických dátových štruktúr v jazyku Free Pascal, C++, Java alebo Python.
+
# Spôsoby prehľadávania stavového priestoru, do hĺbky a do šírky, backtracking. Príklad v jazyku Free Pascal, C++, Java alebo Python.
+
# Tvorba informačných systémov - modely vývoja softvéru, fázy vývoja - špecifikácia, návrh, integrácia, testovanie, údržba, Ganttov diagram, UML, návrhové vzory.
+
 
+
=== Úvod do teoretickej informatiky ===
+
# Výpočtový model, základné charakteristiky.
+
# Deterministický konečný automat (definícia, konfigurácia, krok výpočtu, výpočet, jazyk, ktorý akceptuje)
+
# Nedeterministický konečný automat (definícia, konfigurácia, krok výpočtu, výpočet, jazyk, ktorý akceptuje)
+
# Porovnanie deterministického a nedeterministického  konečného automatu
+
# Techniky návrhu deterministického konečného automatu
+
# Turingov stroj a konečný automat, porovnanie
+
# Determinizmus vs. nedeterminizmus (ako sa definuje na konečných automatoch a TS). Praktické dôsledky na uvedených modeloch.
+
# Jednopáskový, viacpáskový, deterministický a nedeterministický TS
+
# Dôkazy neriešiteľnosti problému v danom výpočtovom modeli (konečný automat, TS.)
+
  
=== Počítačová grafika a spracovanie obrazu ===
 
  
# Referenčný model počítačovej grafiky. Základná geometria scény, súradnicové systémy a transformácie medzi nimi. Zobrazovací kanál (rendering pipeline).
+
=== Aplikovaná informatika ===
# Viditeľnosť, rasterizácia, textúry a antialiasing.
+
# Osvetlenie a tieňovanie, tiene, animácia a kódovanie.
+
# Snímanie obrazu a jeho vlastnosti (škála, šum, metriky).
+
# Predspracovanie obrazu v priestorovej a frekvenčnej oblasti.
+
  
Odporučená literatúra z počítačovej grafiky:
+
# Počítačové systémy: Základné logické funkcie a ich realizácia. Boolovské funkcie. Niektoré kombinačné obvody (sčítačka, multiplexor a demultiplexor).
* Ružický, E., Ferko, A. : Počítačová grafika a spracovanie obrazu
+
# Organizácia počítačových systémov - vrstvový model počítača, súvislosti medzi vrstvami. Procesor (mikroprocesor, ALU, realizácia inštrukcií), vnútorná a vonkajšia pamäť, prídavné zariadenia, zbernica z hľadiska hardvéru aj softvéru.
* Žára, J. a kolektív : Moderní počítačová grafika
+
# Operačný systém pri pohľade zvonku (služby, ich význam z pohľadu vyšších vrstiev vrstvového modelu počítača) a zvnútra (správa procesov, správa pamäti, správa zariadení a správa súborov). Hlavné úlohy jednotlivých správ.
* Šikudová E. a kol.: Počítačové videnie: detekcia a rozpoznávanie objektov
+
# Synchronizácia procesov a vlákien – zdieľanie údajov, časová závislosť, vzájomné vylúčenie, kritická sekcia, deadlock, busy waiting.
 +
# Správa pamäti: jednoduchá správa pamäti, virtuálna pamäť, stránkovanie, segmentovanie. Algoritmy výmeny stránok.
 +
# Správa zariadení a správa súborov: radič, spôsoby prenosu údajov medzi radičom a pamäťou. software správy zariadení. Pojem súbor a adresár, druhy súborov, spôsoby kódovania znakov v textových súboroch. Implementácia súborového systému.
 +
# Sieťová architektúra, vrstvové modely, služby – vrstva, rozhranie, protokol, fyzický a logický tok údajov. Kľúčové problémy pri návrhu sietí.
 +
# Bezpečnosť sietí – bezpečnostné problémy a mechanizmy na rôznych vrstvách – VLAN,
 +
# Navrhovanie databáz: relačný model dát, kardinalita vzťahov
 +
# Modelovanie a návrh: entitno-relačný diagram, diagram dátových tokov, UML diagramy: use-case, stavový, activity, sekvenčný, komponentný, triedny, deployment. Študent vie nakresliť príklad každého diagramu a vysvetliť ho.
 +
# Web: základná štruktúra dokumentu, metadáta, sekcie a nadpisy, zgrupovanie a elementy s text-level sémantikou, formuláre. Vlastnosti CSS, ich hodnoty, selektory, box model, statické, relatívne, absolútne a fixné polohovanie, media queries.
 +
# Javascript: základné údajové štruktúry, práca s objektami. Document object model. Úloha a význam JS na strane klienta a na strane servera.
 +
# Klientské vs. serverové webové aplikácie, princíp fungovania, vysvetlenie sieťovej komunikácie a jej spracovania.
  
  
 
[[Category:Bakalársky program Aplikovaná informatika]]
 
[[Category:Bakalársky program Aplikovaná informatika]]

Revision as of 09:55, 28 March 2017

Štátne záverečné skúšky,
študijný odbor 9.2.9. aplikovaná informatika, bakalárske štúdium

Garant: Doc. RNDr. Damas Gruska, PhD.
gruska @ ii.fmph.uniba.sk

Oznamujem študentom, že augustový termín štátnych skúšok je výlučne opravným termínom a nie je možné sa naň prihlásiť ako na prvý termín. Tento postup bol zvolený po dohode s pani študijnou prodekankou.

Úvodné poznámky

Štátne skúšky sa konajú z povinných predmetov bakalárskeho štúdia odboru Aplikovaná informatika a majú za úlohu zistiť, nakoľko študent zodpovedá profilu absolventa bakalárskeho štúdia. Štátna skúška pozostáva z dvoch častí (sylaby k bakalárskym štátniciam ostávajú v platnosti):

  • obhajoba bakalárskej práce – odporúčania
  • skúška z predmetu štátnej záverečnej skúšky Aplikovaná informatika – obsah.

Štátna skúška bude 26.6.27.6.2017 na Katedre aplikovanej informatiky (miestnosť a čas budú upresnené neskôr). Prezentácia bakalárskej práce trvá 15 minút vrátane diskusie, ciže 10-12 minút na prejav. Dodržanie času bude tiež jednou zložkou hodnotenia na obhajobe.

Opravný termin štátnej skúšky bude 30. 8. 2016 o 9h. Obhajované práce je potrebné odovzdať do 3. 8. 2016. Aktuálne štátnicové otázky s vysvetlením: Bakalárske štátnice opravné

Študenti si musia zabezpečiť vlastný notebook, na ktorom budú prezentovať svoje bakalárske práce.

Tí, čo si dávajú prihlášku na bakalárske štátnice, mali by v nej explicitne uviesť, že chcú aj obhajovať bakalársku prácu. Tí, ktorí už prihlášku dali a neuviedli explicitne, že idú aj obhajovať bakalárku, tak nemusia dodatočne urobiť. Len v prípade, ze NEJDÚ obhajovať, nech to zahlásia na študijnom oddelení.

Obsah štátnej záverečnej skúšky z predmetu Aplikovaná informatika

Študent si zvolí jednu otázku, ktorá bude spravidla pozostávať z troch častí, každá z jedného z doleuvedených okruhov.

Pozri tiež: Štátne záverečné skúšky bakalárskeho programu Aplikovaná informatika - pre šudentov, ktorí začali štúdium v akademickom roku 2013/2014 alebo skôr

Matematika a teoretická informatika

  1. Základné kombinatorické konfigurácie. Binomické koeficienty. Princíp zapojenia a vypojenia.
  2. Typy dôkazov. Priamy a nepriamy dôkaz. Dôkaz sporom. Matematická indukcia.
  3. Diskrétne číselné množiny: Z, N. Základy teórie čísel. Deliteľnosť. Prvočísla. Modulárna aritmetika. Rekurzia.
  4. Diskrétna pravdepodobnosť. Experiment. Udalosť̌. Nezávislé udalosti. Podmienená pravdepodobnosť.
  5. Zobrazenia. Injektívne, surjektívne a bijektívne zobrazenia. Inverzné zobrazenia.
  6. Limita a spojitosť funkcii jednej reálnej premennej.
  7. Derivácia funkcii jednej reálnej premennej a jej využitie pri vyšetrovaní priebehu funkcii.
  8. Primitívna funkcia a Riemannov určitý integrál a metódy ich výpočtu.
  9. Výroková logika: symboly jazyka, formula, vytvárajúci strom formuly, ohodnotenie výrokových premenných, relácia splnenia formuly pri ohodnotení́; tautológia, splniteľnosť formuly; výrokovo logické vyplývanie, (ne)splniteľnosť množiny formúl a ich vzájomný vzťah
  10. Deterministický konečný automat (definícia, konfigurácia, krok výpočtu, výpočet, jazyk, ktorý akceptuje)
  11. Nedeterministický konečný automat (definícia, konfigurácia, krok výpočtu, výpočet, jazyk, ktorý akceptuje)
  12. Turingov stroj, porovnanie s konečným automatom.
  13. Existuje jazyk, ktorý sa nedá rozpoznať žiadnym TS?


Programovanie a dátové štruktúry

  1. Asymptotická výpočtová zložitosť, notácia veľké O, amortizovaná zložitosť.
  2. Úloha abstraktného dátového typu, rozdiely v implementácii v rôznych jazykoch.
  3. Ošetrovanie chýb, assert, výnimky, testy, rozdiely v rôznych jazykoch.
  4. Lineárne dátové štruktúry (zoznam, front, zásobník), efektívna implementácia pomocou dynamických dátových štruktúr. Rozdiely v implementácii v rôznych jazykoch.
  5. Stromové dátové štruktúry. Rozdiely v implementácii pomocou dynamických dátových štruktúr v rôznych jazykoch.
  6. Algoritmy prechádzania stromových dátových štruktúr. Možnosti realizácie pomocou lazy algoritmov v rôznych jazykoch.
  7. Efektívne realizácie dátovej štruktúry asociatívneho poľa. Riešenie kolízií. Implementácie asociatívneho poľa v rôznych jazykoch.
  8. Efektívne realizácie dátových štruktúr Set a Multiset. Porovnanie implementácií v rôznych jazykoch.
  9. Rozdeľuj a panuj triediace algoritmy. Využitie rekurzie, možné problémy s rekurziou v rôznych jazykoch. Vlastnosti algoritmu merge-sort zdola nahor.
  10. Efektívna realizácia operácií prioritného frontu PriorityQueue. Porovnanie implementácií v rôznych jazykoch.
  11. Rýchle algoritmy hľadania podreťazca v reťazci. Kompresia textov a Huffmanovo kódovanie. Porovnanie implementácií v rôznych jazykoch.
  12. Spôsoby prehľadávania stavového priestoru, do hĺbky a do šírky, backtracking. Porovnanie implementácií v rôznych jazykoch.
  13. Efektívne reprezentácie dátovej štruktúry graf. Využitie problému Union-find pri hľadaní kostry grafu.


Aplikovaná informatika

  1. Počítačové systémy: Základné logické funkcie a ich realizácia. Boolovské funkcie. Niektoré kombinačné obvody (sčítačka, multiplexor a demultiplexor).
  2. Organizácia počítačových systémov - vrstvový model počítača, súvislosti medzi vrstvami. Procesor (mikroprocesor, ALU, realizácia inštrukcií), vnútorná a vonkajšia pamäť, prídavné zariadenia, zbernica z hľadiska hardvéru aj softvéru.
  3. Operačný systém pri pohľade zvonku (služby, ich význam z pohľadu vyšších vrstiev vrstvového modelu počítača) a zvnútra (správa procesov, správa pamäti, správa zariadení a správa súborov). Hlavné úlohy jednotlivých správ.
  4. Synchronizácia procesov a vlákien – zdieľanie údajov, časová závislosť, vzájomné vylúčenie, kritická sekcia, deadlock, busy waiting.
  5. Správa pamäti: jednoduchá správa pamäti, virtuálna pamäť, stránkovanie, segmentovanie. Algoritmy výmeny stránok.
  6. Správa zariadení a správa súborov: radič, spôsoby prenosu údajov medzi radičom a pamäťou. software správy zariadení. Pojem súbor a adresár, druhy súborov, spôsoby kódovania znakov v textových súboroch. Implementácia súborového systému.
  7. Sieťová architektúra, vrstvové modely, služby – vrstva, rozhranie, protokol, fyzický a logický tok údajov. Kľúčové problémy pri návrhu sietí.
  8. Bezpečnosť sietí – bezpečnostné problémy a mechanizmy na rôznych vrstvách – VLAN,
  9. Navrhovanie databáz: relačný model dát, kardinalita vzťahov
  10. Modelovanie a návrh: entitno-relačný diagram, diagram dátových tokov, UML diagramy: use-case, stavový, activity, sekvenčný, komponentný, triedny, deployment. Študent vie nakresliť príklad každého diagramu a vysvetliť ho.
  11. Web: základná štruktúra dokumentu, metadáta, sekcie a nadpisy, zgrupovanie a elementy s text-level sémantikou, formuláre. Vlastnosti CSS, ich hodnoty, selektory, box model, statické, relatívne, absolútne a fixné polohovanie, media queries.
  12. Javascript: základné údajové štruktúry, práca s objektami. Document object model. Úloha a význam JS na strane klienta a na strane servera.
  13. Klientské vs. serverové webové aplikácie, princíp fungovania, vysvetlenie sieťovej komunikácie a jej spracovania.