Nemes Tihamér OKSzTV 2001

1. feladat: Gráf (20 pont)

Egy irányított gráfot sorszámozott pontokkal és azokat összekötő élekkel adunk meg. A gráfot egy G mátrix írja le, amelyben G(i,j)=1, ha az i-edik pontból vezet él a j-edik pontba, s G(i,j)=0, ha nem. Az alábbi algoritmus egy N pontból álló gráf pontjainak tulajdonságait vizsgálja:
 

Algoritmus:   i:=1; j:=N; k:=1   Ciklus amíg i<>j     Ha G(i,j)=1       akkor j:=j-1       {*}       különben i:=i+1    {**}   Ciklus vége   Ciklus amíg k<=N és (G(i,k)=1 és G(k,i)=0 vagy i=k)     k:=k+1   Ciklus vége   Ha k>N akkor s:=i      {***} Eljárás vége.

A. Milyen tulajdonságú pontok esetén hajtódik végre a {*}-gal jelölt utasítás?
B. Milyen tulajdonságú pontok esetén hajtódik végre a {**}-gal jelölt utasítás?
C. Milyen tulajdonságú pontok esetén hajtódik végre a {***}-gal jelölt utasítás?
D. Lehetséges-e, hogy egy gráfban több olyan tulajdonságú pont is van, mint aminek a sorszámát a {***}-gal jelölt utasításban megadjuk? Magyarázd meg, miért!

Egy lemezegységen az adatok N sávban helyezkednek el, a legkülső sáv sorszáma 1. A lemezvezérlő egy adatot 1 időegység alatt képes leolvasni az aktuális sávból. Az i-edik sávból a j-edik sávba való lépéshez ?i-j?+K időre van szüksége.

A fejlesztők rájöttek, hogy nem gazdaságos az olvasási kérelmeket beérkezésük sor-rendjében teljesíteni. Ha például az olvasó fej az 1. sávban áll és jön egy olvasáskérés az N. sávra, akkor a vezérlő elindítja az olvasófejet befelé. Ha közben jön egy olvasáskérés az N/2-edik sávra, akkor érdemesebb lenne ott megállni, beolvasni az ott levő adatot, majd továbbmenni az N-edik sávra.

Az alábbi algoritmusok feltételezik, hogy a T tömb i-edik eleme tartalmazza, hogy pillanatnyilag hány olvasáskérés van az i-edik sávra. A T tömböt kívülről tölti fel a megfelelő időpontban egy megszakítás-kezelő eljárás.
 

Algoritmus:   i:=1; ir:=1   Ciklus ...    Ha van olvasáskérés akkor      Következő-*(i,j,ir)      Mozgatás(i,j)      i:=j; T(i):=0    Elágazás vége   Ciklus vége Eljárás vége

Következő-A(i,j,ir):   j1:=i; j2:=i   Ciklus amíg T(j1)=0 és T(j2)=0     Ha j1>1 akkor j1:=j1-1     Ha j2<N akkor j2:=j2+1   Ciklus vége   Ha T(j1)>0 akkor j:=j1           különben j:=j2 Eljárás vége.

Következő-B(i,j,ir):   j:=i   Ciklus amíg T(j)=0     Ha j=1 akkor ir:=1     Ha j=N akkor ir:=-1     j:=j+ir   Ciklus vége Eljárás vége.

Következő-C(i,j,ir):   j:=i   Ciklus amíg T(j)=0     Ha j=N akkor j:=1         különben j:=j+1   Ciklus vége Eljárás vége.

A. Mi a stratégiája a három Következő-* eljárásnak?
B. Fogalmazd meg, milyen olvasáskéréssel kell a legtovább várni az egyes algoritmusok esetén!
C. Fogalmazd meg, milyen (nem az aktuális sávra vonatkozó) olvasáskéréssel kell a legkevesebbet várni az egyes algoritmusok esetén!

Tekintsük az alábbi F1 és F2 függvényeket, ahol S betűket tartalmazó sorozat.
 

Függvény F1(i, j):  Ha i>j akkor F1:=0  Egyébként     ha i=j akkor F1:=1    Egyébként       ha S[i]=S[j] akkor F1:=2+F1(i+1,j-1)      Egyébként F1:=Maximum(F1(i+1,j),F1(i,j-1))  Elágazás vége Függvény vége.

Függvény F2(i, j):  Ha i>=j akkor F2:=0  Egyébként    ha S[i]=S[j] akkor F2:=F2(i+1,j-1)    Egyébként F2:=1+Minimum(F2(i+1,j), F2(i,j-1))  Elágazás vége Függvény vége.

A. Mi az értéke az F1(1,10) függvényhívásnak, ha S='elvermelve' ?
B. Mit számít ki az F1(1,N) függvényhívás, ha S pontosan N betűből áll?
C. Mi az értéke az F2(1,10) függvényhívásnak, ha S='elvermelve' ?
D. Mit számít ki az F2(1,N) függvényhívás, ha S pontosan N betűből áll?

Egy autó parkolóban N darab autó parkol egymás mellett. Az autókat érkezési sor-számokkal azonosítjuk 1-től N-ig. Rendezni kell az autókat úgy, hogy sorszámuk szerint növekvően legyenek a parkolóban. A rendezést három dolgozó végzi a következő eljárás szerint. Egy menetben mindegyik dolgozó legfeljebb egy autót mozgathat, de csak olyan helyre, ahonnan ugyanebben a menetben egy másik autót elvisz egy dolgozó. A cél az, hogy a lehető legkevesebb menetben elvégezzék a rendezést.

Példa:

Ha 6 autó van, az autók kezdeti sorrendje 3, 4, 1, 5, 6, 2, akkor 3 menet kell.

A. Legkevesebb hány menet kell a rendezéshez, ha 11 autó kezdeti sorrendje: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1

B. Legkevesebb hány menet kell a rendezéshez, ha 20 autó kezdeti sorrendje:

5, 1, 3, 7, 2, 8, 4, 10, 11, 9, 6, 20, 19, 18, 12, 15, 17, 16, 14, 13

C. N autó esetén legrosszabb esetben hány menet kell a rendezéshez?

Csillagászok naponta észlelnek két távoli égitestről érkező jelsorozatokat. Minden jelsorozat egy bitsorozattal azonosítható, és az alábbi szabályokkal jellemezhető.

Az A égitest esetén:

A1. Az egyetlen 0-t tartalmazó jelsorozat észlelt.
A2. Ha <alfa> észlelt, akkor az <alfa>0 és <alfa>10 is észlelt.
A3. Minden észlelt jelsorozat megkapható az A1. és A2. szabályok véges sokszori alkalmazásával.


A B égitest esetén:

B1. Az egyetlen 0-t és egyetlen 1-et tartalmazó jelsorozat észlelt.
B2. Ha <beta> észlelt, akkor a 0<beta>0 és az 1<beta>1 is észlelt.
B3. Minden észlelt jelsorozat megkapható az B1. és B2. szabályok véges sokszori alkalmazásával.


Melyek azok a jelsorozatok, amelyek mindkét égitestről származhatnak? Add meg a jelsorozatok szabályait.

Elérhető összpontszám: 100 pont