======================================

Vzorové otázky:

1. Grafové štruktúry; Adresácia

a) V akých situáciách ste sa streli s využitím stromových štruktúr (resp. s uložením údajov v strome). Ako sa v týchto situáciách využívajú stromy? Existuje nejaká súvislosť medzi aritmetickými výrazmi a stromovými štruktúrami? Ako by ste vyjadrili gramatiku aritmetického výrazu

b) Počítačovú sieť je možné reprezentovať pomocou grafu. Aké grafové algoritmy sa tu využívajú a aké ciele sledujú? Je potrebné opísať aspoň jeden z nich podrobnejšie. Ako prebieha adresácia v protokole IPv4 a IPv6?

2. Formálne jazyky; Smerovače

a) Súčasťou programovacích jazykov sú aj aritmetické výrazy. Vytvorte gramatiku, ktorá bude generovať všetky ozátvorkované aritmetické výrazy pozostávajúce z kladných čísel a operácií +, - a *. Príklady: (2+4*(8-1)), ((45*2)+(3-101)). Ako by ste ukázali, že jazyk takýchto aritmetických výrazov nemôže byť regulárny?

b) Aká je úloha smerovača v sieti Internet? Aký je obsah smerovacej tabuľky? Je možné vytvárať smerovaciu tabuľku dynamicky? Uveďte algoritmus nasmerovania IP paketu.

3. Turingov stroj; Internet - aplikačná vrstva

a) Pomocou Turingovho stroja je možné definovať vypočítateľnosť funkcií a tiež ilustrovať neriešiteľnosť niektorých problémov. Definujte Turingov stroj (TS) a sformulujte problém, ktorý nie je na TS riešiteľný. Popíšte ideu dôkazu.

b) Popíšte služby aplikačnej vrstvy komunikačného modelu v sieti Internet. Aká je organizácia doménových serverov? Aký je význam a využitie doménových mien? Popíšte protokol elektronickej pošty a jeho použitie.

======================================

FORMÁLNE ZÁKLADY INFORMATIKY - ATOMICKÉ VEDOMOSTI

Je porebné vedieť definície, vety, idey dôkazov a riešiť jednoduché obmeny problémov v rozsahu jednotlivých nasledujúcich oblastí.

Logika:

Význam negácie, konjunkcie, disjunkcie, implikácie, ekvivalencie, existenčného kvantifikátora, všeobecného kvantifikátora. Prepis matematickej vety v prirodzenom (slovenskom) jazyku do reči symbolov, rozoznávanie voľných a viazaných premenných, tabuľka pravdivostných hodnôt, definícia ekvivalentnosti dvoch výrokov, princíp dôkazu sporom, princíp nepriameho dôkazu, princíp dôkazu matematickou indukciou, formálny zápis dôkazu matematickou indukciou, princíp definície matematickou indukciou, prepis výroku do stromového tvaru, prepis výroku do prefixového tvaru, prepis výroku do postfixového tvaru.

Množiny:

Definícia inklúzie dvoch množín, princíp dôkazu inklúzie dvoch množín, definícia rovnosti dvoch množín, princíp dôkazu rovnosti dvoch množín, definícia prieniku, zjednotenia a rozdielu dvoch množín, definícia karteziánskeho súčinu dvoch množín, definícia prieniku systému množín, definícia zjednotenia systému množín, definícia prázdnej množiny, definícia potenčnej množiny, definícia charakteristickej funkcie množiny, definícia rovnakej mohutnosti dvoch množín, definícia konečnej množiny, definícia spočítateľnej množiny, vzťah mohutnosti potenčnej množiny a mohutnosti jej základnej množiny, porovnanie mohutností množiny prirodzených, celých, racionálnych a reálnych čísel.

Relácie:

Definície nasledujúcich pojmov: relácia, reflexívna relácia, symetrická relácia, tranzitívna relácia, antireflexívna relácia, antisymetrická relácia, inverzná relácia k relácii, skladanie relácií, tranzitívny uzáver relácie.

Funkcie:

Definícia funkcie, zápis funkcie z množiny do množiny, definícia definičného oboru, definícia oboru hodnôt, definícia prostej funkcie (injekcie), definícia funkcie na (surjekcie), definícia bijekcie, definícia inverznej funkcie k funkcii, definícia skladania funkcií, definícia obrazu množiny vo funkcii, definícia zúženia funkcie.

Matice:

Definícia matice, definícia súčtu matíc, správne používanie značiek pre sumu a produkt, definícia súčinu matíc, definícia jednotkovej, transponovanej a inverznej matice k štvorcovej matici, definícia determinantu matice, riešenie sústavy lineárnych rovníc.

ĎALŠIE PREDMETY

Algoritmy a postupy , ktoré sa vyskytujú v nasledujúcich predmetoch je potrebné vedieť vyhodnotiť z hľadiska pamäťovej a časovej zložitosti. Je tiež potrebné mať premyslené údajové štruktúry, ktoré sú pri ich implementácii použiteľné.

Matematická analýza:

Číselné množiny (ohraničenosť, maximum, minimum, supremum, infinum). Absolútna hodnota, mocnina, logaritmus. Postupnosť čísel. Funkcie jednej reálnej premennej (základné pojmy a vlastnosti). Limita a spojitosť funkcie. Elementárne funkcie. Diferenciálny počet reálnej funkcie jednej reálnej premennej. Taylorov polynóm, Taylorova veta.

Integrálny počet reálnej funkcie jednej reálnej premennej: a) Neurčitý integrál - vlastnosti, metódy výpočtu, b) Určitý integrál - vlastnosti, metódy výpočtu, veta o strednej hodnote, c) Nevlastný integrál - vlastnosti, metódy výpočtu.

Automaty a formálne jazyky:

Chomského hierachia jazykov a gramatík. Konečnostavový automat, regulárne zobrazenia, konštrukcia redukovaného automatu. Konečnostavové akceptory, nedeterministické akceptory. Regulárne výrazy. Uzáverové vlastnosti triedy regulárnych jazykov. Bezkontextové gramatiky, Chomského a Greibachovej normálny tvar. Zásobníkové automaty. Pumping lema. Uzáverové vlastnosti bezkontextových jazykov. Deterministické zásobníkové automaty. Uzáverové vlastnosti deterministických bezkontextových jazykov.

Teória vypočítateľnosti:

Intuitívny pojem algoritmu, potreba exaktnej definície. Turingov stroj ako formalizácia algoritmu. Čiastočne rekurzívne funkcie. Aritmetizácia (Gödelovské číslovanie). Kleeneho veta o normálnom tvare. Ekvivalentnosť rozličných formalizácii pojmu algoritmu. Algoritmická nerozhodnuteľnosť problému zastavenia Turingovho stroja.

Podrobnej3ie:

Turingove stroje. Základné princípy práce Turingovho stroja. Formalizácia základných pojmov. Posúvanie stavov. Skladanie strojov. Výpočty na zložených úplných strojoch. Výpočty na zložených poloúplných strojoch. Úpravy konfigurácie. Elementárne úplné a poloúplné Turingove stroje. Zloženiny elementárnych Turingových strojov.

Rekurzívne funkcie. Induktívna štruktúra primitívne rekurzívnych funkcií. Príklady primitívne rekurzívnych funkcií. Primitívne rekurzívne predikáty. Funkcie a predikáty z teórie čísel. Goedelovská aritmetizácia. Goedelovská aritmetizácia turingovskej vypočítateľnosti. Induktívna štruktúra rekurzívnych funkcií. Vzťah rekurzívnych a turingovsky vypočítateľných funkcií. Problém zastavenia Turingovho stroja

Programovanie, algoritmy a zložitosť:

Trieda a objekt ako prostriedok na zgrupovanie viacerých premenných, grafická trieda trojuholník, štvorec, (metódy ukaz, skry, presun, zmenFarbu, ....), konštruktor, preťažovanie metód, kompozícia objektov. Interface ako intuitívny prostriedok abstrakcie, interface ako parameter a referencia, pole objektov implementujúcich daný interface.

Dedenie, prekrývanie metód polymorfizmus – možno využiť prekrývanie a doplňovanie metód triedy kresliaceho pera, (dedenie ako prostriedok prispôsobenia a rozšírenia existujúcich objektov), pole polymorfných objektov, abstraktná trieda „grafický objekt“. Rekurzia (rekurzia vo fraktáloch, prepis známych funkcií do rekurzívnej formy).

Triedenie (O a Omega-notácie, MinSort - triedenie čísel , MinSort - triedenie objektov, QuickSort, strom v poli, HeapSort, MergeSort). Údajové štruktúry (zásobník a rad, a ich využitie pri riešení niektorých úloh). Stromy (prehľadávanie stromov, binárne vyhľadávacie stromy).

Backtrack (generovanie variácií a problém delenia lupu, backtrack všeobecne a v úlohách, orezávanie backtracku). Rozdeľuj a panuj, dynamické programovanie, princíp a príklady.

Prehľadávanie textov (KMP algoritmus). Grafy a základné grafové algoritmy (grafy a ich reprezentácie, testovanie súvislosti grafu, prehľadávanie do hĺbky a prehľadávanie do šírky, kostra grafu, najkratšie cesty v grafe, Dijkstrov algoritmus, FW algoritmus). Greedy algoritmy (Najlacnejšia kostra, TopSort).

Databázové systémy:

Princípy databázových systémov a SQL. SQL - práca s dátami, integritné obmedzenia, navrhovanie databázového modelu. Množinové operácie. Tranzitívny uzáver a rekurzia. SQL - Pohľady. Indexy. Triggery. Systémové tabuľky. Formálne základy databáz - Relačná algebra. Databázové operácie v relačnej algebre. Vzťah relačnej algebry a SQL.

Operačné systémy:

Štruktúra a funkcie operačného systému. Vytváranie obrazu úlohy a jej vykonanie. Charakteristiky druhov OS. Proces, správa procesov, komunikácia, klasické problémy, prideľovanie procesora. Správa pamäte, segmentácia, stránkovanie, virtualizácia. Súborové systémy FAT, NTFS a ext4 , adresáre, bezpečnosť a ochrana prístupovými právami. Riadenie vstupno-výstupných zariadení, prideľovanie zdrojov, uviaznutie. Architektúra operačných systémov MS DOS, UNIX, Windows. Prepájanie počítačov, súborové a hostiteľské servery, mapovanie a presmerovanie. Virtualizácia.

Počítačové siete: Úvod do počítačových sietí, spôsoby pripojenia k internetu, straty a zdržania paketov, referenčný model ISO/OSI, rodina protokolov TCP/IP. Jednotlivé vrstvy modelu: aplikačná (aplikačné protokoly, doménové mená a DNS), transportná (UDP, potvrdzovaný prenos dát, TCP, kontrola toku dát), sieťová (preklad adries NAT, protokol ICMP, IPv4, IPv6, princípy smerovacích algoritmov), spojová (odhaľovanie chýb pri prenose, viacnásobný prístup k zdieľanému spoju CSMA/CD a CSMA/CA, MAC adresy, opakovače, prepínače, virtuálne siete VLAN,..) a fyzická (digitálny a modulovaný prenos).