Infó MSc felvételi 2010. január 4.

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

AlgEl

1. Legyen $f_{1}(n)=10nlog_{2}n+3n^{2}+15$ és $f_{2}(n)=32n*2^{log_{2}n}+8n^{\frac {3}{2}}+15$. Igaz-e,hogy

$f_{1}=O(f_{2})$ ? $f_{2}=O(f_{1})$ ?

1. Az alábbi kupacon (min-kupac) hajtsa végre a BESZÚR(3) művelete és az eredményt rajzolja le

• • ...

1. Az n pontú teljes gráfból kihagytunk egy élet. Hány 3 hosszú kör van az így kapott gráfban?
2. Az alábbi gráfon az A ponttól vett távolságok meghatározására a Dijkstra-algoritmust futtatjuk. Folytassa az alábbi, a számított távolságokat tartalmazó táblázat kitöltését, amíg megkapja a legrövidebb utak hosszát!

• • ...

1. Az $a_{1},a_{2},...,a_{2n}$ sorozatot beszúrásos rendezéssel, lineáris kereséssel rendezzük. Mennyi az algoritmus során az összehasonlítások száma, ha a rendezés után a sorrend $a_{n+1}<a_{n+2}<...<a_{2n}<a_{1}<a_{2}<...<a_{n}$ ?
2. Az A halmaz álljon az olyan G = (V, E) irányítatlan gráfokból, melyekre igaz a következő: $\exists X\subseteq V$, hogy $\forall x,y\in V$ pontpárhoz, ha ${x,y}\in E$, akkor $(x\in X$ és $y\notin X)$ vagy $(x\notin X$ és $y\in X)$. Jellemezze szavakkal az A-beli gráfokat!
3. Igaz-e, hogy az alábbi probléma NP-ben van? Válaszát röviden indokolja is! Adott: G páros gráf és egy k pozitív egész szám. Kérdés: A G-beli maximális párosítás k élből áll-e?
4. Éllistájával adott egy n csúcsú e élű összefüggő irányítatlan gráf, melyben minden él súlya 1 vagy 5. Vázoljon egy $O(n+e)$ lépésszámú algoritmust, amely meghatározza a gráf egy minimális súlyú feszítőfájának súlyát!

Hálók

1. Kösse össze egyenes vonallal az egyik oszlopban található protokollokat és a hozzájuk tartozó adategység megnevezését! (2p)

• • IP - csomag
  • Ethernet - keret
  • TCP - szegmens

1. Az alábbiak közül melyek a TCP és az UDP közös jellemzői? (2p)
   1. Sorrendhelyes átvitel
   2. Porthasználat
   3. Forgalomszabályozás
   4. 3-utas kézfogás (3-way handshake)
   5. Szállítási rétegbeli protokoll
2. Az alábbiak közül mely hálózati eszköz(ök) használja(k) mindenkép a hálózati rétegbeli funkcionalitást (is)? (2p)
   1. Hub (többkapus ismétlő)
   2. Router (forgalomirányító vagy útválasztó)
   3. Gateway (átjáró)
   4. Switch (kapcsoló)
3. Az alábbiak közül melyik állítás nem igaz a DNS-re? (2p)
   1. A DNS egy névfeloldási protokoll.
   2. A névtér hierarchikus
   3. Az 53-as portot használja
   4. A DNS-szervereken a zónákban rekordok (bejegyzések) találhatók
   5. Egy tartománynak több elsődleges és több másodlagos szerverrel kell rendelkeznie, mely a tartományt szolgáltatja.
4. Egy új LAN technológiát tervezünk. 1 Gbit/s-os adatátviteli sebesség mellett minimum mekkorára kell választani a minimális adategységméretet bájtban mérve, ha rézvezetőn CSMA/CD-t használunk, és a két legtávolabbi állomás maximum 40 m-re lehet egymástól? (Rézben a jelterjedési sebesség $2*10^{8}$ m/s.) (3p)

Ütközésérzékeléshez a minimális idő= ${\frac {2L}{C}}={\frac {2*40}{2*10^{8}}}=4*10^{-7}$ sec. Ennyi idő alatt 1Gbit/seccel az átvitt adatmennyiség $4*10^{-7}*10^{9}=400bit=50Byte$

1. Az alábbiak közül mely(ek) egy IPv4-es router feladata(i)? (2p)
   1. A TTL (Time to Live) érték csökkentése
   2. TCP folyamvezérlés
   3. Útvonalválasztás az SMTP szerver válasza alapján
   4. Szükség esetén újratördelés
   5. Az FTP forgalom titkosítása
2. Mely állítás(ok) igaz(ak) az alábbiak közül az RTS/CTS-re? (2p)
   1. Az RTS/CTS hányados értéke minden hálózatban 1-nél kisebb
   2. WLAN-oknál használt mechanizmus
   3. A rejtett állomás problémájára (hidden terminal) ad megoldást
   4. Az RTS/CTS-ben az RTS a Response Time in Seconds rövidítése

OpRe

1. Az alábbiak közül mely állítások igazak a kemény valós idejű (hard real-time) rendszerekre? (2p)
   1. A beérkező kéréseket kiszolgáló folyamatok a legmagasabb prioritással futnak az ilyen rendszerekben.
   2. A beérkező kérésekre a specifikációban megadott időkorláton belül helyesen válaszolnak, egyébként működésük hibásnak tekintendő.
   3. A beérkező kérésekre egy megadott, 1-től eltérő, de 1-hez közeli valószínűséggel reagálnak megadott időkorláton belül.
   4. Az általános célú operációs rendszerek (Windows, UNIX) nem alkalmazhatók kemény valós idejű rendszerekben.
   5. A fentiek közül egyik állítás sem igaz.

...

SzoftTech (LZ-féle)

...

SzoftTech (tervezési mintás)

1. Adja meg két-három pontban, miben és hogyan segítenek a tervezési minták a szoftvertervezés során! _Figyelem_: Ne a tervezési minta definícióját adja meg! (2p)
2. Milyen általános problémát old meg a Factory Method (Metódusgyár) tervezési minta? (2p)
3. Rajzolja fel általánosságban vagy egy példára vonatkozóan a Factory Method (Metódusgyár) minta osztálydiagramját! (2p)
4. Az előző feladat osztálydiagramjára építve ismertesse általánosságában vagy egy példa alapján a Factory Method minta működését, jellemezze a benne szereplő osztályokat! (2p)
5. Hasonlítsa össze a kliens és kiszolgáló oldali szkript szerepét a webalkalmazásokra vonatkozóan! (2p)

Adatbázisok

Minden BCNF séma egyben 3NF is. Mivel minden 3NF sémára illeszkedő reláció tartalmazhat redundanciát funkcionális függés következtében, ezért a BCNF sémára illeszkedő reláció is tartalmazhat redundanciát funkcionális függés következtében. (2p)

Az első mondat igaz (tétel a könyvben). Viszont a második mondat első és második fele sem igaz: Nem minden 3NF sémára illeszkedik olyan reláció, ami tartalmaz funkcionális függés miatti redundanciát. A második fele sem igaz (tétel a könyvben). A 3NF-ség csupán nem zárja ki a rendundanciát tartalmazó reláció létezésének lehetőségét, de a létezését nem kényszeríti ki (például a BCNF-ekre pont nem is létezik redundáns reláció).

Igaz-e, hogy egy sémafelbontás következtében a rész-sémák normálformája nem csökkenhet? (2p)

Eredetileg ezt válaszolták -> Igaz.

Jó: Biztos hamis . Dehogynem csökkenhet a részsémák normálformája. Van olyan, hogy (R,F) séma BCNF, de lehet úgy képezni a dolgokat, hogy (R1,F1) vagy (R2,F2) séma normálformája csökkenhet.

Részsémák kisebbtől a nagyobbig. 0. NF; 1. NF; 2. NF; 3. NF; BCNF; 4. NF; 5. NF

Klasszikus példa, hogy az állítás hamis.

R(A,B,C,D,E) F(AB->C; BC->D; CD->E; DE->A; EA->B) => BCNF
R1(A,B,C) F1(AB->C) => BCNF
R2(A,B,D,E) F2(DE->A,EA->B) => Jelen esetben EA->B függés sérti a BCNF tulajdonságot, mert EA nem szuperkulcs. DEA a kulcs, DEA elsődleges B másodlagos attribútum R2-ben. R2 nem is 3 NF mert EA->B függésben EA sem szuperkulcs, és B sem elsődleges attribútum. R2 sem 2 NF, mert teljesül rá, hogy van olyan másodlagos attribútum (B) amely függ valamelyik kulcs (ADE) valódi részhalmazától (AE). Az R2 reláció 1. NF-ben van, mert minden attribútum atomi.

mivel 1. NF < BCNF => csökkent a részséma normálformája. ==> állítás hamis.

Egy 2.000.000 rekordból álló állományt szeretnénk "vödrös hash" szervezéssel tárolni. A rekordhossz 240 byte, egy blokk kapacitása (a fejrészt nem számítva) 2000 byte. A kulcsok 25 byte-osak, egy mutatóhoz 8 byte kell. A rekordok kiolvasására legfeljebb 4 blokkelérési időt engedélyezve számítsa ki a vödrök minimális számát és a hash-tábla minimális méretét! (Tételezze fel, hogy a vödörkatalógus kereséskor memóriában tartható és a hash függvény egyenletesen osztja el a kulcsokat.) (2p)

2000 byte / 240 byte alsó egész része: 8

Egy blokkban 8 rekordunk lesz.

max 4 blokkból el akarjuk érni a rekordokat akkor egy vödörben max 4 blokk lehet, 4*8 = 32 rekordot tárolunk vödrönként. 2 000 000 / 32 = 62 500 vödrünk lesz.

Máshogy számolva: 2 000 000 / 8 = 250 000 blokk kell a tarolashoz. ha 4 blokkeleres kell, es a hashtabla kiolvasasa nem szamit annak, akkor 4 blokk/vödör; 250 000 blokkhoz 250 000 / 4 = 62 500 vödör.

A vödörkatalógusban csak mutatókat tárolunk

62 500 * 8byte = 500 000 byte

Kövesse lépésről lépésre a tranzakciók sorsát időbélyeges író-olvasó modellt alkalmazó tranzakciókezelés mellett! A tranzakciók időbélyege: T1: 10, T2: 20. (2p)

*T1*:10	*T2*:20
Read A
	Read A
	Write B
Read B
Write A

-- molnarm - 2010.12.29. -- ijanos - 2010.12.31.