SZZ Bc. Informatika
Napsal: 21. 6. 2017 09:26
VAROVÁNÍ: Tento příspěvek jsem psal v očekování, že mi ostatní pomůžou opravit chyby v mých odpovědích. Protože jsem nedostal skoro žádné reakce, je to zřejmě málo zkontrolované a obsahuje to spoustu chyb. Neřiďte se mými odpověďmi. Prosím.
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/s ... o-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.
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/s ... o-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.