Nemes Tihamér OKSzTV'99

1. feladat: Időszerű (15 pont)

Az alábbi algoritmus két rendezett állomány (A és B) elemeiből állít elő egy újabb rendezett állományt (C). A B állomány minden egyes rekordja egy-egy parancs, amelyet az A állományon kell végrehajtani. A parancsok háromfélék lehetnek:
 

törlés:	az A állomány adott kulcsú rekordját ne rakd be a C állományba!
javítás:	az A adott kulcsú rekordja helyett a B-beli rekordot rakd be a C-be!
beszúrás:	a parancsban megadott B-beli rekordot rakd be a C-be!

A két állomány rekordstruktúrája:
 

A=Rekord(kulcs:Szöveg, egyéb:Szöveg)

B=Rekord(fajta: (beszúrás, törlés, javítás), kulcs:Szöveg, egyéb:Szöveg)

A B-beli parancsokat az alábbi Időszerűsítés eljárás hajtja végre (a Vége(f)) függvény  IGAZ értékű, ha az f állományból az utolsó olvasás sikertelen volt.
 

Időszerűsítés(A,B,C):   Olvas(A,X): Olvas(B,Y)   Ciklus amíg nem Véga(A) és nem Vége(B)     Ha X.kulcs<Y.kulcs akkor Ír(C,X): Olvas(A,X)     különben ha X.kulcs=Y.kulcs akkor Valami1              különben Valami2   Ciklus vége Eljárás vége

Valami1:   Ha Y.fajta=javítás akkor     X.egyéb:=Y.egyéb: Ír(C,X)     Olvas(A,X); Olvas(B,Y)   Elágazás vége Eljárás vége

Valami2:   Ír(C,(Y.kulcs, Y.egyéb)): Olvas(B,Y) Eljárás vége

Feltehetjük, hogy az A és a B állomány mindig helyes: rendezett és nincsenek benne ismétlődő kulcsú rekordok. Ismétlődő kulcsú rekordok a C állományba sem írhatók.

A.  Egy bizonyos esetben a fenti algoritmus akkor is hibásan működik, ha a B állományban csupa helyes parancs van.

A1. Milyen esetben?

A2. Mi a rossz az eredményben?

A3. Fogalmazd meg, mit kell tenni, azaz hogyan lehet kijavítani a hibát!

B. Milyen hibás, a definíciónak nem megfelelő parancsok lehetnek a B állományban?

Egy családfa az első gyereket a szülőtől balra, a többi gyereket az első gyerektől jobbra ábrázolja. A családfán a következő műveleteket értelmezzük.
 

Balra(f):	az f-nek az a részcsaládfája, amelynek gyökéreleme az f gyökérelemének első gyereke;
Jobbra(f):	az f-nek az a részcsaládfája, amelynek gyökéreleme az f gyökérelemének első testvére
Siker:	igaz, ha a fenti két művelet közül a legutóbb végrehajtott sikeresen ért véget.



Példa: a legfiatalabb olyan elsőszülött, akinek minden őse elsőszülött
 

Elsőszülött(f):   Ciklus     g:=f: f:=Balra(f)   amíg Siker   Ciklus vége   Elsőszülött:=g Eljárás vége

A. Mi az eredménye az alábbi algoritmusoknak?
 

A1.	A2.
Egyik(f):   f:=Balra(f): db:=0   Ciklus amíg siker     f:=Jobbra(f):     db:=db+1   Ciklus vége   Egyik:=db Eljárás vége	Másik(f):   g:=Balra(f)   Ha Siker   akkor db:=Masik(g)   különben db:=1   f:=Jobbra(f)   Ciklus amíg Siker     db:=db+Másik(f)     f:=Jobbra(f)   Ciklus vége   Másik:=db Eljárás vége

B. Írj olyan algoritmust, amely meghatározza a családfa gyökérelemében ábrázolt szülő legkisebb gyerekét! (Feltesszük, hogy van gyereke.)
 

Az alábbi, PROLOG-szerű nyelven felírt tények azt írják le, hogy ki mikor született:
 
Született("Éva", 1959).
Született("András", 1943).
Született("Anna", 1959).
Született("István", 1961).


Azt, hogy X és Y ugyanabban az évbenszülett, így írhatjuk le:
 

Egyidősek(X,Y) ha Született(X,E) és Született(Y,E) és X<>Y.


(A fenti tényállítások alapján Egyidősek(X,Y) teljesül, és az egyik lehetséges válasz: X=Éva, Y=Anna.)

Mit ír le az alábbi öt szabály, azaz milyen paraméterekre teljesülnek, továbbá mi lesz az értéke X-nek, illetve Y-nak a fenti tényállítások mellett? (Az A., B. és C. részfeladatok függetlenek egymástól.)

A.

MilyenA(X) ha Született(X,E) és Született(Y,F) és E<F.
B.
MilyenB(X) ha Született(X,E) és nem(Valami(E)).
Valami(E) ha Született(X,F) és E>F.
C.
MilyenC(X,Y) ha Született(X,E) és Született(Y,F) és X<>Y és nem (Ilyen(abs(E-F))).
Ilyen(G) ha Született(P,A) és Született(Q,B) és abs(A-B)<G.

Az alábbi algoritmusok 16 bites, előjel nélküli egész számokal bitenkénti műveleteket végeznek. A XOR  kizáró vagy művelet, az SHL bitenkénti balra tolás, jobbról 0 jön be, a legértékesebb bit elveszik.
 

Mitcsinál(A,B):   Ciklus amíg B<>0     A:=A XOR B     B:=SHL((A XOR B) AND B)   Ciklus vége   Mitcsinál:=A Függvény vége.

Találdki(A,B):   Ciklus amíg B<>0     A:=A XOR B     B:=SHL((NOT(A XOR B)) AND B)   Ciklus vége   Találdki:=A Függvény vége.

A. Mi a két függvény feladat?
B. Mi a B változó szerepe a ciklus belsejében?
C. Maximum hányszor hajtja végre a ciklus magját a két függvényeljárás?

Egy K szintű megszakítási rendszerben a magasabb szintű megszakításkérés megszakítja az alacsonyabb szintű kiszolgálását, az éppen kiszolgáltnál (az aktuálisnál) nem magasabb szintű megszakításkéréseknek várakozniuk kell. (A megszakítási szinteket természetes számokkal kódoljuk, a legalacsonyabb szint az 1-es.) Mindegyik szinthez egy-egy várakozósor (SOR) amelyben a még fel nem dolgozott megszakításkérések legfontosabb adatait tároljuk. Feltesszük, hogy minden megszakításkérés kiszolgálása azonos ideig, pontosan 10 időegységig tart.

A megszakítás-kiszolgáló olyan objektum, amelynek AKT nevű mezőjében a legutóbb kiszolgált szintjét tároljuk, a következő három eljárást képes végrehajtani.
 

Init: [végrehajtandó a rendszer indításakor]   AKT:=K : VAN:=hamis Eljárás vége.

Megszakításkérés (P, Név): [végrehajtandó megszakításkéréskor]   R.NÉV:=NÉV : R.IDŐ:=0 : Sorba(P,R)   VAN:=igaz Eljárás vége.

Kiszolgálás: [végrehajtandó VAN=igaz esetén]   Ciklus amíg AKT>=1 és ÜRES(AKT)     AKT:=AKT-1   Ciklus vége   Ki: Első(AKT).NÉV   R:=Első(AKT) : R.IDŐ:=R.IDŐ+1 : ElsőtMódosít(AKT,R) Eljrárás vége.

A Sorba(P,R) eljárás a P szintű megszakításkérést leíró (NÉV és IDŐ mezőkből álló) rekordot bejegyzi a P megszakítási szint várakozási sorának végére. A Sorból(P) eljárás törli a P szint várakozósorából a soron következő megszakításkérést. Az Első(P) függvényeljárás egy rekordot ad eredményül: a P szint várakozósorában tárolt megszakításkérések közül az elsőt leíró rekordot. Az Elsőtmódosít(P,R) eljárás a P szint várakozósorában levő első rekordot írja fölül az R rekorddal. Az Üres(P) függvényeljárás igaz eredményt ad, ha a P szint várakozósorában már nincs több kiszolgálásra váró megszakításkérés.

Milyen hibák vannak a Megszakításkérés és a Kiszolgálás eljárásban, s hogyan lehet ezeket kijavítani?

Az U változó értéke akkor lesz igaz az alábbi algoritmusban, ha az MI[1..M] minta előfordul az S[1..N] szövegben. A karaktereket 1-től 255-ig kódoljuk. Különleges jelentése van a 0 kódú karakternek.
 

Kereső:   Ciklus J=0-tól 255-ig     SH(J):=M+1   Ciklus vége   Ciklus J=1-től M-ig     SH(MI(J)):=M+1-J   Ciklus vége   K:=0 : L:=1 : S(N+1):=0   Ciklus amíg K<M és L<=N-M+1     Ha S(K+L)=MI(K+1) akkor K:=K+1                       különben L:=L+SH(S(L+M)) : K:=0   Ciklus vége   U:=(K=M) Eljárás vége.

A. Mi van az SH vektorban a második ciklus lefutása után?

B. Rögzített N és M, továbbá a mintát nem tartalmazó szöveg esetén milyen mintára és rögzített szövegre minimális a harmadik ciklus lépésszáma? Mennyi ez a lépésszám?

C. Rögzített N és M, továbbá a mintát nem tartalmazó szöveg esetén milyen mintára és szövegre maximális a harmadik ciklus lépésszáma? Mennyi ez a lépésszám?

Elérhető összpontszám: 100 pont