SZZ Bc. Informatika

Vše co se týká bakalářských státních závěrečných zkoušek.

SZZ Bc. Informatika

Příspěvekod madvorak » 21. 6. 2017 08:26

Protože jsem nikde nenašel řešení otázek z minulých termínu státnic, tak jsem se pokusil vyřešit některé sám. Dávám tady svůj pokus o vyřešení informatických otázek z https://www.mff.cuni.cz/studium/bcmgr/szz/priklady-jaro-2017.pdf , který bude jistě obsahovat chyby. Bylo by skvělé, kdybyste mi někdo pomohl mé chyby opravit a směřovat tak vytvoření "vzorového" řešení, ze kterého se možná budeme moci učit. Otázky jsou odděleny trojicí prázdných řádků, podotázky jsou odděleny jedním prázdným rádkem.



1. SQL

SELECT * FROM Obchodník WHERE NOT EXISTS (
SELECT Id FROM ObchodniTransakce NATURAL JOIN Komodita WHERE Název = 'přenice' AND Rok = 2016 AND ObchodniTransakce.Kód = Obchodník.Kód)

SELECT Kód FROM ObchodniTransakce WHERE Rok = 2016 GROUP BY Kód HAVING SUM(Cena) > 10000000

read uncommited - hrozí WR, RW a Phantom - no protocol
read commited - hrozí RW a Phantom - S2PL pro zapisovací zámky + 2PL pro čtecí zámky
repeatable read - hrozí pouze Phantom - S2PL pro všechny zámky
serializable - nehrozí WR, RW, ani Phantom - S2PL pro všechny zámky + phantom prevention



2. Kódy

min(přes různá x, y){d(k(x), k(y))}, kde k je kódovací funkce a d je Hammingova vzdálenost
vzdálenost uvedeného kódu je 2
počet chyb, které je možno v přeneseném slově opravit, je největší přirozené číslo menší než polovina vzdálenosti

000, 011, 101, 110
00 01 11 10
ano je lineární

pro délku kódovaného slova n existuje nejvýše 2^n kódů
při požadavku na vzdálenost d vzniká kolem každého kódovaného slova koule o objemu suma_{i = 0,..,d}(n choose i)
Hammingův odhad říká, že počet kódových slov v kódu o vzdálenosti d je nejvýše 2^n děleno touto sumou



3. Morfologie

morfologická analýza - hledání všech lemmata a značek, které můžou popsat daný slovní tvar
morfologické značkování - výběr jednoho správného lemmatu a značky podle kontextu, ve kterém se daný slovní tvar vyskytuje
lemmatizace - generování základního tvaru od uvedeného slova (nohy -> noha)

konkrétní slovní tvar může být odvozen od více lemmat (tři - 3 / třít (imperativ) ; žena - lidská samička / žene (přechodník) ; hnát - spěchat / ruka)

algoritmus využívá seznam kmenů slov a flektivní pravidla ???



4. TCP a NAT

sequence number - určuje, kolikáty paket je posílán
acknowledgment number - určuje, kolik paketů již má potvrzeno přijetí
(ostatní netuším)
source port - port na straně klienta
destination port - port na straně "serveru"
např. při inicializaci komunikace s HTTP serverem si klient vybere nějaké pravděpodobné náhodné číslo portu (třeba 32875), které je source port a komunikuje standardně se serverem na portu 80 (destination port) -> odpověď na tento požadavek ze strany serveru bude mít source port 80 a destination port ono náhodné klientovo číslo (třeba 32875)


5. NP-úplnost

rozhodovací problém je nějaké zobrazení {0,1}^n -> {0,1}
instance problému je konkrétní příklad vstupu z {0,1}^n
NP je třída všech rozhodovacích problémů, které lze řešit v polynomiálním čase s nápovědou, tedy
existuje polynom p a existuje polynomiální algoritmus K, takový, že pro instanci x je problém řešitelný právě tehdy, když existuje nápověda y o délce maximálně p(x): K(x,y) = 1
ekvivalentně je NP třída všech problémů, které lze řešit v polynomiálním čase na nedeterministickém turingově stroji
(ale turingovy stroje raději netahejme do složitosti, protože tam vychází věci jinak než na RAMu)
NPÚ je průnik tříd NP a NP-Hard, tedy třída problémů, na které lze převést všechny problémy v NP a zároveň samy lezí v NP
NPÚ jsou tedy ty nejtěžší problémy ze třídy NP

KLIKA : je zadán graf jako matice sousednosti - obsahuje kliku o velikost k?
NZMNOŽ : je zadán graf jako matice sousednosti - obsahuje nezávislou množinu o velikost k?
3SAT : je zadána výroková formula v CNF, kde každá klauzule obsahuje nejvýše 3 literály - je splnitelná?
TSP : je zadán ohodnocený úplný graf - existuje kružnice přes všechny vrcholy, která má součet vah hran nejvýše k?
TSP leží v ve třídě NP, protože když k řešitelné instanci dostaneme jako nápovědu správnou permutaci vrcholů, ověříme její váhu v lineárním čase
(NP-úplnost TSP bychom zdůvodnili tak, že pomocí něj lze vyřešit problém Hamiltonovy kružnice, který je také NPÚ:
za hrany vytvoříme hranu s hodnotou 1, za nehrany vytvoříme hranu s hodnotou 2 a pustíme TSP s k rovným počtu vrcholů)

mějme problém B, o kterém víme, že je NPÚ; ukážeme, že každou instanci B lze převést na instanci A tak, že A vydá stejnou odpověď jako B
tento převod musí běžet v polynomiálním čase (z toho plyne, že i vstup pro problém A se zvětšil nejvýše polynomiálně)

a) spokojit se s možností vyřešit jen velmi malé instance
b) omezit se na nějakou podmnožinu vstupů (speciální případy), pro kterou máme polynomiální algoritmus
c) použít aproximační algoritmus
d) použít heuristické řešení (například evoluční algoritmy), případně kombinace s aproximačním algoritmem



6. Vlákna

Vlákno je nějaká sekvence instrukcí, která se vykonává v procesoru (na jednom jádře).
Součástí jeho kontextu je stav registrů procesoru (včetně IP neboli PC) a obsah zásobníku.

running - právě se vykonává na procesoru
sleeping - čeká se na uvolnění nějakého prostředku, aby pak vlákno mohlo dál běžet
readyToRun - vlákno je připraveno k běhu a čeká na naplánování
terminated - čeká se na smazání

V proceduře Yield je potřeba uložit do paměti IP/PC, pak obsah všech registrů procesoru, stack pointer a celý call stack.
Z paměti je potřeba načíst kontext vlákna, které se má probudit, tedy jeho call stack, stack pointer, registry a nakonec IP/PC.
Naposledy upravil madvorak dne 24. 6. 2017 14:57, celkově upraveno 1
madvorak
Matfyz(ák|ačka) level I
 
Příspěvky: 7
Registrován: 2. 9. 2015 18:50
Typ studia: Informatika Bc.

Re: SZZ Bc. Informatika

Příspěvekod Katami » 21. 6. 2017 09:03

source port - port na straně klienta
destination port - port na straně "serveru"

např. při inicializaci komunikace s HTTP serverem si klient vybere nějaké pravděpodobné náhodné číslo portu (třeba 32875), které je source port a komunikuje standardně se serverem na portu 80 (destination port). Odpověď na tento požadavek ze strany serveru bude mít source port 80 a destination port ono náhodné klientovo číslo (třeba 32875).
Katami
Matfyz(ák|ačka) level I
 
Příspěvky: 20
Registrován: 3. 2. 2014 13:40
Typ studia: Informatika Bc.

Re: SZZ Bc. Informatika

Příspěvekod madvorak » 21. 6. 2017 11:10

Další vyřešená písemka (řeším jen informatické otázky, které jsou navíc platné pro moje zaměření):
https://www.mff.cuni.cz/studium/bcmgr/szz/priklady-podzim-2016.pdf
Opět požádám o kontrolu chyb, kterých jsem se dopustil.



1. Morfologická a syntaktická analýza

tagging - osazování slov značkami slovních druhů a gramatických kategorií
parsing - stavba syntaktického stromu věty (slovního spojení, většího celku)



2. Architektura počítače

Předpokládám, že jsou čísla zapsána jako big endian, tedy v podobě obvyklé pro lidi.
Hexadecimální číslo je dělitelné 8, pokud je jeho poslední cifra dělitelná 8 (obdoba dělitelnosti dekadických čísel 5).
Osmi jsou tedy dělitelná čísla 0xF13C1C50 a 0x5318C5E8.

Lepší výkon bude mít { a = b / 4; }, protože se operace přeloží na bitový shift (doprava o 2 pozice). Dělení je pomalejší operace.

Program napíšu v C#:
uint maskN = (1 << N) - 1;
uint maskM = (1 << M) - 1;
uint A = iA & maskN;
uint B = iB & maskM;
uint oC = A + (B << N); // místo plus by šlo použít or
return oC;



3. Databáze

Funkční závislosti atributů relace popisují, jestli je ze znalosti nějakého atributu (sloupce) jednoznačně určena hodnota jiného.
Relace R(K1, K2, A, B) nebude v 2NF, protože atribut B nezávisí na celém klíči.
Možná změna je rozdělení na R1(K1, K2, A) a R2(K2, B), která už bude v 2NF.

Rozvrh je serializovatelný, protože odpovídá sériovému provedení T1 před T2.

V druhé relaci nemohou existovat záznamy, které mají stejné K1 a liší se pouze v K2.



4. Databáze

Mějme relační schéma v 1NF. Toto schéma je zároveň v 2NF, pokud každý atribut závisí na celém klíči. Speciálně pokud je klíčem jediný atribut, je schéma v 2NF.
Příkladem relace, která je v 1NF, ale není v 2NF je R(A, B, C), kde klíčem je dvojice {A, B} a funkční závislost F = { A -> C }.

Rozvrh S není zotavitelný. Aby byl zotavitelný, bylo by potřeba Commit2 provést až po Commit1.

Sjednocení myslím nejde nahradit pomocí ostatních operací.



6. Halda

Halda je zakořeněný binární strom, kde každý prvek (kromě kořene) má vyšší hodnotu (pozdější prioritu) než jeho rodič.
V haldě musí platit, že hloubka všech listů se liší maximálně o 1 a poslední vrstva je zarovnána doleva.

Nejmenší prvek se nachází v kořeni. Největší prvek se může nacházet v libovolném listu.

vlož prvek do nejlevějšího prázdného místa dole;
while (prvek.hodnota < prvek.rodič.hodnota)
{
foo = prvek.rodič.hodnota;
prvek.rodič.hodnota = prvek.hodnota;
prvek.hodnota = foo;
prvek = prvek.rodič;
}

Pro spor nechť vložení i smazání prvku v n-prvkové haldě trvá o(log n). Pak dokážeme provést komparativní třídění n prvků v čase o(n log n),
protože stačí provést n-krát vložení prvku a pak n-krát smazání minima (s ukládáním hodnoty, při kterém získáváme setříděnou posloupnost).
Komparativní třídění nelze provést v čase o(n log n), protože existuje n! různých vstupů, které se liší přeuspořádáním hodnot.
Když se na běh celého programu podíváme jako na binární strom, kde vrcholy odpovídají provedení příkazu if, tak tento strom má n! listů.
Protože je to strom zakořeněný binární, jeho hlouba je alespoň logaritmus počtu listů, ale n! >= (n/2)^(n/2), takže jeho logaritmus musí být
alespoň (n/2) * log(n/2) = (n * (log(n) - 1)) / 2, což je Théta(n log n), takže to neleží v o(n log n).



9. Organizace paměti

Typická paměť RAM je skoro random-access. Sekvenční čtení je mírně rychlejší než "náhodné", ale rozdíl není zdaleka tak velký, jako třeba u HDD.
Pamětí ROM existuje několik druhů, které se liší podmínkami, za kterých lze přepsat jejich obsah. U některých se třeba smazání provádí světlem.
RAM dnes slouží jako operační paměť počítače, jejíž obsah se mění mnohokrát za sekundu. EEPROM se používá například na firmware.

BIOS se podívá do takzvaného Master boot sector, který se nachází v prvním oddílu disku (začátek HDD).
V něm je boot manager, který vybírá, ze kterého oddílu se načte operační systém.

Je boot loader něco jiného než boot manager ???



11. Neprocedurální programování

otec(Ot, Di) :- rodic(Ot, Di), muz(Ot).
dedecek(De, Di) :- otec(De, X), rodic(X, Di).

Seznamy jsou definovány rekurzivně. Seznam (neprázdný) se skládá z hlavy (to je první prvek) a těla, což je zase seznam. Zápis: [H|T].

Predikát r(+I,-O) vezme vstup I, zrotuje ho a vrátí jako výstup O.

Dotaz {X = 1 + 3.} se snaží o unifikaci levé strany výrazem {1 + 3}. Dotaz {X is 1 + 3} se pokusí za X dosadit hodnotu 4.



12. Rozhraní pro synchronizaci

Rozhraní bude obsahovat metody:
bool Lock();
void Unlock();
Lock() se pokusí zamknout zámek a vrátí, zda se to povedlo. Unlock() odemkne držený zámek.

Lock() { return CAS(ref variable, false, true); }
Unlock() { variable = false; }



13. Vyhledávací stromy

Binární vyhledávací strom je zakořeněný binární strom, kde každý prvek je >= prvkům v levém postromu a je <= prvkům v pravém podstromu.
Formálně zakořeněný binární strom je buď prázdná množina, nebo uzel, ve kterém je hodnota a má dva následníky, kteří jsou zase typu zakořeněný binární strom.
K tomu přidat podmínky na hodnoty klíčů.

AVL strom je binární vyhledávací strom, ve kterém pro každý uzel platí, že výška levého a pravého podstromu se liší maximálně o 1.

V obecném binárním stromu výšky 3 se můžou nacházet minimálně 4 vrcholy a maximálně 15 vrcholů.
V korektním AVL stromu výšky 3 se může nacházet minimálně 7 vrcholů a maximálně 15 vrcholů.
Pro AVL stromy platí, že minimální počet vrcholů roste po Fibonacciho číslech (mínus jedna) a maximální roste po mocninách dvojky (mínus jedna).

Následník vrcholu se nachází v jeho pravém podstromu jako nejlevější prvek. Pokud je pravý podstrom prázdný, tak se musí jít k rodiči.
Pokud je náš vrchol levým potomkem svého rodiče, je jeho následník samotný rodič.
Pokud je náš vrchol pravým potomkem, musíme jít k rodiči tohoto rodiče. První vzestupná hrana doprava nám určí následníka.



14. Topologické uspořádání

Topologické uspořádání na orientovaném grafu je očíslování vrcholů takovými čísly {1..n}, že hrany vedou vždy jen směrem rostoucího čísla.

Topologicky lze uspořádat jen acyklické grafy, tj. grafy bez orientované kružnice.
Topologické uspořádání není určeno jednoznačně.
Například prázdný graf má n! topologických uspořádání. Orientovaná cesta má jen 1 topologické uspořádání. Hvězda má (n-1)! topologických uspořádání.

Worst-case asymptotická složitost topologického uspořádání je Théta(N + M).
Vrcholy není potřeba řadit, ale stačí je na začátku rozdělit na ty s nulovým počtem vstupních hran a na ty ostatní.
Množinu vrcholů s nulovým počtem vstupních hran lze udržovat v celkovém čase Théta(N + M).

Idea algoritmu bude odpovídat Dijkstrově algoritmu, akorát budeme díky topologickému uspořádání dopředu znát pořadí uzavírání vrcholů.
Začneme zdrojovým vrcholem (kterému vzdálenost nastavíme na 0, ostatním nekonečno) a postupně si budeme brát vrcholy podle očíslování. Pro každý takový vrchol:
Jeho vzdálenost prohlásíme na definitivní
a pro všechny jeho následníky nastavíme vzdálenost na vzdálenost tohoto vrcholu + délku hrany, pokud už cíl nemá nižší vzdálenost.
Časová složitost bude Théta(N + M).
madvorak
Matfyz(ák|ačka) level I
 
Příspěvky: 7
Registrován: 2. 9. 2015 18:50
Typ studia: Informatika Bc.

Re: SZZ Bc. Informatika

Příspěvekod ggx » 23. 6. 2017 17:48

4. Databáze
sjednocené je možné pomocí ostatních operací:
AnB = (AuB)\((A\B)u(B\A))
ggx
 

Re: SZZ Bc. Informatika

Příspěvekod madvorak » 24. 6. 2017 14:57

ggx píše:4. Databáze
sjednocené je možné pomocí ostatních operací:
AnB = (AuB)\((A\B)u(B\A))


Obávám se, že jsi vyjádřil průnik pomocí ostatních operací. Souhlasíš teda s tím, že sjednocení vyjádřit pomocí ostatních nejde?
madvorak
Matfyz(ák|ačka) level I
 
Příspěvky: 7
Registrován: 2. 9. 2015 18:50
Typ studia: Informatika Bc.


Zpět na Bakalářské SZZ

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron