Obsah a organizácia záverečného konania pre I. stupeň štúdia študijného programu v odbore 9.2.1. Informatika na FMFI UK1


Doc. RNDr. Daniel Olejár, PhD., garant študijného programu



Úvod


Bakalárske štúdium informatiky je podľa študijného programu ukončené záverečným konaním. Tento dokument je určený študentom bakalárskeho štúdia informatiky, ktorí budú končiť v školskom roku 2007/8 štúdium a obsahuje informácie o obsahu a organizácii záverečného konania. Dokument vychádza zo študijných poriadkov UK, FMFI UK, akreditovaného študijného programu I. stupňa v odbore 9.2.1. Informatika na FMFI UK a obsahu štátnej skúšky, prerokovanom na zasadaní Sekcie informatiky FMFI UK.

Študijný program bakalárskeho štúdia informatiky definuje ciele a štruktúru záverečného konania


Úlohou štátnej skúšky bakalárskeho štúdia je overiť, či študent získal vedomosti a zručnosti dané profilom absolventa bakalárskeho štúdia informatiky, či je schopný syntetizovať poznatky získané štúdiom čiastkových predmetov a tvorivo ich uplatniť.


Štátna skúška bakalárskeho štúdia informatiky pozostáva


Obsah štátnej skúšky špecifikuje Študijný program bakalárskeho štúdia informatiky takto


Štátnicové predmety pokrývajú ťažiskové predmety študijného programu (povinné a povinne voliteľné predmety). Návrh štátnicových predmetov a ich obsahu predkladá garant štúdia sekcii informatiky a vedeckej rade fakulty a schvaľuje ich dekan fakulty.


Garant štúdia vypracoval návrh štátnicových predmetov a ich obsahu. Tento návrh bol prerokovaný v sekcii informatiky

Obsah štátnej skúšky


Štátna skúška bakalárskeho štúdia pokrýva potreby dvoch rozličných skupín študentov bakalárskeho štúdia informatiky. Pre tých študentov, ktorí budú pokračovať v magisterskom štúdiu informatiky, musí overiť ich vedomosti a schopnosť syntetizovať základné poznatky odboru pred ďalšou hlbšou špecializáciou.. Pre tých absolventov bakalárskeho štúdia, ktorí nebudú pokračovať v magisterskom štúdiu, má záverečná skúška overiť ich odbornú spôsobilosť (danú profilom absolventa bakalárskeho štúdia informatiky) pred nástupom do reálnej praxe. Na naplnenie oboch požiadaviek bol obsah a rozsah štátnej skúšky stanovený nasledovne.

Predmety štátnej skúšky bakalárskeho štúdia informatiky sú


  1. matematika

  2. informatika



Štátnicový predmet matematika pokrýva problematiku diskrétnej matematiky a logiky, ktoré tvoria základ teoretickej informatiky aj samotnej informatiky. Pozostáva z nasledujúcich okruhov (zodpovedajúcich predmetom povinného základu)



Štátnicový predmet informatika obsahuje teoretickú informatiku a aplikovanú informatiku, pokrytú nasledujúcimi predmetmi bakalárskeho štúdia informatiky:



Sylaby štátnicových predmetov sú uvedené v prílohe I.






Bakalárska práca

Príloha I. Obsah predmetov štátnej skúšky

Algebra

  1. Vektorové priestory, lineárne zobrazenia [priestor, podpriestor, lineárna závislosť, báza a dimenzia. Steinitzova veta, súčty podpriestorov, lineárne zobrazenia, kompozícia lineárnych zobrazení, inverzné lineárne zobrazenia, matica lineárneho zobrazenia, jadro a obraz lineárneho zobrazenia.

  2. Matice a riešenia lineárnych rovníc nad poľom F [matice, operácie s maticami (násobenie, sčítanie), elementárne riadkové operácie, trojuholníkový a redukovaný trojuholníkový tvar matice, systémy lineárnych rovníc nad poľom F, množina riešení homogénnych a nehomogénnych systémov lineárnych rovníc, existencia a tvary riešení]

  3. Determinanty. [Determinant lineárneho zobrazenia a matice. Vlastnosti determinantov. Výpočty determinantov a ich použitie pri riešení lineárnych rovníc a hľadaní inverznej matice]

  4. Grupy [grupy, podgrupy, izomorfizmus a homomorfizmus grúp, cyklické grupy (s klasifikáciou) a ich podgrupy, grupy permutácií, rozklad grupy podľa podgrupy, Lagrangeova veta, homomorfizmus a izomorfizmus grúp, normálna podgrupa, faktorizácia grupy podľa podgrupy]

  5. Okruhy [základné vlastnosti operácií v okruhoch, podokruh, ideál (hlavný, maximálny, prvoideál), faktorizácia okruhu podľa ideálu, vzťah medzi výsledkom faktorizácie a vlastnosťami ideálu, podľa ktorého sa faktorizuje, obor integrity a veta o podielovom poli]

  6. Okruhy hlavných ideálov [existencia jednotky v okruhu, najväčší spoločný deliteľ, vlastnosti deliteľnosti, ireducibilné prvky, veta o jednoznačnom rozklade]

  7. Okruhy polynómov [pojem algebraického a transcendentného prvku pre daný okruh, okruh polynómov R[x], okruh polynómov F[x] nad poľom F ako okruh hlavných ideálov, veta o jednoznačnom rozklade polynómov nad daným poľom, substitučný homomorfizmus (veta o substitúcii), korene, viacnásobné korene, Hornerova schéma, derivácia, Taylorov rozvoj]

  8. Rozšírenia polí [jednoduché, viacnásobné a konečné rozšírenie poľa, vzťah medzi nimi, minimálny polynóm daného algebraického prvku, transcendentné rozšírenie]

  9. Konečné polia [harakteristika poľa, rozkladové pole daného polynómu nad daným poľom, veta o existencii a izomorfizmus rozkladových polí, konečné polia - veta o existencii a izomorfizme konečných polí.]

Úvod do diskrétnych štruktúr


  1. Základy matematickej logiky [logické operácie, formuly, výrokové funkcie, kvantifikácia výrokov, autógia, kontradikcia]

  2. Matematický dôkaz [logický dôsledok, základné typy matematickych dôkazov]

  3. Intuitivný pojem množiny [základné pojmy a označenia, množinové operácie. Množinové identity]

  4. Karteziánsky súčin množín a jeho vlastnosti.

  5. Relácie [skladanie relácií, inverzná relácia, relácie na množinách. Relácia ekvivalencie, rozklad množiny. Tranzitívny uzáver relácie, reflexívno-tranzítivny uzáver. Definicia, vlastnosti.]

  6. Čiastočné usporiadanie a usporiadanie množiny (ostré a neostré). [Definícia, vlastnosti usporiadania, minimálny, maximálny, prvý a posledný prvok množiny]

  7. Zobrazenia.

  8. Mohutnosť množiny. [Základné vlastnosti mohutnosti a nerovnosti. Počítanie s mohutnosťami, súčet, súčin a mocnina.]

  9. Cantor-Bernsteinova veta a jej dôsledky.

  10. Konečné a nekonečné množiny.

  11. Spočítateľné a nespočítateľné množiny.

  12. Aritmetika celých nezáporných čísel.


Úvod do kombinatoriky a teórie grafov


  1. Prirodzené čísla a matematická indukcia

  2. Dirichletov princíp

  3. Pravidlo súčtu a pravidlo súčinu

  4. Variácie a enumerácia zobrazení

  5. Kombinácie bez opakovania a enumerácia podmnožín

  6. Binomická veta s prirodzeným aj reálnym exponentom

  7. Rovnosti a nerovnosti s kombinačnými číslami

  8. Kombinácie s opakovaním

  9. Polynomická veta

  10. Princíp zapojenia a vypojenia

  11. Odhady čísla n!

  12. Hierarchia rastu funkcií

  13. Stromy, lesy a kostry

  14. Súvislé grafy, komponenty a meranie vzdialeností v grafe

  15. Eulerovské grafy

  16. Bipartitné grafy

  17. Meranie vrcholovej a hranovej súvislosti grafu

  18. Hamiltonovské grafy


Úvod do matematickej logiky


  1. Výstavba logickej teórie [Jazyk logiky, formálne systémy logiky]

  2. Výroková logika [Syntax a sémantika výrokovej logiky. Formálny systém výrokovej logiky]

  3. Základné vety výrokovej logiky [Veta o kompaktnosti a jej dôsledok, veta o dedukcii. Základné teorémy výrokovej logiky]

  4. Postova veta [slabá forma, silná forma]

  5. Bezospornosť formálneho systému.

  6. Pravidlá odvodenia vo výrokovej logike [Veta o nahradení podformúl ekvivalentnými formulami. De Morganove pravidlá. Veta o dôkaze rozborom prípadov. Veta o substitúcii prvotných formúl.]

  7. Disjunktívna a konjunktívna normálna forma formuly.

  8. Predikátová logika. [Jazyk predikátovej logiky. Sémantika a syntax predikátovej logiky. Substitúcia termov za premenné.Voľné a viazané premenné.]

  9. Axiómy a pravidlá odvodenia predikátovej logiky. [Pravidlá zavedenia kvantifikátorov.Veta o uzávere. Lema o distribúcii kvantifikatorov.Veta o ekvivalencii. Veta o variantoch. Veta o dedukcii. Dôsledky vety o dedukcii. Veta o konštantach. Zovšeobecnená veta o dedukcii a jej dôsledok.]

  10. Prenexný a Skolemov tvar formuly.

  11. Rovnosť [Axiómy rovnosti. Základné vlastnosti rovnosti. Príklady teórií s rovnosťou.]


Formálne jazyky a automaty

  1. Regulárne jazyky. [Deterministické a nedeterministické konečné automaty, regulárne gramatiky, regulárne výrazy, ekvivalencia popisov regulárnych jazykov, pumpovacia lema, uzáverové vlastnosti.]

  2. Bezkontextové jazyky. [Bezkontextové gramatiky, normálne tvary, nedeterministické zásobníkové automaty, ekvivalencia zásobníkových automatov a bezkontextových gramatík, uzáverové vlastnosti.]

  3. Rekurzívne vyčísliteľné a rekurzívne jazyky. [Turingove stroje, frázové gramatiky, ich ekvivalencia, uzáverové vlastnosti, univerzálny Turingov stroj, Turingova hypotéza.]

  4. Nerozhodnuteľné problémy. [Diagonalizácia, problém zastavenia, metódy dokazovania nerozhodnuteľnosti.]

  5. Miery zložitosti pre Turingove stroje [triedy zložitosti, kompresia pásky, zrýchľovanie výpočtov, vplyv redukcie počtu pások na zložitosť]

Algoritmy a dátové štruktúry


  1. Metódy vytvárania algoritmov [Divide et impera, Dynamické programovanie; Gradientná metóda]

  2. Riešenie rekurencií pre odhady zložitosti algoritmov

  3. Algoritmy triedenia a popis ich zložitosti [Insertsort, Heapsort, Quicksort]

  4. Algoritmus Randomized Quicksort [popis a odhad jeho zložitosti]

  5. Triedenia v lineárnom čase

  6. Dolný odhad časovej zložitosti algoritmu triedenia porovnávaním

  7. Elementárne dátové štruktúry

  8. Stromy [reprezentácie stromov, binárne prehľadávacie stromy a operácie na nich]

  9. Porovnanie haldy a binárnych prehľadávacích stromov

  10. Vyvážené stromy a operácie na nich [RB-stromy, B-stromy]

  11. Hašovanie [zreťazením, otvorenou adresáciou]


Tvorba efektívnych algoritmov


  1. Problém slovníka (2-3 stromy).

  2. Union/Find-Set problém.

  3. Algoritmy pre hľadanie najkratších ciest v grafe.

  4. Algoritmus pre hľadanie najlacnejšej kostry grafu. Strassenov algoritmus na násobenie matíc.

  5. Princípy tvorby efektívnych algoritmov (vrátane konkrétnych aplikácií):

  6. Vyváženosť a voľba vhodnej dátovej štruktúry.

  7. Triedy P a NP; polynomiálna redukovateľnosť. Cook-Levinova Veta a ďalšie NP-úplné problémy.

Operačné systémy


  1. Koncepcia OS (procesy, súbory, funkcie a služby OS, systémové volania, interpreter príkazov) a štruktúra OS (monolitický kernel, mikrokernel, …).

  2. Procesy (hierarchia procesov, vytváranie, swapovanie procesov, životný cyklus procesu) a komunikácia medzi procesmi (synchronizácia, adresovanie, formát správ, zaraďovanie správ, riešenie straty správ, pipe – rúra).

  3. Synchronizácia procesov (časová závislosť procesov /race conditions/, vzájomné vylúčenie /mutual exclusion/ a spôsoby jeho dosiahnutia – hardvérové aj softvérové) a klasické problémy synchronizácie procesov (producent/konzument, problém obedujúcich filozofov, problém čitateľov a zapisovateľov).

  4. Uviaznutie – podmienky pre vznik uviaznutia, metódy riešenia uviaznutia (ignorovanie, detekcia a vyvedenie, prevencia, vyhýbanie sa). Rozdiel medzi uviaznutím a vyhladovaním.

  5. Správa procesov a procesora – plánovače a ich funkcie. Algoritmy plánovania procesov (FCFS, SJF, HRN, SRT, RR, ...).

  6. Správa pamäte – jej funkcie, typy správy pamäte (jeden súvislý úsek, statické súvislé úseky, dynamické súvislé úseky, stránkovanie, segmentovanie).

  7. Správa pamäte –virtuálna pamäť, výpadok stránky, nahradzovacie algoritmy (FIFO, NRU, LRU, NFU), stránkovanie na žiadosť, model s pracovnou množinou, implementačné problémy (zálohovanie inštrukcií, zamykanie stránok v pamäti, zdieľanie stránok).

  8. Správa súborov – funkcie, typy súborov, štruktúra súboru, hierarchické systémy adresárov, správa voľného priestoru na disku (spájaný zoznam voľných blokov, indexové bloky, bitová mapa), správa priestoru prideleného súboru (FAT, i-node), zdieľané súbory.

  9. Správa zariadení – funkcie, klasifikácia V/V zariadení, pojem riadiaca jednotka, DMA, techniky prideľovania V/V, V/V softvér, správa diskových požiadaviek (SSTF, SCAN, C-SCAN, N-step SCAN).


Úvod do databáz

  1. Dátové modely. Entitno-relačný model. [Bachmanove diagramy.] Relačný model.

  2. Architektúra DBMS a modelovanie reality. Trojschémová architektúra (ANSI sparc).

  3. Relačný model. Relačná algebra. Tabuľková a predikátová interpretácia relačnej algebry. Negácia, doménovo nezávislé a bezpečné formuly. Relačný kalkul (doménový). Relačný jazyk SQL. Programovanie v SQL. Iné dotazové jazyky (QBE, Datalog).

  4. Teória navrhovania relačných báz dát. Funkčné závislosti, vyplývanie, Armstrongove axiómy, efektívne odvodenie. Normálne formy 3NF, BCNF. Algoritmy pre úpravu do normálnych foriem.

  5. Transakcie a spracovanie transakcií. Sériovateľnosť, test sériovateľnosti. Zámky a zamykacie protokoly. Journal, commit a rollback. Optimistické a pesimistické riadenie transakcií, časové razítka.

  6. Bezpečnosť v databázových systémoch. Autorizácia, metódy ochrany pred neoprávneným prístupom. Ochrana dát pred poškodením a zničením - backup.

  7. Fyzická organizácia. Dvojúrovňový model pamäti a organizácie dát. Indexové súbory. B a B^*-stromy. Hašované súbory. Dotazy na čiastočnú zhodu. Realizácia relačných operácií. Kompresia dát (statické metódy, Ziv-Lempel).



Počítačové siete

  1. Telekomunikácie - verejné a súkromné možnosti - koncept prenosu informácií v minulosti a dnes - integračné trendy.

  2. Siete - topológia a geografia - základné typy sietí - siete s redundanciou - siete bez redundancie - príklady siete viacerých typov - viacúrovňové LAN.

  3. Informačné toky (information streams) - zdroje, cieľové uzly, prepínací systém - jednosmerné a obojsmerné spojenia - konferencie.

  4. Komunikačné kanály (communication channels) - multiplexovanie - virtuálne okruhy - uzly s jednosmernou premávkou - uzly s dvojsmernou premávkou.

  5. Schéma jednoduchého komunikačného modelu.

  6. Sieťový software - technika štrukturovaného sieťového softwaru - koncepcia vrstiev - protokoly - virtuálna komunikácia - fyzická komunikácia - interface.

  7. Všeobecné závery z oblasti počítačových sietí, ktoré musia byť zakomponované do viacvrstvovej sieťovej architektúry.

  8. Adresovanie - pravidlá pre prenos údajov - správa chýb - postupnosť (následnosť) správ - problém rýchleho odosielateľa a pomalého príjemcu - neschopnosť akceptovať správy ľubovoľnej dĺžky - efektívny prenos malých správ - multiplexovanie a demultiplexovanie - smerovanie.

  9. Rozhrania a služby - entity - entity rovný s rovným - poskytovateľ služby - používateľ služby - vzťah medzi vrstvami a rozhraniami - Service Access Points (SAP's) - Interface Data Unit.

  10. Spojované služby (connection-oriented services) a nespojované služby (connectionless services).

  11. Kvalita služby - spoľahlivá spojovaná služba - nespoľahlivá (t.j. nepotvrdzovaná) nespojovaná služba - potvrdzovaná datagramová služba.

  12. Službové primitíva (service primitives).

  13. Referenčné modely - ciele a nebezpečenstvá - ARPANET, SNA, DNA - Open Systems Architecture - norma ISO 7498.

  14. TCP/IP - referenčný model.

  15. Porovnanie OSI a TCP/IP referenčného modelu.

  16. Kritika OSI modelu a protokolov.

  17. Kritika TCP/IP referenčného modelu.

  18. Teoretické základy pre dátovú komunikáciu - Nyquistovo tvrdenie a Shannonove odhady.

  19. Prenosové média - vodiace média - nevodiace média - magnetické média - krútená dvojlinka - koaxiálny kábel - optické vlákna - siete z optických vlákien - ring, star - porovnanie optických a metalických káblov.

  20. Sieťové komponenty - techniky prepojovania sietí - charakter kabeláže - štruktúrovaná kabeláž.

  21. Dátové prenosy, UART, USRT, synchronizácia.

  22. Bezdrôtový prenos (wireless transmission).

  23. Elektromagnetické spektrum - rádiové vysielanie (prenosy) - mikrovlnné vysielanie (prenosy) - infračervené a milimetrové vlny - svetelné prenosy.

  24. Telefónny systém - modemy - štandardy - konštelačné vzorky - modulačné techniky

  25. Diaľkové vedenia a multiplexovanie –FDMA/TDMA/CDMA

  26. SDH - SONET architektúra - definícia rámcov v SDH.

  27. Prepínanie (switching) - časovanie udalostí pri jednotlivých typoch prepínania.

  28. ISDN - systém pre domáce a firemné využitie, xDSL.

  29. Synchrónny a asynchrónny prenosový režim - ATM - základný ATM - switch - knockout switch - banyan switch.

  30. Linková vrstva - MAC - IEEE štandardy 802 pre LAN - FDDI - Fast Ethernet. - Gigabit Ethernet - 10 Gigabit Ethernet – 802.11 – WPAN/Bluetooth – 802.16

  31. Sieťová vrstva - interná organizácia sieťovej vrstvy - príklad prenosu packetov cez sieť - uzly a smerovacie tabuľky - porovnanie virtuálnych kanálov a datagramov - smerovanie - algoritmy smerovania - riadenie upchatia siete.

  32. Transportná vrstva – TCP, UDP, SSL

  33. Aplikačná vrstva a podporné protokoly

Programovanie


  1. Objektovo orientované programovanie – základné myšlienky (zapuzdrenie, dedičnosť, polymorfizmus), syntax (definícia triedy, modifikátory prístupu, konštruktory, deštruktor, dedenie, vlastnosti (properties), implicitná a explicitná implementácia rozhrania – interface). Garbage Collection.

  2. Hodnotové typy, referenčné typy, boxing, polia (jednorozmerné, pravidelné viacrozmerné, nepravidelné – jagged), vnorené triedy (nested classes) - statické členské triedy, členské triedy, lokálne triedy, anonymné triedy. Garbage Collection.

  3. Delegát (delegate) ako call-back metóda, udalosti (event), výnimky (exception) - vyhodenie výnimky, zachytenie a spracovanie výnimiek, vlastné triedy výnimiek, checked a unchecked výnimky.

  4. Vlákna (threads) – stav vlákna (new, runnable, blocked, waiting, timed_waiting, terminated), životný cyklus vlákna (vytvorenie, spustenie, zastavenie, ...), plánovanie vlákien (fixed-priority scheduling, yield, time-slicing). Synchronizácia vlákien (kritické úseky, wait a notify, explicitné zámky a podmienkové premenné).

  5. Generics (formálne typové parametre, parametrizovaný typ, wildcards, ohraničené wildcards, generic methods).

  6. Návrhové vzory

    1. Composite, Strategy

    2. Decorator, Abstract Factory

    3. Bridge, Command

    4. Iterator, Visitor

1 Toto je pracovná verzia, určená pre základnú informáciu študentov. Chýbajúce informácie o bakalárskej práci a témach bakalárskych prác budú doplnené začiatkom septembra.