Katedra aplikovanej informatiky

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

Garant: Doc. RNDr. Mária Markošová, PhD.
markosova ii.fmph.uniba.sk

Ú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
• skúška z predmetu štátnej záverečnej skúšky Aplikovaná informatika.

Štátna skúška bude 28.6. až 29.6.2011 na Katedre aplikovanej informatiky (miestnosť a čas budú upresenné 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ávaju 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, nepriamy, sporom, matematická indukcia.
   Dirichletov princíp.
   Základné enumeračné pravidlá – pravidlo súčtu a súčinu.
2. Množiny. Zakladné operácie, karteziánsky súčin.
   Binárne relácie. Reprezentácia pomocou matice a grafu binárnej relácie. Skladanie binárnych relácií.
3. Relácie ekvivalencie a rozklady množín. Definície a vzájomný vzťah.
   Usporiadania a zobrazenia.
4. Variácie bez a s opakovaním. Definície. Odvodenie počtu.
5. Kombinácie bez opakovania. Binomická veta.
6. Kombinácie s opakovaním, permutácie s opakovaním, polynomická veta.
7. Princíp zapojenia a vypojenia.
8. Eulerovské grafy. Charakterizácia. Predlžovací algoritmus na nájdenie eulerovského ťahu.
   Hamiltonovské grafy. Postačujúce podmienky pre existenciu hamiltonovskej kružnice v grafe.
9. Vrcholová a hranová súvislosť grafu.
   Vrcholové a hranové farbenia grafu.
10. Planárne grafy.

Doporučená literatúra z teórie grafov:

• Kvasnička, V., Pospíchal, J.: Algebra a diskrétna matematika, STU Press, Bratislava 2008.
• Matoušek, J., Nešetřil, J.: Kapitoly z diskrétnej matematiky, Nakladatelství Karolinum, Praha 2009 (4. vydanie).
• Znám, Š.: Kombinatorika a teória grafov, MFF UK, Bratislava 1981 (2. vydanie).

Algoritmy a dátové štruktúry

1. Efektívnosť reprezentácie množín (kritériá efektívnosti, porovnanie efektívnosti operácií)
   • bitový vektor
   • pole, spájaný zoznam
   • vyvážené a nevyvážené stromy.
2. Vyhľadávanie informácií v tabuľkách
   • binárne vyhľadávanie
   • hašovanie otvorené a zatvorené, hašovacie funkcie, riešenie kolízií
   • porovnanie zložitosti operácií.
3. Porovnanie triediacich algoritmov
   • napr. merge-sort, quick-sort, heap-sort
   • odhady zložitosti.
4. Dátové štruktúry pre množiny
   • disjunktné množiny s operáciami UNION a FIND
   • viacrozmerné množiny
   • reprezentácia vzťahov typu mnoho-mnoho – multilist.

Programovanie

1. Triedy, ukrývanie implementácie, dedenie, virtuálne dedenie, typy konštruktorov, deštruktory, príklady v Free Pascal, C++ alebo Java.
2. Abstraktný dátový typ a jeho implementácia triedou, príklady v Free Pascal, C++ alebo Java.
3. Parametrický polymorfizmus, preťažovanie, preťažovanie operátorov, príklady v Free Pascal, C++ alebo Java.
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++ alebo Java.
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++ alebo Java.
9. Spôsoby prehľadávania stavového priestoru, do hĺbky a do šírky, backtracking. Príklad v jazyku Free Pascal, C++ alebo Java.

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.

Doporuč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