Nemes Tihamér OKSzTV'99

1. feladat: Halmazok metszete (16 pont)

Az alábbi algoritmus két halmaz metszetét határozza meg. A két halmazt az N elemszámú A és az M elemszámú B tömbben tároljuk.
 

Metszet:   K:=0   Cilus I=1-től N-ig     J:=1     Ciklus amíg J<=M és A(I)<>B(J)       J:=J+1                             (*)     Ciklus vége     Ha J<=M akkor K:=K+1 : C(K):=A(I)   Ciklus vége Eljárás vége

A.  Adott N és M esetén (N<=M) milyen adatokra a leggyorsabb az algoritmus, azaz a (*)-gal jelölt sort milyen A és B vektorokra hajtja végre a legkevesebbszer? A (*)-gal jelölt sort ebben az esetben hányszor hajtja végre?

B.  Adott N és M esetén (N<=M) milyen adatokra a leglassúbb az algoritmus, azaz a (*)-gal jelölt sort milyen A és B vektorra hajtja végre a legtöbbször? A (*)-gal jelölt sort ebben az esetben hányszor hajtja végre?

Az alábbi algoritmus a képernyő pontjait festi ki az (I,J) pontból kiindulva, a DB tömb feltöltésétől függő sorrendben.
 

Fest(I,J):   K:=1 : L:=1   Ciklus amíg KépernyőnBelül(I,J)     Pontrajzolás(I,J)     I:=I+T(L,1) : J:=J+T(L,2) : DB(K):=DB(K)-1     Ha DB(K)=0 akkor K:=K+1 : L:=L mod 4+1   Ciklus vége Eljárás vége

A Képernyőnbelül(I,J) függvényeljárás igaz értéket ad eredményül, ha az (I,J) pont a képernyőn belül van. A Pontrajzolás(I,J) eljárás kivilágítja az (I,J) pontot.

A négyszer két elemű T tömbelemeinek tartalma:
T(1,1)=0, T(1,2)=1, T(2,1)=-1, T(2,2)=0, T(3,1)=0, T(3,2)=-1, T(4,1)=1, T(4,2)=0

Milyen sorrendben festi ki az algoritmus az ábrán látható terület pontjait, ha a DB vektort az alábbiak szerint töltjük ki? Másold le az ábrát 3-szor, és írd bele a további lépések sorszámát!
 

	J (jobbra nő)
I le nő
				3
			1	2

A. DB=1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ...
B. DB=1, 2, 3, 4, 5, 6, ...
C. DB=1, 2, 2, 3, 4, 4, 5, 6, ...

Az alábbi algoritmus két rendezett vektor (A, B) elemeiből állít elő egy újabb rendezett vektort, amelyben azok az elemek szerepelnek, amelyek legalább az egyikben előfordulnak. Az eredmény minden elemének különbözőnek kell lennie.
 

Összefuttatás(A, N, B, M, C, K):   I:=1 : J:=1 : K:=0   Ciklus amíg I<=N és J<=M     K:=K+1     Ha A(I)<B(J) akkor C(K):=A(I) : I:=I+1     különben Ha A(I)=B(J) akkor (C(K):=A(I) : I:=I+1 : J:=J+1           különben C(K):=B(J) : J:=J+1   Ciklus vége Eljárás vége

A. Milyen feltételeknek kell teljesülniük A-ra és B-re az eljárás működéséhez?
B. Milyen hibát okoz az eredményben, ha ezek a feltételek nem teljesülnek?

A kiskapus sor olyan adatszerkezet, amelyen háromféle műveletet lehet végrehajtani:
SORBA a BE bemenetre érkező jelet beteszi a sor végére,
SORBÓL kirakja a következő jelet a sor elejéről a KI kimenetre,
ÁT pedig átengedi a BE bemenetre érkező jelet a KI kimenetre.

A kiskapus sort illusztrálja az ábra.



Feltesszük, hogy a BE bemenetre az 1, 2, 3, 4, 5 jelsorozat érkezik.

Példa
Az 5, 1, 2, 3, 4 sorozat előállítható a SORBA, SORBA, SORBA, SORBA, ÁT, SORBÓL, SORBÓL, SORBÓL, SORBÓL műveletsorozattal.

A. Elő lehet-e állítani az alábbi sorozatokat? Amelyiket nem, azt meddig lehet? Amelyiket igen, azt hogyan lehet minimális számú művelettel előállítani?

A1. 3, 1, 4, 2, 5 A2. 2, 4, 3, 1, 5 A3. 5, 1, 2, 4, 3 A4. 2, 3, 1, 5, 4 B. Fogalmazd meg, hogy milyen sorrendű lehet az eredménysorozat?

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 viszont 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) tartozik, 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áskiszolgáló olyan objektum, amelynek AKT nevű mezőjében a legutóbb kiszolgált megszakítás szintjét tároljuk, s 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ó megszkí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) Eljá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ó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 javítani?