UNIVERZITA PAVLA JOZEFA ŠAFÁRIKA V KOŠICIACH - Prírodovedecká fakulta

українська
AIS2

Informatika - podmienky prijatia

Didaktika informatiky:

Cieľ, obsah, 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á).

Databázové systémy:

Úvod – história, základné princípy. Základy SQL – práca s jednou tabuľkou, agregačné funkcie, vnorené dopyty, modifikácia dát, integritné obmedzenia, modifikácia štruktúry tabuľky.

Kombinatorické algoritmy:

Úvod do orientovaných i neorientovaných grafov. Úvod do algoritmov, algoritmická zložitosť. Triediace algoritmy. Vyhľadávacie algoritmy. Kladné algoritmy. NP-úplnosť. Stromy a kostry - koreňové stromy. Vyhľadanie všetkých kostier grafu. Úloha o minimálnej kostre. Vzdialenosť v grafoch. Úloha o najkratšej ceste. Úloha o najspoľahlivejšej ceste. Úloha o najširšej ceste. Úvod do sieťovej analýzy. Rozmiestňovacie úlohy. Úlohy o maximálnych tokoch. Úloha o najlacnejších tokoch. Párovacie a príraďovacie problémy. Úloha čínskeho poštára. Problém obchodného cestujúceho. Dopravné úlohy.

Programovanie, algoritmy a zložitosť:

Algoritmický problém a jeho riešenie. Príklady konkrétnych algoritmov, zápis algoritmu v dohodnutom formalizme. Správnosť algoritmu a testovanie algoritmov. Vlastnosti programovacích jazykov vyššieho typu. Základné údajové a príkazové štruktúry programovacieho jazyka PASCAL. Procedúry, funkcie, knižnice procedúr a funkcií. Dynamické údajové štruktúry, typ smerník. 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.

Úvod do kryptológie:

Kryptografické modely, konvenčná symetrická kryptografia, metódy a možnosti kryptoanalýzy. Asymetrické kryptografické systémy, elementy teórie čísel, autentizácia, hašovacie funkcie a systémy elektronického podpisu. Generovanie a distribúcia kľúčov, autentizačné protokoly a ich zraniteľnosť. Certifikácia, bezpečné elektronické platobné systémy.

Výpočtová logika:

Úvodná motivácia o potrebe logiky v informatike. Alternatívne metamatematické základy: teória množín, slová a čísla a reprezentácia dátových štruktúr (relácie - typované s atribútmi, funkcie, ordinálne čísla, stromy). Základné štruktúry a pojmy výrokového a predikátového počtu: syntax (syntaktické stromy, vytvárajúce postupnosti, dôkazy) a sémantika (štruktúry a pravdivosť). Korektnosť výrokového a predikátového počtu (korektnosť axiómy o substituovateľnosti a zavedení kvantifikátora). Algoritmické aspekty syntaxe. Súvislosť sémantiky s databázami. Vety o dedukcii, úplnosť a kompaktnosť. Sémantické tableaux, deduktívne systémy a algoritmy.

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

Výpočtové učenie:

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.