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/s ... m-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).
Další vyřešená písemka (řeším jen informatické otázky, které jsou navíc platné pro moje zaměření):
[url]https://www.mff.cuni.cz/studium/bcmgr/szz/priklady-podzim-2016.pdf[/url]
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).