Š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.

Štátna skúška bude 22.6.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.

Š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

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.

Matematika I (Analýza)

  1. 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).
  2. 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.
  3. 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).
  4. 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.
  5. 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.

Matematika II (Algebra a geometria)

  1. 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.
  2. 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.
  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.
  4. 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

  1. Typy dôkazov. Priamy a nepriamy dôkaz. Dôkaz sporom. Matematická indukcia.
  2. Základné enumeračné pravidlá: pravidlo súčtu a súčinu. Variácie bez a s opakovaním. Odvodenie počtu.
  3. Permutácie bez a s opakovaním. Odvodenie počtu. Multinomická veta.
  4. Kombinácie bez a s opakovaním. Odvodenie počtu. Usporiadané partície čísel.
  5. Binomické koeficienty. Ich základné vlastnosti. Pascalova formula a Pascalov trojuholník. Binomická veta.
  6. Princíp zapojenia a vypojenia. Problém šatniarky: formulácia a riešenie.
  7. Prirodzené a celé čísla. Neúplný podiel a zvyšok po delení. Najväčší spoločný deliteľ. Euklidov algoritmus.
  8. Prvočísla a zložené čísla. Základné vlastnosti prvočísel. Rozklad čísla na prvočinitele. Základná veta aritmetiky.
  9. Vybrané číselné postupnosti: aritmetická a geometrická postupnosť, Fibonacciho čísla. Ich základné vlastnosti. Súčet prvých n členov postupnosti.
  10. 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.
  11. Množiny. Paradoxy teórie množín. Základné vzťahy a operácie. Potenčná množina. Karteziánsky súčin.
  12. 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.
  13. Relácie na množine. Základné vlastnosti relácií na množine. Reflexivita a ireflexivita. Symetria, antisymetria a asymetria. Tranzitivita.
  14. Relácia ekvivalencie a rozklad množiny. Ich vzájomný vzťah. Systém zvyškových tried podľa modulu.
  15. Čiastočné a lineárne usporiadania. Hasseho diagram usporiadania. Minimálny a maximálny prvok. Najmenší a najväčší prvok. Supremum a infimum. Zväzy.
  16. Zobrazenia. Zúženie a rozšírenie zobrazenia. Zložené zobrazenie. Inverzné zobrazenie. Obraz a vzor množiny v zobrazení.
  17. Injektívne, surjektívne a bijektívne zobrazenia.

Algoritmy a dátové štruktúry

  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.
    Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.
  1. 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.
    Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.
  1. 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.
    Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.
  1. 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.
    Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.
  1. 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)).
    Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.
  1. 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.
    Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.
  1. 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).
    Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.
  1. 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.
    Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.

Programovanie

  1. Triedy, ukrývanie implementácie, dedenie, virtuálne dedenie, typy konštruktorov, deštruktory, príklady v Free Pascal, C++, Java alebo Python.
  2. Abstraktný dátový typ a jeho implementácia triedou, príklady v Free Pascal, C++, Java alebo Python.
  3. Parametrický polymorfizmus, preťažovanie, preťažovanie operátorov, príklady v Free Pascal, C++, Java alebo Python.
  4. Šablóny, typy šablón, kontajnery, kolekcie, príklady v Free Pascal, C++ alebo Java.
  5. 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++.
  6. 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.
  7. Ošetrovanie chýb, assert, výnimky, testy, a príklad v Free Pascal, C++, Java alebo Python.
  8. 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.
  9. 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.
  10. 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

  1. Výpočtový model, základné charakteristiky.
  2. Deterministický konečný automat (definicia, konfigurácia, krok výpočtu, výpočet, jazyk, ktorý akceptuje)
  3. Nedeterministický konečný automat (definicia, konfigurácia, krok výpočtu, výpočet, jazyk, ktorý akceptuje)
  4. Porovnanie deterministického a nedeterministického konečného automatu
  5. Techniky návrhu deterministického konečného automatu
  6. Turingov stroj a konečný automat, porovnanie
  7. Determinizmus vs. netereminizmus (ako sa definuje na konečných automatoch a TS). Praktické dôsledky na uvedených modeloch.
  8. Jednopáskový, viacpáskový, deterministický a nedeterministický TS
  9. Dôkazy neriešiteľnosti problému v danom výpočtovom modeli (konečný automat, TS.)

Grafické systémy, vizualizácia a multimédiá

  1. Referenčný model počítačovej grafiky. Úloha grafického systému v ňom. Rozhrania medzi súčasťami referenčného modelu a význam pre implementáciu.
  2. Geometrický príestor scény, priestor obrazovky. Súradnicové systémy. Transformácie na objektoch alebo medzi súradnicovými systémami. Maticová reprezentácia.
  3. Zobrazovací kanál (rendering pipeline). Rasterizácia, textúrovanie, antialiasing.
  4. Výpočet osvetlenia, viditeľnosti a tieňov. Príklady realtime a offline algoritmov.
  5. Typy multimédií, kódovanie a kompresia. Príklady postupov a formátov na kódovanie obrazu, zvuku, animácie.

Odporučená literatúra z počítačovej grafiky:

  • Ružický, E., Ferko, A. : Počítačová grafika a spracovanie obrazu
  • Žára, J. a kolektív : Moderní počítačová grafika
  • vlastné poznámky z prednášok