VIK Wiki

„Infó MSc felvételi 2010. január 4.” változatai közötti eltérés

Újabb szerkesztés →
VizuálisWikiszöveges
Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfoMscFelv2010jan04}} __TOC__ ==AlgEl== # Legyen <math>f_1(n) = 10nlog_2n + 3n^2 + 15</math> és <math>f_2(n) = 32n * 2^{log_2n} + 8n^{\f…”
 
Szikszayl (vitalap | szerkesztései)
4 274 szerkesztés
Nincs szerkesztési összefoglaló
1. sor: 1. sor:
{{GlobalTemplate|Infoalap|InfoMscFelv2010jan04}}
__TOC__
==AlgEl==
# Legyen <math>f_1(n) = 10nlog_2n + 3n^2 + 15</math> és <math>f_2(n) = 32n * 2^{log_2n} + 8n^{\frac{3}{2}} + 15</math>. Igaz-e,hogy
<math>f_1 = O(f_2)</math> ?
<math>f_2 = O(f_1)</math> ?
# Az alábbi kupacon (min-kupac) hajtsa végre a BESZÚR(3) művelete és az eredményt rajzolja le
** ...
# Az n pontú teljes gráfból kihagytunk egy élet. Hány 3 hosszú kör van az így kapott gráfban?
# 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!
** ...
# Az <math>a_1, a_2, ... , a_{2n}</math> 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 <math>a_{n+1} < a_{n+2} < ... < a_{2n} < a_1 < a_2 < ... < a_n</math> ?
# Az A halmaz álljon az olyan G = (V, E) irányítatlan gráfokból, melyekre igaz a következő: <math>\exists X \subseteq V</math>, hogy <math>\forall x,y \in V</math> pontpárhoz, ha <math>{x,y} \in E</math>, akkor <math>(x \in X</math> és <math>y \notin X)</math> vagy <math>(x \notin X</math> és <math>y \in X)</math>. Jellemezze szavakkal az A-beli gráfokat!
# 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?
# É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 <math>O(n + e)</math> 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==
==Hálók==
# Kösse össze egyenes vonallal az egyik oszlopban található protokollokat és a hozzájuk tartozó adategység megnevezését! (2p)
# Kösse össze egyenes vonallal az egyik oszlopban található protokollokat és a hozzájuk tartozó adategység megnevezését! (2p)
** IP - csomag
#* IP - csomag
** Ethernet - keret
#* Ethernet - keret
** TCP - szegmens
#* TCP - szegmens
# Az alábbiak közül melyek a TCP és az UDP közös jellemzői? (2p)
# Az alábbiak közül melyek a TCP és az UDP közös jellemzői? (2p)
## Sorrendhelyes átvitel
## Sorrendhelyes átvitel
42. sor: 21. sor:
## A DNS-szervereken a zónákban rekordok (bejegyzések) találhatók
## A DNS-szervereken a zónákban rekordok (bejegyzések) találhatók
## '''Egy tartománynak több elsődleges és több másodlagos szerverrel kell rendelkeznie, mely a tartományt szolgáltatja.'''
## '''Egy tartománynak több elsődleges és több másodlagos szerverrel kell rendelkeznie, mely a tartományt szolgáltatja.'''
# 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 <math> 2*10^8 </math> m/s.) (3p)
# 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ő= <math> \frac{2L}{C}=\frac{2*40}{2*10^8}=4*10^{-7} </math> sec. Ennyi idő alatt 1Gbit/seccel az átvitt adatmennyiség <math> 4*10^{-7}*10^9=400 bit=50Byte </math>  
#*Ütközésérzékeléshez a minimális idő = <math> \frac{2L}{C}=\frac{2*40}{2*10^8}=4*10^{-7} </math> sec. Ennyi idő alatt 1Gbit/seccel az átvitt adatmennyiség <math> 4*10^{-7}*10^9=400 bit=50Byte </math>  
# Az alábbiak közül mely(ek) egy IPv4-es router feladata(i)? (2p)
# Az alábbiak közül mely(ek) egy IPv4-es router feladata(i)? (2p)
## '''A TTL (Time to Live) érték csökkentése'''
## '''A TTL (Time to Live) érték csökkentése'''
57. sor: 36. sor:


==OpRe==
==OpRe==
# Az alábbiak közül mely állítások ''igazak'' a kemény valós idejű (hard real-time) rendszerekre? (2p)
# Az alábbiak közül mely állítások ''igazak'' a kemény valós idejű (hard real-time) rendszerekre? (2p)
## A beérkező kéréseket kiszolgáló folyamatok a legmagasabb prioritással futnak az ilyen rendszerekben.
## A beérkező kéréseket kiszolgáló folyamatok a legmagasabb prioritással futnak az ilyen rendszerekben.
64. sor: 42. sor:
## '''Az általános célú operációs rendszerek (Windows, UNIX) nem alkalmazhatók kemény valós idejű rendszerekben.'''
## '''Az általános célú operációs rendszerek (Windows, UNIX) nem alkalmazhatók kemény valós idejű rendszerekben.'''
## A fentiek közül egyik állítás sem igaz.
## A fentiek közül egyik állítás sem igaz.
...
==SzoftTech (LZ-féle)==
...
==SzoftTech (tervezési mintás)==
# 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)
# Milyen általános problémát old meg a Factory Method (Metódusgyár) tervezési minta? (2p)
# Rajzolja fel általánosságban vagy egy példára vonatkozóan a Factory Method (Metódusgyár) minta osztálydiagramját! (2p)
# 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)
# Hasonlítsa össze a kliens és kiszolgáló oldali szkript szerepét a webalkalmazásokra vonatkozóan! (2p)


==Adatbázisok==
==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<br/>
#* R1(A,B,C) F1(AB->C) => BCNF <br/>
#* 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 tároláshoz.
#* ha 4 blokkelérés kell, és a hashtábla kiolvasása nem számit 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


===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)===
-- [[MolnarMarton|molnarm]] - 2010.12.29.
 
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ó).
 
===*TODO* sémafelbontás (2p)===
 
=== 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<br/>
R1(A,B,C) F1(AB->C) => BCNF <br/>
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)===
 
{| border="1"
|*T1*:10||*T2*:20||&nbsp;||&nbsp;
|-
| Read A ||&nbsp;||&nbsp;||&nbsp;
|-
|&nbsp;|| Read A ||&nbsp;||&nbsp;
|-
|&nbsp;|| Write B  ||&nbsp;||&nbsp;
|-
| Read B ||&nbsp;||&nbsp;||&nbsp;
|-
| Write A ||&nbsp;||&nbsp;||&nbsp;
|}
 
 
 
 


-- [[MolnarMarton|molnarm]] - 2010.12.29.
-- [[IllesJanos|ijanos]] - 2010.12.31.
-- [[IllesJanos|ijanos]] - 2010.12.31.


[[Category:Infoalap]]
[[Category:Infoalap]]
A lap eredeti címe: „https://vik.wiki/Infó_MSc_felvételi_2010._január_4.”