Prejsť na obsah

Predmety rigoróznej skúšky – Informatika

8minút, 24sekúnd

Zoznam a anotácie predmetov pre rigoróznu skúšku v odbore INFORMATIKA

Študijné predmety sú rozdelené do skupiny povinných a voliteľných predmetov. Uchádzač si vyberie dva študijné predmety, z ktorých jeden musí byť zo skupiny povinných predmetov a jeden zo skupiny voliteľných predmetov.

Povinné predmety

Automaty a formálne jazyky

Chomského hierachia jazykov a gramatík. Konečnostavový automat, a jeho varianty: deterministické, nedeterministické, alternujúce, pravdepodobnostné, kvantové, atď. Jednosmerné, dvojsmerné, obratovo ohraničené konečnostavové automaty. Regulárne výrazy a gramatiky. Unárne regulárne jazyky a ich vlastnosti. Problematika konštrukcie efektívnych automatov jednotlivých typov, z hľadiska počtu stavov a hrán. Súvislosti medzi teóriou konečnostavových automatov a teóriou zložitosti.                       
Literatúra:
J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley, 2001.

Databázové systémy  

Úvod  (História databázových technológií, História SQL, Princípy databázových systémov a SQL). Práca s jednou tabuľkou  (Vytvorenie a naplnenie tabuľky. Výpisy všetkých záznamov a záznamov spĺňajúcich nejakú podmienku. Agregačné funkcie. Vnorené dopyty.  Manipulácia s dátami tabuľky. Primárny kľúč a ďalšie integritné obmedzenia). Práca s viacerými tabuľkami (Spojenie dvoch tabuliek. Cudzí kľúč. Modifikácia štruktúry tabuľky. Návrh väčšej databázovej štruktúry. Množinové operácie. Ako postupovať pri konštrukcii dopytu?), Ďalšie črty SQL (Tranzitívny uzáver a rekurzia. Pohľady. Triggery. Indexy. Systémové tabuľky. Základy administrácie databázy. Spolupráca SQL a iných jazykov). Teoretické základy databáz (Formalizácia tabuľky. Databázová logika. Relačná algebra. Funkčné závislosti a normálne formy).
Literatúra:  
J. Ullman, Principles of database and knowledge – base systems, Comp. Sci. Press., 1988.

Výpočtová zložitosť

Pojem nedeterministického algoritmu pracujúceho v polynomiálnom čase, NP-úplnosť. Deterministická simulácia nedeterministických Turingových strojov. Problém splniteľnosti boolovskej formuly. Ďalšie NP-úplné problémy (splniteľnosť boolovskej formuly v konjunktívnom normálnom tvare, 3-splniteľnosť, 3-zafarbiteľnosť grafu, 3-zafarbiteľnosť planárneho grafu, plnenie ruksaku, vyvažovanie …) Pamäťovo ohraničené algoritmy, triedy LOG-space a P-space. Deterministická simulácia (Savitchova veta). Uzavretosť na komplement (Immerman-Szelepcsényiho veta).  
Literatúra:   J.E. Hopcroft, R.Motwani, J.D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley, 2001. 
     
Algoritmy a štruktúry údajov 

Algoritmický problém a jeho riešenie. Správnosť algoritmu a testovanie algoritmov. Vlastnosti programovacích jazykov vyššieho typu. Zložitosť algoritmov. Rekurzia, metóda s návratom (backtracking). Algoritmický problém triedenia, algoritmy a zložitosť. Dôležité údajové štruktúry – zásobník, rad, graf. Algoritmy na grafoch.
Literatúra: 1. N. Wirth, Algorithms+Data Structures=Programs, Prentice-Hall, 1976, ex. slovenský preklad v roku 1987.    
2. P. Toepfer,  Algoritmy a  programovací techniky,  Prometheus, Praha, 1995.

Logika 

Výrokový a predikátový počet, korektnosť a úplnosť, normálne formy, vzťah k relačným databázam, kompaktnosť.
Literatúra:
M.Ben-Ari, Mathematical logic for Computer Science 2ed. Springer Verlag London 2001

Teória algoritmov a vypočítateľnosti

Turingov stroj ako formalizácia pojmu algoritmus. Čiastočne rekurzívne funkcie. Kleeneho veta o normálnom tvare. Vzťah funkcií vypočítateľných na Turingovom stroji a čiastočne rekurzívnych funkcií. Problém zastavenia sa Turingovho stroja. Vlastnosti rekurzívne očíslovateľných množín. Univerzálny systém programov. Veta o preklade, Riceova veta. Dynamická miera zložitosti, príklady. Veta o medzere, vzťah hodnoty funkcie a dynamickej miery zložitosti.
Literatúra:                                                                                                        
1. L. Bukovský, Teória algoritmov, ES UPJŠ, Košice 2004.
2. S. Bridges S, Computability: A mathematical Sketchbook, Springer 1994.

Voliteľné predmety

Počítačové systémy a siete

Princípy činnosti procesora, strojové inštrukcie a ich vykonávanie. Komunikácia procesora s okolím. Radiče zariadení a funkcie ovládačov. Štruktúra a funkcie operačného systému. Vytváranie obrazu úlohy a jej vykonanie. Proces, správa procesov, komunikácia, klasické synchronizačné problémy, prideľovanie procesora. Správa pamäte, segmentácia, stránkovanie, virtuálna pamäť. Súborové systémy, adresáre, bezpečnosť a ochrana prístupovými právami. Riadenie vstupno-výstupných zariadení, prideľovanie zdrojov, uviaznutie. Terminálové siete, súborové a hostiteľské servery, mapovanie a presmerovanie. Sieťové a distribuované operačné systémy, middleware. Vrstvový ISO OSI referenčný model. Charakteristiky prenosových kanálov, teoretické ohraničenia prenosu signálu, prenosové techniky. Prístupové metódy CSMA/CD, Token Ring, vysokorýchlostné siete. Prepájanie sietí, opakovače, mosty, smerovače. Sieťová vrstva v sieťach TCP/IP, adresová štruktúra, ARP, ES-IS komunikácia. Protokol IP, ICMP riadenie, spojované a bezspojové transportné protokoly TCP a UDP. Aplikačné protokoly Telnet, FTP, SMTP, SNMP, systém doménových mien DNS, tvorba sieťových a distribuovaných aplikácií.
Literatúra:
1. A. Silberschatz, G. Gagne, P. Baer, Operating System Concepts, Wiley, 2002.
2. A.S. Tanenbaum, Computer Networks, Prentice Hall, 2002.

Paralelné a distribuované systémy

Paralelné architektúry, paralelný výpočtový model. Stratégie rozloženia záťaže, zreťazené výpočty, synchronizácia, detekcia ukončenia. Programovanie so zdieľanou pamäťou, vlákna. Škálovateľnosť paralelných programov, základné programovacie  techniky. Distribuovaný výpočtový model, komunikačné protokoly, charakteristika distribuovaných systémov. Medzipočítačová komunikácia, distribuované synchronizačné algoritmy, transakcie, detekcia ukončenia a uviaznutia. Procesy v distribuovanom prostredí, vlákna, migrácia, vyvažovanie záťaže, systémové chyby. Distribované súborové systémy, replikácia, správa mien. Problémy konzistencie pri distribuovanom zdieľaní pamäte. Objektovo orientované nadstavby a aplikačné prostredia. Ochrana a bezpečnosť distribuovanej komunikácie.
Literatúra: 
A.S. Tanenbaum, M. van Steen, Distributed Systems – Principles and Paradigms, Prentice Hall, 2002.
                                                                                
Deduktivne znalostne systemy 

Model logického programovania a Datalog-u – vypočítaná a správna odpoveď, korektnosť a úplnosť, fixpoint, rozšírenia pre viachodnotové logiky, vzťah k SQL, rôzne stratégie hľadania najlepšej odpovede.
Literatúra: J. Ullman, Principles of database and knowledge based systems. Comp. Sci. Press 1988.

Získavanie informácií a induktívne logické programovanie 

Základné modely (formulácie úloh) a algoritmy induktívneho logického programovania, rozšírenie pre viachodnotové logiky a monotónnu klasifikáciu, porovnanie s asociačnými pravidlami, apriori algoritmom, klasifikačnými a regresnými stromami.
Literatúra:
J. B. Paris, The uncertain Reasoners Companion. Cambridge University Press, 1994.

Informačné systémy

Systém, životný cyklus IS, životný cyklus vývoja IS. Vizuálne modelovanie, metodológie, CASE nástroje. UML. Riadenie projektu, dokumentácia projektu a údržba dokumentácie.
Literatúra:  
Rumbaugh J., Blaha M., Premerlani W., Eddy F., Lorensen W., Object-Oriented Modeling and Design, Prentice Hall 1991.
                                                    
Kryptografia a bezpečnosť informačných systémov 

Kryptografické modely, konvenčná symetrická kryptografia, metódy a možnosti kryptoanalýzy. Asymetrické kryptografické systémy, autentifikácia, hašovacie funkcie a systémy elektronického podpisu. Generovanie a distribúcia kľúčov, autentifikačné protokoly a ich zraniteľnosť. Certifikácia, bezpečné elektronické platobné systémy. Mechanizmy zabezpečenia IS, systémové a sieťové bezpe-čnostné hrozby. Bezpečnostná politika, analýza rizík, kritériá hodnotenia bezpečnosti informačných systémov. Bezpečnostné hrozby v jednotlivých vrstvách siete Internet, filtre, bezpečnostné brány a zástupné servery. Riešenie bezpečnosti v sieti Internet, protokoly SSL, IPSec.
Literatúra: 
D. R. Stinson, Cryptography. Theory and Practie, CRC Press, 2002.  
   
Počítačová grafika 

Technické prostriedky počítačovej grafiky, farebné modely, metódy kódovania obrazu. Rýchle prírastkové algoritmy pre kresbu úsečiek, kružníc, polynómov. Vyplňovanie oblastí, orezávanie. Modelovanie kriviek, Fergusonova interpolácia, spline krivky, Bézierove a B-spline krivky, modelovanie plôch. Homogénne súradnice, transformácie v rovine a priestore, stredové a rovnobežné premietanie. Určovanie viditeľnosti, osvetľovacie modely, tieňovanie. Realistické zobrazovanie, textúry, sledovanie lúča, vyžarovacia metóda. Reprezentácie údajov, popis scény, zobrazovací reťazec, postupy počítačovej animácie, virtuálna realita.
Literatúra:  
J. Žára, B. Beneš, P. Felkel, Moderní počítačová grafika, Computer Press, 1998.    
                                       
Neurónové siete

Modely dopredných a rekurentných neurónových sietí, back-propagation algoritmus pre adaptáciu sietí, schopnosť neurónových sietí byť univerzálnym aproximátorom. Hopfieldova neurónová sieť a riešenie optimalizáčnych úloh. Kohonenove neurónové siete. Neurónové siete vo vzťahu k iným výpočtovým modelom. Teoretické problémy v oblasti neurónovývh sietí.
Literatúra: J. Šíma, R. Neruda, Teoretické otázky neurónových sítí. Matfyzpress,MFF UK, Praha, 1996.

Teória výpočtového učenia

Učiace algoritmy, koncepcie, hypotézy. Booleovské formuly a ich reprezentácia. Pravdepodobnostné učenie, konzistentné algoritmy a učenie, efektívne učenie, redukovatelnosť v PAC učení, učenie konečných automatov pomocou experimentov. Učenie v neurónových sieťach.
Literatúra:
M. Anthony, N. Biggs, Computational Learning Theory, Cambridge University Press, 1991, 1999.

Teória vyučovania informatiky

Cieľ, obsah a didaktické prostriedky vyučovania školskej informatiky. Pojmotvorný proces v školskej informatike. Úvod do metodológie pedagogického výskumu v školskej informatike. Stanovovanie učebných cieľov. Maturitný štandard z informatiky. Postavenie úloh v školskej informatike, didaktické funkcie a formulácie úloh, tvorba systémov úloh. Hodnotenie žiackych výkonov, didaktické testy. Tvorba didaktických projektov. Výučba štruktúrovaného a objektového programovania. Aritmetika počítača. Matematické modelovanie a simulácie. Výučba tematických oblastí: Informácie okolo nás, Počítačové systémy, Informačná spoločnosť, Oblasti využitia informatiky (kancelársky balík, Internet, multimédiá).
Literatúra:
Kalaš, I. a kol., Informatika pre stredné školy, SPN, Bratislava, 2001.


Študuj na UPJŠ