State examinations for Bachelor program in Applied Informatics/sk: Rozdiel medzi revíziami
d |
d |
||
| (30 medziľahlých úprav od 8 ďalších používateľov nie je zobrazených) | |||
| Riadok 1: | Riadok 1: | ||
= Štátne záverečné skúšky, <br>študijný odbor 9.2.9. aplikovaná informatika, bakalárske štúdium = | = Štátne záverečné skúšky, <br>študijný odbor 9.2.9. aplikovaná informatika, bakalárske štúdium = | ||
| + | __TOC__ | ||
| − | '''Garant:''' Doc. RNDr. | + | '''Garant:''' Doc. RNDr. Damas Gruska, PhD.<br> |
| − | '' | + | ''gruska [[Image:zavinac.gif|@]] 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 == | == Úvodné poznámky == | ||
| Riadok 8: | Riadok 11: | ||
Š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): | Š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 | + | * obhajoba bakalárskej práce - [[Ako pripravit prezentaciu pre obhajobu prace|odporúčania]] |
* skúška z predmetu štátnej záverečnej skúšky Aplikovaná informatika. | * skúška z predmetu štátnej záverečnej skúšky Aplikovaná informatika. | ||
| − | Štátna skúška bude ''' | + | Š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. |
Študenti si musia zabezpečiť '''vlastný notebook''', na ktorom budú prezentovať svoje bakalárske práce. | Študenti si musia zabezpečiť '''vlastný notebook''', na ktorom budú prezentovať svoje bakalárske práce. | ||
| − | ''Tí, čo si | + | ''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 == | == Obsah štátnej záverečnej skúšky == | ||
| Riadok 22: | Riadok 25: | ||
<small> | <small> | ||
| − | + | === Matematika I (Analýza) === | |
# 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). | # 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). | ||
| Riadok 30: | Riadok 33: | ||
# 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. | # 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) === | |
# 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. | # 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. | ||
| Riadok 37: | Riadok 40: | ||
# 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í. | # 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 === | |
| − | # | + | # Typy dôkazov. Priamy a nepriamy dôkaz. Dôkaz sporom. Matematická indukcia. |
| − | # | + | # Základné enumeračné pravidlá: pravidlo súčtu a súčinu. Variácie bez a s opakovaním. Odvodenie počtu. |
| − | # | + | # Permutácie bez a s opakovaním. Odvodenie počtu. Multinomická veta. |
| − | # | + | # 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. |
| − | # | + | # 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. |
| − | # | + | # Prvočísla a zložené čísla. Základné vlastnosti prvočísel. Rozklad čísla na prvočinitele. Základná veta aritmetiky. |
| − | # | + | # Vybrané číselné postupnosti: aritmetická a geometrická postupnosť, Fibonacciho čísla. Ich základné vlastnosti. Súčet prvých n členov postupnosti. |
| − | # | + | # 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. | ||
| + | # 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). | |
| − | + | # 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: | |
| − | + | * Ružický, E., Ferko, A. : Počítačová grafika a spracovanie obrazu | |
| − | + | * Žára, J. a kolektív : Moderní počítačová grafika | |
| − | + | * Šikudová E. a kol.: Počítačové videnie: detekcia a rozpoznávanie objektov | |
| − | + | </small> | |
| − | + | ||
| − | + | [[Category:Bakalársky program Aplikovaná informatika]] | |
| − | + | ||
| − | + | ||
Aktuálna revízia z 00:24, 6. máj 2016
Š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. 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.
Š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)
- 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).
- 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.
- 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).
- 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.
- 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)
- 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.
- 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
- Typy dôkazov. Priamy a nepriamy dôkaz. Dôkaz sporom. Matematická indukcia.
- Základné enumeračné pravidlá: pravidlo súčtu a súčinu. Variácie bez a s opakovaním. Odvodenie počtu.
- Permutácie bez a s opakovaním. Odvodenie počtu. Multinomická veta.
- 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.
- 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.
- Prvočísla a zložené čísla. Základné vlastnosti prvočísel. Rozklad čísla na prvočinitele. Základná veta aritmetiky.
- Vybrané číselné postupnosti: aritmetická a geometrická postupnosť, Fibonacciho čísla. Ich základné vlastnosti. Súčet prvých n členov postupnosti.
- 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.
- 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
- 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.
- 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.
- 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.
- 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
Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.
- 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.
- 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)
Na riešenie úlohy si zvoľte jeden z programovacích jazykov: FreePascal, C++, Java, Python.
- 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.
- 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
- 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).
- 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:
- Ružický, E., Ferko, A. : Počítačová grafika a spracovanie obrazu
- Žára, J. a kolektív : Moderní počítačová grafika
- Šikudová E. a kol.: Počítačové videnie: detekcia a rozpoznávanie objektov