Line 44: Line 44:
 
# Kombinácie bez a s opakovaním. Odvodenie počtu. Usporiadané partície čísel.
 
# Kombinácie bez a s opakovaním. Odvodenie počtu. Usporiadané partície čísel.
 
# Binomické koeficienty. Ich základné vlastnosti. Pascalova formula a Pascalov trojuholník. Binomická veta.
 
# Binomické koeficienty. Ich základné vlastnosti. Pascalova formula a Pascalov trojuholník. Binomická veta.
 +
# Princíp zapojenia a vypojenia. Problém šatniarky: formulácia a riešenie.
 
# Prirodzené a celé čísla. Neúplný podiel a zvyšok po delení. Najväčší spoločný deliteľ. Euklidov algoritmus. Lineárne diofantické rovnice.
 
# Prirodzené a celé čísla. Neúplný podiel a zvyšok po delení. Najväčší spoločný deliteľ. Euklidov algoritmus. Lineárne diofantické rovnice.
 
# Prvočísla a zložené čísla. Základné vlastnosti prvočísel. Rozklad čísla na prvočinitele. Základná veta aritmetiky.
 
# Prvočísla a zložené čísla. Základné vlastnosti prvočísel. Rozklad čísla na prvočinitele. Základná veta aritmetiky.
Line 49: Line 50:
 
# 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.
 
# 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.
 
# Množiny. Paradoxy teórie množín. Základné vzťahy a operácie. Potenčná množina. Karteziánsky súčin.
 
# Množiny. Paradoxy teórie množín. Základné vzťahy a operácie. Potenčná množina. Karteziánsky súčin.
# Princíp zapojenia a vypojenia. Problém šatniarky: formulácia a riešenie.
 
 
# Binárne relácie. Maticová a grafická reprezentácia relácie. Skladanie relácií. Inverzná relácia. Obraz a vzor množiny v relácií. Jednoznačné a všade definované relácie.
 
# Binárne relácie. Maticová a grafická reprezentácia relácie. Skladanie relácií. Inverzná relácia. Obraz a vzor množiny v relácií. 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ácie na množine. Základné vlastnosti relácií na množine. Reflexivita a ireflexivita. Symetria, antisymetria a asymetria. Tranzitivita.

Revision as of 18:27, 22 February 2012

Š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.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 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. Lineárne diofantické rovnice.
  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í. Inverzná relácia. Obraz a vzor množiny v relácií. 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.
  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. Efektívnosť reprezentácie množín (kritériá efektívnosti, porovnanie efektívnosti operácií)
    • bitový vektor, pole, spájaný zoznam
    • binárny vyhľadávací strom
    • vyvážené stromy.
  2. Vyhľadávanie informácií v tabuľkách
    • sekvenčné a 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
    • popis niektorých triediacich algoritmov, napr. merge-sort, quick-sort, heap-sort
    • zložitosť popísaných algoritmov
    • odhady zložitosti optimálneho algoritmu triediaceho porovnávaním
  4. Dátové štruktúry pre množiny
    • disjunktné množiny s operáciami UNION a FIND
    • viacrozmerné množiny - dotaz na úplnú zhodu, dotaz na čiastočnú zhodu
    • 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