N´ev, azonos´ıt´ o:
MI
pont(90) :
Felv´ eteli vizsga Mesterk´ epz´ es, m´ ern¨ ok informatikus szak BME Villamosm´ ern¨ oki ´ es Informatikai Kar 2009. j´ unius 8.
´ MEGOLDASOK A dolgozat minden lapj´ ara, a kerettel jel¨ olt r´eszre ´ırja fel nev´et, valamint felv´eteli azonos´ıt´oj´ at! A feladatok megold´as´ ahoz csak pap´ır, ´ır´ oszer, zsebsz´amol´ og´ep haszn´alata megengedett, egy´eb seg´edeszk¨oz ´es a kommunik´aci´ o tiltott. A megold´asra ford´ıthat´ o id˝o: 120 perc. A feladatok ut´an azok pontsz´ am´ at is felt¨ untett¨ uk. A megold´asokat a feladatlapra ´ırja r´a, illetve ott jel¨olje. Teszt jelleg˝ u k´erd´esek eset´en elegend˝o a kiv´ alasztott v´alasz bet˝ ujel´enek bekarik´ az´asa. Kieg´esz´ıtend˝o k´erd´esek eset´en, k´erj¨ uk, adjon vil´agos, egy´ertelm˝ u v´alaszt. Ha egy v´alaszon jav´ıtani k´ıv´ an, teszt jelleg˝ u k´erd´esek eset´en ´ırja le az u ´ j bet˝ ujelet, egy´ebk´ent jav´ıt´asa legyen egy´ertelm˝ u. A feladatlapra ´ırt inform´aci´ ok k¨oz¨ ul csak az eredm´enyeket vessz¨ uk figyelembe. Az ´attekinthetetlen v´alaszokat nem ´ert´ekelj¨ uk. A vizsga v´egezt´evel mindenk´eppen be kell adnia dolgozat´ at. K´erj¨ uk, hogy a dolgozathoz m´as lapokat ne mell´ekeljen. Felh´ıvjuk figyelm´et, hogy illeg´alis seg´edeszk¨oz felhaszn´al´asa eset´en a fel¨ ugyel˝o kolleg´ ak a vizsg´ab´ol kiz´arj´ak, ennek k¨ovetkezt´eben felv´eteli vizsg´aja, illetve emelt szint˝ u z´ ar´ovizsg´ aja sikertelen lesz, amelynek let´etel´et csak a k¨ovetkez˝o felv´eteli, illetve z´ ar´ovizsga-id˝ oszakban k´ıs´erelheti meg u ´ jb´ ol.
Szakir´ anyv´ alaszt´ as
K´erem, az al´abbi t´ abl´ azatban jel¨ olje meg, mely szakir´ anyon k´ıv´ anja tanulm´anyait folytatni. A t´ abl´ azatban a szakir´ any neve mellett sz´ ammal jel¨ olje a sorrendet: 1-es sz´am az els˝o helyen kiv´ alasztott szakir´ anyhoz, 2-es a m´asodik helyen kiv´ alasztotthoz tartozik stb. Nem kell az ¨ osszes szakir´ any mell´e sz´amot ´ırni, de legal´ abb egy szakir´ anyt jel¨olj¨on meg. Egy sorsz´am csak egyszer szerepeljen.
szakir´ any neve
gondoz´o tansz´ek
Alkalmazott informatika szakir´ any Auton´om ir´ any´ıt´ o rendszerek ´es robotok szakir´ any H´ al´ ozatok ´es szolg´ altat´ asok szakir´ any H´ırk¨ ozl˝ o rendszerek biztons´aga szakir´ any Intelligens rendszerek szakir´ any M´ediainformatika szakir´ any Rendszerfejleszt´es szakir´ any Sz´am´ıt´ aselm´elet szakir´ any Szolg´ altat´ asbiztos rendszertervez´es szakir´ any
AAIT IIT TMIT HIT MIT TMIT IIT SZIT MIT
1
sorrend
M´ern¨ ok informatikus MSc felv´eteli
2009. j´ unius 8.
2
M´ern¨ ok informatikus MSc felv´eteli
Algoritmuselm´elet
2009. j´ unius 8.
N´ev, azonos´ıt´ o:
AL
pont(30) :
1. Legyen f1 (n) = n! + n6 ´es f2 (n) = (2n)! + 3. Igaz-e, hogy f1 = O(f2 ) ? f1 = Ω(f2 ) ? Megold´ as: igaz; hamis
pont(2):
¨ OL(7) ¨ 2. Az al´abbi bin´aris keres˝ of´ an hajtsa v´egre a TOR m˝ uveletet! 7
6
3 1
16 6
11
5
3 18
1
16 5
Megold´ as:
14
11
11
5 18
14
1
vagy
16 6
14
18
3
pont(2): 3. Nyitott c´ımz´es˝ u hashel´est alkalmazva egy kezdetben u ¨ res M = 11 m´eret˝ u t´ abl´ aba a h(k) = 2k (mod M ) hashf¨ uggv´enyt ´es kvadratikus marad´ek pr´ob´at haszn´alva sz´ urja be a megadott sorrendben a 4, 10, 26, 6, 17, 15 sz´amokat.
Megold´ as:
0
1 6
2 17
3
4 15
5
6
7 26
8 4
9 10
10
pont(2):
4. Legyen X egy n > 1 elem˝ u halmaz ´es legyen k egy eg´esz sz´am, 1 ≤ k ≤ n − 1. A G = (V, E) gr´af cs´ ucsai az X halmaz k elem˝ u r´eszhalmazainak felelnek meg. A k elem˝ u A, B ⊆ X halmazoknak megfelel˝o cs´ ucsok k¨oz¨ott a gr´afban akkor van ´el, ha A ∩ B = ∅. H´ any ´ele van a G gr´afnak?
Megold´ as:
n k
n−k k
· 2
pont(4):
5. Egy ter¨ ulet u ´ th´al´ ozat´at egy ir´ any´ıtatlan gr´ af ´ırja le. Sajnos ezek mindegyike rossz min˝os´eg˝ u, fel´ uj´ıt´asra szorul´o u ´ t, minden ´el s´ ulya a megfelel˝o u ´ tszakasz fel´ uj´ıt´asi k¨olts´ege. A gr´af minden cs´ ucsa vagy egy rakt´ arat vagy egy ´ szeretn´enk minim´ boltot jelk´epez. Ugy alis k¨olts´eggel n´eh´any u ´ tszakaszt fel´ uj´ıttatni, hogy v´eg¨ ul minden bolthoz valamelyik rakt´ arb´ ol el lehessen jutni olyan u ´ tvonalon, amelynek minden szakasza fel´ uj´ıtott. Melyik ismert algoritmust haszn´aln´ a a feladat megold´as´ara ´es milyen bemeneten futtatn´a azt?
Megold´ as: M´ odis´ıtjuk a gr´ afot: hozz´ avesz¨ unk egy cs´ ucsot, ahonnan minden rakt´ arhoz vezet egy 0 s´ uly´ u ´el (szuperrakt´ ar). Ebben a gr´afban minim´ alis s´ uly´ u fesz´ıt˝ of´ at kell meghat´arozni. Algoritmus lehet pl. Kruskal vagy Prim pont(4):
3
M´ern¨ ok informatikus MSc felv´eteli
Algoritmuselm´elet
2009. j´ unius 8.
6. Tegy¨ uk fel, hogy P 6= NP ´es tekints¨ uk a k¨ovetkez˝o A ´es B probl´em´ at. A:
adott a G gr´ af k´erd´es, hogy van-e G-ben 10 pont´ u teljes r´eszgr´ af.
B:
adott a G1 ´es G2 gr´ af k´erd´es, hogy van-e a G1 gr´ afnak a G2 gr´affal izomorf r´eszgr´ afja.
(i) R¨ oviden indokolja, hogy mi´ert van A-r˝ ol B-re Karp-redukci´o (polinomi´alis visszavezet´es)! Megold´ as: AzA probl´ema NP-beli (tan´ u egy 10 pont´ u klikk), B NP-teljes ´es minden NP-beli visszavezethet˝o egy NP-teljesre. (ii) Igaz-e, hogy B ≺ A ? Megold´ as: Nem.
pont(4):
7. Az A halmaz ´alljon az olyan G = (V, E) gr´afokb´ol, melyekben minden a, b ∈ V pontp´arhoz tal´ alhat´ok olyan a = v1 , v2 . . . , vt = b ∈ V cs´ ucsok (t ≥ 2), hogy {vi , vi+1 } ∈ E, ha 1 ≤ i ≤ t − 1. (i) Jellemezze az A-beli gr´ afokat!
Megold´ as: Az ¨osszef¨ ugg˝ o gr´ afok. (ii) V´ azoljon egy polinom l´ep´essz´ am´ u algoritmust, ami eld¨ onti, hogy egy ´ellist´ aval megadott G = (V, E) gr´af beletartozik-e az A halmazba!
Megold´ as: Sz´eless´egi bej´ ar´ as (BFS) vagy m´elys´egi bej´ ar´as (DFS).
pont(6):
8. Adott egy n ´es egy m hossz´ u 0-1 sorozat, a1 , a2 , . . . , an , illetve b1 , b2 , . . . , bm . Ezek alapj´an egy T t¨ omb¨ ot t¨ olt¨ ott¨ unk ki a k¨ovetkez˝o m´odon: Ha 0 ≤ i ≤ n, akkor T [i, 0] = 0. Ha 0 ≤ j ≤m, akkor T [0, j] = 0. T [i − 1, j − 1] + 1 ha ai = bj Ha 1 ≤ i ≤ n ´es 1 ≤ j ≤ m, akkor T [i, j] = max{T [i, j − 1], T [i − 1, j]} ha ai 6= bj ´Irja le, hogy mi a jelent´ese a T [i, j] ´ert´eknek! A k´et sorozatnak milyen tulajdons´ ag´at adja meg a T [n, m] ´ert´ek?
Megold´ as: T [i, j] az a1 , a2 , . . . ai ´es a b1 , b2 , . . . , bj sorozatok leghosszabb k¨oz¨os r´eszsorozat´anak hossza. T [n, m] az a ´es b sorozat leghosszabb k¨oz¨os r´eszsorozat´anak hossza.
4
pont(6):
M´ern¨ ok informatikus MSc felv´eteli
Sz´am´ıt´og´ep h´ al´ozatok
2009. j´ unius 8.
N´ev, azonos´ıt´ o:
H
pont(15) :
1. A TCP/IP architekt´ ur´aj´ u h´ al´ ozatokban a csatlakoz´ asi pontok h´ al´ozati r´etegbeli c´ımeik´ent az IP c´ımeket haszn´aljuk. Mi a szerep¨ uk az ilyen h´ al´ ozatokban az adatkapcsolati r´etegbeli c´ımeknek (amelyeket sokszor MAC c´ımeknek is nevez¨ unk)? a) L´enyeg´eben nincs szerep¨ uk, elegend˝o lenne az IP c´ım, de biztons´agi okokb´ ol adatkapcsolati azonos´ıt´ot is haszn´alnak. b) Nem el´eg az IP c´ım a csatlakoz´asi pont azonos´ıt´as´ara, mert a DHCP-vel kiosztott IP c´ımek esetr˝ ol esetre v´altozhatnak. c) Az adatkapcsolati ´es a h´ al´ ozati r´etegben p´ arhuzamosan alkalmazott f¨ uggetlen c´ımz´es a protokollr´etegek f¨ uggetlens´eg´enek elv´et val´ os´ıtja meg. d) A MAC c´ımek szerepe a h´ al´ ozat gerinc-r´esz´eben b´ır igaz´an nagy jelent˝ os´eggel, mert csak ´ıgy tudj´ak a gerinch´ al´ozati routerek cs¨ okkenteni az u ´ tvonalt´ abl´ aik m´eret´et. Megold´ as: c)
pont(2):
2. A t´ avols´agvektor-m´ odszert megval´ os´ıt´ o Bellman-Ford-algoritmus alkalmaz´asa sor´an egy adott id˝opontban a h´ al´ozat A csom´ opontja a k¨ovetkez˝o ´ allapotvektort tartja nyilv´ an: B, 1
C, 2
D, 3
E, 4
F, 1
D, 2
E, 4
H, 2
Meg´erkezik B-t˝ ol a k¨ovetkez˝o ´ allapotvektor: A, 1
C, 3
Mely bejegyz´essel/bejegyz´esekkel b˝ ov´ıti illetve m´odos´ıtja A az ´allapotvektor´at? Megold´ as: H, 3
pont(2):
3. A TCP/IP protokoll-architekt´ ura ,,interf´esz” r´eteg´enek mely ISO OSI architekt´ ura r´eteg(ek) felelnek meg? a) H´ al´ozati r´eteg. b) Sz´all´ıt´asi r´eteg. c) Adatbiztons´ agi r´eteg. d) Fizikai ´es adatkapcsolati r´etegek egy¨ utt. e) A fentiek k¨oz¨ ul egyik v´alasz sem helyes. Megold´ as: d)
pont(2):
4. Mit jelent az IEEE 802.11 szabv´any´ u WLAN-n´al az ESS (Extended Service Set)? a) Egy ,,access point”-ot ´es az ahhoz kapcsol´od´o v´egpontokat. b) A WLAN QoS-szolg´altat´ as´ at. c) A WLAN ´altal ny´ ujtott kieg´esz´ıt˝ o szolg´ altat´ asokat. d) WLAN-okat ´es Ethernet-gerincet tartalmaz´ o elrendez´est. e) Egyik v´alasz sem j´ o. Megold´ as: d)
pont(2):
5
M´ern¨ ok informatikus MSc felv´eteli
Sz´am´ıt´og´ep h´ al´ozatok
2009. j´ unius 8.
5. Az al´abbi ´all´ıt´asok k¨oz¨ ul melyik nem igaz a viv˝ o´erz´ekel´eses t¨ obbsz¨or¨os hozz´ af´er´eses elj´ar´asok tulajdons´ agai k¨oz¨ ul? a) Vezet´ekes (k´ abeles) fizikai k¨ozegen igen bonyolult a viv˝ o ´erz´ekel´ese. b) Az Aloha protokollokn´ al j´ oval nagyobb csatorna-kihaszn´ alts´agot ny´ ujtanak. c) Nagy ´erz´ekenys´eg a terjed´esi k´esleltet´esre: ameddig nem ´er hozz´ ank a jel, nem ´eszlelhetj¨ uk. ¨ oz´esdetekci´ d) Utk¨ oval kombin´ alva koaxi´ alis k´abeles fizikai k¨ozeg eset´en tov´abb n¨ ovelhet˝o a csatorna-kihaszn´ alts´ag. e) A fenti v´alaszok k¨oz¨ ul mindegyik igaz. Megold´ as: a)
pont(2):
6. Az al´abbiak k¨oz¨ ul mely feladato(ka)t l´atja el az UDP? a) Sorrendhelyes ´ atvitel. b) Portkezel´es. c) Forgalomszab´ alyoz´as. d) Torl´od´asvez´erl´es. e) A fentiek k¨oz¨ ul egyik v´alasz sem helyes. Megold´ as: b)
pont(2):
7. Az A ´es B v´egpontok TCP protokoll seg´ıts´eg´evel kommunik´alnak. Az A ´altal aktu´alisan B-nek k¨ uld¨ott szegmensben a sorsz´am 42, az ACK-sz´am 79, a szegmens 16 byte adatot tartalmaz. B a szegmens helyes v´etele eset´en milyen sorsz´amot ´es ACK-sz´amot helyez el az u ¨ zenet´eben? Megold´ as: 79;58b
pont(3):
6
M´ern¨ ok informatikus MSc felv´eteli
Oper´aci´ os rendszerek
2009. j´ unius 8.
N´ev, azonos´ıt´ o:
O
pont(15) :
1. Adja meg, hogy az al´ abbi v´alaszok k¨oz¨ ul melyek igazak illetve hamisak ! (i) Napjaink batch rendszereire az jellemz˝ o, hogy az azonos munkaf´ azisokat ig´enyl˝ o munk´ akat v´alogatjuk o¨ssze ´es futtatjuk egym´ as ut´an. igaz – hamis (ii) Ha u ´ j folyamat ´erkezik egy preempt´ıv rendszerbe, akkor a r¨ovidt´ av´ uu ¨ temez˝o mindig fut, ´es felt´etlen¨ ul bek¨ ovetkezik k¨ornyezetv´ alt´ as is. igaz – hamis (iii) A sz´alak (thread, pehelys´ uly´ u folyamat) p´ arhuzamos v´egrehajt´ as´ u, saj´at logikai processzorral rendelkez˝o programr´eszek a norm´ al folyamatokon (heavyweight process) bel¨ ul. igaz – hamis (iv) A kritikus szakasz megval´ os´ıt´ as´ an´al megismert test and set szinkroniz´aci´ os eszk¨ oz teljes´ıti a k¨olcs¨on¨os kiz´ar´as, a halad´as, ´es a v´eges v´arakoz´asi id˝o k¨ovetelm´enyeit. igaz – hamis (v) Blokkok ´ atmeneti, a k¨ozponti mem´ ori´aban vagy a perif´eria illeszt˝oben lev˝o t´ arban t¨ ort´en˝o t´ arol´as´an´al alkalmazott write through cache technika azt jelenti, hogy a tartalmi v´altoz´ asokat a t´ arral egy¨ utt a lemezre is azonnal fel´ırjuk. Ez rontja a teljes´ıtm´enyt, de n¨ oveli az adatt´arol´as biztons´ag´at. igaz – hamis pont(5): 2. Adja meg a helyes v´alaszt az al´ abbi k´erd´esekre! (i) Alkalmazhat´o-e a programsz´ aml´al´ o relat´ıv c´ımz´es glob´alis v´altoz´ ok kezel´es´en´el? igen – nem (ii) Igaz-e, hogy a homog´en t¨ obbprocesszoros rendszerekben az egy, k¨oz¨os r¨ovidt´ av´ uu ¨ temez´esi v´arakoz´asi sor haszn´alata jobb terhel´eseloszt´ast tesz lehet˝ov´e, m´ıg a heterog´en t¨ obbprocesszoros rendszerekben ´altal´ aban t¨ obb r¨ovidt´ av´ uu ¨ temez´esi v´arakoz´asi sort kell szervezni? igen – nem (iii) Jobb-e a p´ aszt´az´o (scan) diszk u ¨ temez´esi algoritmus ki´eheztet´es szempontj´ ab´ol a legr¨ovidebb fejmozg´ asi id˝o (SSTF: Shortest Seek Time First) algoritmusn´al? igen – nem pont(3): 3. V´ alassza ki, hogy az al´ abbiak k¨oz¨ ul mely tulajdons´ agok jellemz˝ oek a ´allom´anyokhoz tartoz´o blokkok nyilv´ antart´ as´an´al haszn´alt Folytonos ter¨ ulet lefoglal´ asa, L´ ancolt list´ as, illetve Indexelt t´ arol´as m´odszerekre. Folytonos ter¨ ulet lefoglal´ asa Nincs k¨ uls˝ o t¨ ordel˝ od´es A blokkok hasznos ter¨ ulete 2 eg´esz hatv´anya
L´ ancolt list´ as
Indexelt t´ arol´as
x
x
x
x x
A t´ arolt inform´aci´ ot sorosan lehet el´erni
pont(3):
7
M´ern¨ ok informatikus MSc felv´eteli
Oper´aci´ os rendszerek
2009. j´ unius 8.
4. Egy virtu´alis lapkezel´est alkalmaz´o rendszerben fut´o folyamatnak 4 mem´oriakerete van. A rendszer a M´ asodik es´ely (second chance, SC) lapcsere algoritmust alkalmazza. A folyamat laphivatkoz´asai a k¨ovetkez˝o sorrendben t¨ ort´ennek: 1, 2, 1, 3, 4, 2, 1, 5, 3, 6, 1. Laphib´at okoz-e a 11. (1-es logikai lapra t¨ ort´en˝o) hivatkoz´as? igen – nem Mely lapok lesznek a mem´ ori´aban az utols´ o hivatkoz´as ut´an? Megold´ as: 1, 3, 5, 6
pont(4):
8
M´ern¨ ok informatikus MSc felv´eteli
Szoftvertechnol´ ogia
2009. j´ unius 8.
N´ev, azonos´ıt´ o:
S1
pont(10) :
1. Az al´abbi UML2 diagram alapj´ an – a kulcs felhaszn´al´as´aval – jellemezze az ´all´ıt´asokat! <
> X
Z
+foo( )
+bar( )
S
Q -im +bar(s:S)
+bar(x:X)
R
B -val +foo(q:Q)
-qux(b:B)
A B C D E
– – – – –
ha mindk´et tagmondat igaz ´es a k¨ovetkeztet´es is helyes ha mindk´et tagmondat igaz, de a k¨ovetkeztet´es hamis ha csak az els˝o tagmondat igaz ha csak a m´asodik tagmondat igaz egyik tagmondat sem igaz
(+ + +) (+ + –) (+ –) (– +) (– –)
(i) B ´atadhat´ o param´eter¨ ul Q bar(s:S) met´odus´ anak, mert B-b˝ol el´erhet˝o Q.
(ii) B foo(q:Q) met´odusa m´odos´ıthatja saj´at val attrib´ utum´anak ´ert´ek´et, de az attrib´ utumnak mindig negat´ıvnak kell maradnia. Megold´ as: B; C
pont(2):
2. Adja meg a szoftver fejleszt´es´enek spir´ alis modellj´eben szerepl˝ o szektorokat (s´ıknegyedeket)! c´elok kijel¨ ol´ese . . . . . . . . . . . . . . . . . . . . . . .
kock´azat elemz´ese . . . . . . . . . . . . . . . . . . . . . . . . . .
fejleszt´es ´es valid´al´ as . . . . . . . . . . . . . . . . .
u ´ j f´azis tervez´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . pont(2):
3. Nevezze meg a verifik´aci´ o ´es valid´aci´ o sor´an alkalmazott k´et technik´at! 1. ´atvizsg´al´as
2. tesztel´es pont(2):
9
M´ern¨ ok informatikus MSc felv´eteli
Szoftvertechnol´ ogia
2009. j´ unius 8.
4. Pista elk´eri J´oska l´etr´ aj´ at. Pista a l´etr´ at pirosra festi ´es visszaadja a J´osk´anak. J´oska megn´ezi a l´etr´ at, majd a´tfesti k´ekre. Rajzoljon UML2 szekvenciadiagramot ! Megold´ as:
pont(2): 5. Gerzson lek´erdezi sz´ aml´aj´ anak egyenleg´et egy bankautomat´an. Rajzoljon UML2 use-case (haszn´ alati eset) diagramot! (K¨ oztudott, hogy a bankk´ arty´an nincs rajta a PIN-k´ od.) Megold´ as:
pont(2):
10
M´ern¨ ok informatikus MSc felv´eteli
Szoftvertechnik´ak
2009. j´ unius 8.
N´ev, azonos´ıt´ o:
S2
pont(10) :
1. Adja meg k´et-h´arom pontban, miben ´es hogyan seg´ıtenek a tervez´esi mint´ ak a szoftvertervez´es sor´an! Figyelem: Ne a tervez´esi minta defin´ıci´oj´ at adja meg!
Megold´ as: – N¨ ovelik a rendszer karbantarthat´os´ ag´at, m´odos´ıthat´os´ag´at; – n¨ ovelik az egyes r´eszek u ´ jrafelhaszn´ alhat´os´ag´at; – seg´ıtenek megtal´ alni a nem magukt´ ol ´ertet˝ od˝o oszt´alyokat. pont(2): 2. Milyen ´altal´ anos probl´em´ at old meg az Observer (Megfigyel˝o) tervez´esi minta?
Megold´ as: Lehet˝ov´e teszi, hogy egy objektum a megv´ altoz´ asa eset´en ´ertes´ıteni tudjon tetsz˝ oleges m´as objektumokat an´elk¨ ul, hogy b´ armit is tudna r´oluk.
pont(2):
3. Rajzolja fel az Observer minta oszt´alydiagramj´ at ´es jellemezze r¨oviden az oszt´alydiagramon szerepl˝ o oszt´alyokat! Megold´ as:
Subject: T´arolja a beregisztr´ alt Observer-eket. Observer: Interf´eszt defini´al azon objektumok sz´am´ ara, amelyek ´ertes¨ ulni szeretn´enek a Subject-ben bek¨ ovetkezett v´altoz´ asr´ol. ConcreteSubject: Az observer-ek sz´ am´ ara ´erdekes ´allapotot t´ arol, ´es ´ertes´ıti a beregisztr´ alt observer-eket, amikor az ´allapota megv´ altozik. ConcreteObserver: Referenci´ at t´ arol a megfigyelt ConcreteSubject objektumra, implemet´ alja az Observer interf´esz´et (Update m˝ uvelet).
pont(2):
11
M´ern¨ ok informatikus MSc felv´eteli
Szoftvertechnik´ak
2009. j´ unius 8.
4. Egy UML szekvenciadiagram seg´ıts´eg´evel mutassa be az Observer minta oszt´alyainak egy¨ uttm˝ uk¨od´es´et! Megold´ as:
A lesz´armazott ConcreteObserverek az Update f¨ uggv´eny fel¨ ul´ır´ as´aval ´ertes¨ ulnek a Subject v´altoz´ asair´ol. Ilyenkor lek´erik a ConcreteSubject ´ allapot´at, ´es reag´alnak a v´altoz´ asra. Ha az egyik Observer v´altoztatja meg a ConcreteSubject ´allapot´at, akkor a Notify f¨ uggv´eny megh´ıv´ as´aval ´ertes´ıthetik a t¨ obbi Observert bele´ertve saj´at magukat is. pont(2): 5. Adja meg r¨oviden a webalkalmaz´asokra vonatkoz´oan a kliensoldali szkript fogalm´at! Milyen jelleg˝ u m˝ uveleteket v´egezhet?
Megold´ as: Kliens oldali szkript seg´ıts´eg´evel a b¨ ong´esz˝ oben futtathatunk szkript k´odot, amely el˝oa´ll´ıthatja, vagy m´odos´ıthatja az oldalt. Bizonyos m˝ uveletek, mint pl. u ¨zenetablak megjelen´ıt´ese, nyomtat´ as, csak kliens oldali szkriptb˝ol kezdem´enyezhet˝ok. Legeltejedtebb kliens oldali szkript nyelv a Javascript. pont(2):
12
M´ern¨ ok informatikus MSc felv´eteli
Adatb´azisok
2009. j´ unius 8.
N´ev, azonos´ıt´ o:
AD
pont(10) :
1. V´egezzen rel´aci´ oanal´ızist az al´ abbi P–Q ´ all´ıt´ asp´ arok k¨oz¨ott! P ´es Q ¨onmag´ aban is lehet igaz vagy hamis, tov´abb´a az is eld¨ ontend˝ o, hogy van-e logikai kapcsolat k¨oz¨ott¨ uk. Ennek megfelel˝oen a lehets´eges v´alaszok: A B C D E P: ez´ert Q:
– – – – –
P igaz, Q igaz ´es van ¨osszef¨ ugg´es P igaz, Q igaz, de nem kapcsol´odnak P igaz, Q hamis P hamis, Q igaz mindkett˝ o hamis
Ha az r(R) rel´aci´ o X attrib´ utumhalmazon megegyez˝o elemei az Y attrib´ utumhalmazon is megegyeznek, akkor X determin´ansa Y -nak X → Y eset´en az Y attrib´ utumok ´ert´eke mindig kisz´ am´ıthat´o puszt´an az X attrib´ utumok ´ert´ekeib˝ ol.
Megold´ as: E P: mert Q:
pont(2):
Egy els˝odleges attrib´ utum lehet kulcs, de nem felt´etlen¨ ul els˝odleges kulcs az els˝odleges kulcs egy attrib´ utum, ami mindig els˝odleges attrib´ utum.
Megold´ as: C P: ez´ert Q:
pont(2):
Ha egy legal´ abb 1NF rel´aci´ os s´ema minden kulcsa egyetlen attrib´ utumb´ ol ´all, akkor a s´ema automatikusan legal´ abb 2NF is, b´ armely pontosan 1NF s´em´ at vesztes´egmentesen ´es f¨ ugg˝os´eg˝orz˝ oen fel lehet bontani legal´ abb 2NF r´eszs´em´ akba.
Megold´ as: B
pont(2):
2. Az al´abbiak k¨oz¨ ul melyeket z´ arj´ ak ki a 3NF s´em´ ak? (karik´ azza be valamennyi helyeset!) a) ´ert´ekf¨ ugg˝o k´enyszerek ´erv´enyes´ıt´ese b) ism´etl˝ od˝o attrib´ utum´ert´ek c) nemtrivi´alis funkcion´alis f¨ ugg´es d) m´asodlagos attrib´ utum tranzit´ıv f¨ ugg´ese kulcst´ol e) f¨ ugg˝os´eg˝orz´es (nemtrivi´ alis f¨ ugg´eseket tartalmaz´ o f¨ ugg´eshalmaz eset´en) f ) ¨osszetett (nem atomi) attrib´ utum g) t¨ obb kulcs egy s´em´ aban h) t¨ obb els˝odleges attrib´ utum egy s´em´ aban Megold´ as: d), f )
pont(2):
3. Adja meg az R(LM N OP ) s´ema attrib´ utumain ´ertelmezett F = {N O → P, L → M, LM → N O, M → LN, O → L} funkcion´alis f¨ ugg´eshalmaz egy minim´ alis fed´es´et!
Megold´ as: Fmin = {L → M, L → O ( vagy M → O), L → N ( vagy M → N ), M → L, O → P, O → L} pont(2):
13
M´ern¨ ok informatikus MSc felv´eteli
Adatb´azisok
14
2009. j´ unius 8.
