Bakal´aˇrsk´e zkouˇsky (pˇr´ıklady ot´azek)
podzim 2014
1
Nejkratˇ s´ı cesta grafem 1. Uvaˇzujte graf s kladn´ ym ohodnocen´ım hran (d´elka). Definujte form´alnˇe probl´em hled´an´ı nejkratˇs´ı cesty mezi dvˇema uzly tohoto grafu. 2. Napiˇste pseudok´ od algoritmu pro hled´ an´ı nejkratˇs´ı cesty mezi dvˇema uzly grafu s kladn´ ym ohodnocen´ım hran.
2
Vyhled´ av´ an´ı v textu 1. Popiˇste strukturu vyhled´ avac´ıho automatu algoritmu Aho Corasick pro vyhled´av´an´ı v textu (naˇcrtnˇete pˇr´ıklad pro hledan´e ˇretˇezce he“, she“, her“). ” ” ” 2. Napiˇste pseudok´ od algoritmu Aho Corasick pro vyhled´av´an´ı v textu (pouze vyhled´av´an´ı, nikoliv konstrukci vyhled´ avac´ıho automatu). 3. Jak´ a je ˇcasov´ a sloˇzitost tohoto algoritmu ?
3
Architektura poˇ c´ıtaˇ ce
Uvaˇzujte celoˇc´ıseln´ y datov´ y typ INT reprezentovan´ y vnitˇrnˇe v osmi bitech pomoc´ı dvojkov´eho doplˇ nku, tedy napˇr´ıklad ˇc´ıslo 0 je reprezentov´ ano jako 000000002 , ˇc´ıslo 1 jako 000000012 , ˇc´ıslo 127 jako 011111112 , ˇc´ıslo −1 jako 111111112 . Pˇredpokl´ adejte, ˇze operace + pro typ INT je vnitˇrnˇe implementov´ana jako prost´e osmibitov´e bin´arn´ı sˇc´ıt´an´ı, tedy neuvaˇzuje se znam´enko a neindikuje se pˇreteˇcen´ı, v´ ysledek se oˇrez´av´a na osm bit˚ u. 1. Jak´e nejmenˇs´ı a nejvˇetˇs´ı ˇc´ıslo je moˇzn´e zapsat v datov´em typu INT ? 2. Jak´ y bude v´ ysledek operace 127 + 1 pro typ INT ? 3. Jak´ y bude v´ ysledek operace −127 + (−1) pro typ INT ? 4. Uvaˇzujte x jako promˇennou typu INT a MIN jako konstantu rovnou nejmenˇs´ımu ˇc´ıslu typu INT. Jak´ y bude obsah promˇenn´e x po proveden´ı n´ asleduj´ıc´ıho bloku k´ odu ? V odpovˇedi neuvaˇzujte moˇzn´e optimalizace pˇrekladaˇce. x = MIN x = -x
4
Vstupn´ı a v´ ystupn´ı zaˇ r´ızen´ı
Uvaˇzujte bˇeˇznou architekturu poˇc´ıtaˇce, ve kter´e zaˇr´ızen´ı mohou ˇz´adat o obsluhu pomoc´ı pˇreruˇsen´ı. Pˇredpokl´ adejte, ˇze mezi pˇripojen´ ymi zaˇr´ızen´ımi jsou kl´ avesnice, grafick´ y adapter (displej) a disk. 1. Kter´ a z uveden´ ych zaˇr´ızen´ı a v jak´ ych situac´ıch budou pravdˇepodobnˇe ˇz´adat o pˇreruˇsen´ı ? 2. Jak´ ym zp˚ usobem ˇz´ ad´ a zaˇr´ızen´ı o pˇreruˇsen´ı ? Konkr´etnˇe, jak se v architektuˇre poˇc´ıtaˇce informace o potˇrebˇe obsluhy dostane od zaˇr´ızen´ı k procesoru. 3. Jak procesor reaguje na ˇz´ adost o pˇreruˇsen´ı ? Konkr´etnˇe, popiˇste bezprostˇredn´ı reakci z pohledu hardware, nikoliv kroky realizovan´e pomoc´ı software.
5
Automaty 1. Definujte form´ alnˇe pojem koneˇcn´ y automat“. ” 2. Definujte form´ alnˇe kdy koneˇcn´ y automat pˇrij´ım´a slovo. 3. M˚ uˇze koneˇcn´ y automat rozpozn´ avat tak´e nekoneˇcn´e jazyky ? 4. Sestavte koneˇcn´ y automat, kter´ y pˇrij´ım´ a stejn´ y jazyk jako regul´arn´ı v´ yraz ^[a-z]+@[a-z]+\.[a-z.]+$ (v´ yraz pro jednoduchou kontrolu adresy mailu).
6
Transakce 1. Definujte pravidla pro izolaci transakc´ı s pouˇzit´ım dvouf´azov´eho zamyk´an´ı. 2. Uvaˇzujte transakce T1: R(X)R(Y ) a T2: W (X)W (Y ). Napiˇste vˇsechny rozvrhy, kter´ ymi m˚ uˇze tyto transakce pl´ anovat dvouf´ azov´e zamyk´ an´ı (vyznaˇcte i operace zamˇcen´ı a odemˇcen´ı). 3. M˚ uˇze v´est dvouf´ azov´e zamyk´ an´ı nad tˇemito transakcemi k uv´aznut´ı a proˇc ?
7
Principy implementace objektovˇ e orientovan´ ych jazyk˚ u 1. Vysvˇetlete rozd´ıl mezi pˇred´ av´ an´ım parametr˚ u funkce (metody) hodnotou (pass by value) a odkazem (pass by reference). V jak´ ych situac´ıch se hod´ı jeden ˇci druh´ y zp˚ usob pˇred´av´an´ı parametr˚ u? Uvaˇzujte n´ asleduj´ıc´ı k´ od (z dostupn´ ych verz´ı si vyberte jeden programovac´ı jazyk, pozor, verze se nechovaj´ı stejnˇe): Listing 1: Java c l a s s Main { s t a t i c void f ( I n t e g e r x ) { i f ( x > 0 ) { x−−; f ( x ) ; } } public s t a t i c void main ( S t r i n g [ ] arguments ) { int a = 8 ; f ( a ) ; System . out . p r i n t l n ( a ) ; } } Listing 2: C++ #include
void f ( int &x ) { i f ( x > 0 ) { x−−; f ( x ) ; } } int main ( ) { int a = 8 ; f ( a ) ; s t d : : c o u t << a << s t d : : e n d l ; return ( 0 ) ; } Listing 3: C# using System ; c l a s s Example { s t a t i c void f ( r e f int x ) { i f ( x > 0 ) { x−−; f ( r e f x ) ; } } s t a t i c void Main ( string [ ] arguments ) { int a = 8 ; f ( r e f a ) ; C o n s o l e . WriteLine ( a ) ; } }
2. Kolikr´ at se zavol´ a funkce f ? 3. Jak´ y v´ ystup nap´ıˇse k´ od pˇri spuˇstˇen´ı ?
8
Principy implementace objektovˇ e orientovan´ ych jazyk˚ u 1. Vysvˇetlete, co je statick´ y atribut tˇr´ıdy (static field, static class variable, static member variable). 2. Uvaˇzujte tˇr´ıdu s n´ asleduj´ıc´ım rozhran´ım (z dostupn´ ych verz´ı si vyberte jeden programovac´ı jazyk): Listing 4: Java public c l a s s S i n g l e t o n { public s t a t i c S i n g l e t o n g e t I n s t a n c e ( ) { ... } } Listing 5: C++ class Singleton { public : s t a t i c S i n g l e t o n& g e t I n s t a n c e ( ) { ... } }; Listing 6: C# public c l a s s S i n g l e t o n { public s t a t i c S i n g l e t o n I n s t a n c e { get { ... } } } Doplˇ nte implementaci tˇr´ıdy Singleton tak, aby uveden´a metoda (getter) vˇzdy vracela referenci na jedinou Singleton instanci, a aby se tato instance vytvoˇrila pˇri prvn´ım vol´an´ı uveden´e metody (getteru). Neuvaˇzujte existenci v´ıce vl´ aken. 3. Jak doc´ıl´ıte toho, aby program´ ator nemˇel moˇznost obej´ıt uvedenou metodu (getter) a vytvoˇrit si v´ıce instanc´ı tˇr´ıdy Singleton napˇr´ıklad pˇr´ımo vol´ an´ım new ?
9
Protokoly TCP/IP 1. Jak vypad´ a adresa komunikuj´ıc´ıho procesu v protokolu TCP ? 2. Po jak´ ych jednotk´ ach potvrzuje protokol TCP pˇrijat´a data ? Jak protokol TCP minimalizuje poˇcet datagram˚ u pˇren´ aˇsen´ ych kv˚ uli potvrzen´ı ? 3. Jak protokol TCP ˇr´ıd´ı tok v situaci, kdy odes´ılatel produkuje data rychleji, neˇz je pˇr´ıjemce schopen je zpracovat ? 4. Jak´e internetov´e protokoly jsou vystavˇeny nad protokolem TCP (nejm´enˇe dva pˇr´ıklady) ?
10
Rozklad polynom˚ u
1. Definujte pojem ireducibiln´ı polynom nad tˇelesem T “. ” 2. Nad kter´ ymi z uveden´ ych tˇeles existuje ireducibiln´ı polynom stupnˇe alespoˇ n dva (ilustrujte pˇr´ıkladem): Q, C, Z2 , Z3 ?
11
Rozklad polynom˚ u
1. Definujte pojem v´ıcen´ asobn´ y koˇren polynomu“. ” 2. Pro kter´ a z uveden´ ych tˇeles se polynom x4 − 2x3 + 2x2 − 2x + 1 rozkl´ad´a na line´arn´ı ˇcinitele: Q, C, Z2 , Z3 ?
12
Limita posloupnosti
1. Definujte pojem limita posloupnosti re´ aln´ ych ˇc´ısel“ (vlastn´ı i nevlastn´ı). ” 2. Vyslovte vˇetu o str´ aˇzn´ıc´ıch. 3. Rozhodnˇete, zda existuje limita a pokud ano, spoˇctˇete ji: √ 1 + 2 + · · · + b nc n→∞ n lim
13
Metrick´ e prostory
1. Definujte pojem uzavˇren´ a mnoˇzina“ v metrick´em prostoru. ” 2. Rozhodnˇete o platnosti n´ asleduj´ıc´ıch tvrzen´ı: (a) Jsou-li F1 , F2 , . . . uzavˇren´e mnoˇziny, je i ∪∞ ren´a mnoˇzina. n=1 Fn uzavˇ (b) Jsou-li F1 , F2 , . . . uzavˇren´e mnoˇziny, je i ∩∞ ren´a mnoˇzina. n=1 Fn uzavˇ (c) Nen´ı moˇzn´e, aby byly uzavˇren´e mnoˇziny A i X \ A. 3. Jsou n´ asleduj´ıc´ı mnoˇziny uzavˇren´e ? Zd˚ uvodnˇete. (a) (1, ∞) (b) {0} (c) ∅
14
Metrick´ e prostory
1. Definujte pojmy metrika“ a metrick´ y prostor“. ” ” 2. Rozhodnˇete o n´ asleduj´ıc´ıch mnoˇzin´ ach, zda jsou otevˇren´e a zda jsou uzavˇren´e v metrick´em prostoru re´ aln´ ych ˇc´ısel s eukleidovskou metrikou. O jedn´e z tˇechto mnoˇzin vaˇse tvrzen´ı dokaˇzte. (a) < 0, 1 > (b) (0, ∞) (c) (−∞, 1 > (d) (−∞, ∞)
15
Skal´ arn´ı souˇ cin
1. Definujte re´ aln´ y skal´ arn´ı souˇcin. 2. Rozhodnˇete, zda je skal´ arn´ım souˇcinem nad R3 zobrazen´ı hx, yi = 2x1 y1 + 2x2 y2 + 2x3 y3 + x1 y3 + x3 y1 + x2 y3 + x3 y2 .
16
Eulerovsk´ e grafy
1. Definujte eulerovsk´ y graf. 2. Formulujte nutnou a postaˇcuj´ıc´ı podm´ınku pro to, aby graf byl eulerovsk´ y (Eulerovu vˇetu). 3. Necht’ n ∈ N, uvaˇzujme graf G = (V, E) s vrcholy V = {0, 1}n a hranami mezi tˇemi vrcholy, jejichˇz posloupnosti se liˇs´ı v lich´em poˇctu pozic (tedy napˇr´ıklad pro n = 2 je V00 spojen s V01 a V10 ale nikoliv s V11 ). Pro kter´a n je tento graf eulerovsk´ y?
17
Vlastnosti graf˚ u
1. Definujte stupeˇ n vrcholu v (neorientovan´em) grafu. 2. Vyj´ adˇrete (bez sumy) souˇcet stupˇ n˚ u vrchol˚ u stromu, tedy
P
v∈V
deg(v) pro strom T = (V, E).
3. V z´ avislosti na pˇrirozen´em ˇc´ısle n rozhodnˇete, kdy existuje graf s 2n vrcholy takov´ y, ˇze n vrchol˚ u m´a stupeˇ n 1 a n vrchol˚ u stupeˇ n 2. Pro kter´ a n existuje takov´ y graf, kter´ y je nav´ıc souvisl´ y?
