Nemes Tihamér OKSzTV'93

1. feladat: Biokertészet (13 pont)

A következő PROLOG program a biokertészeket segíti: a növényekről beletáplált tudás alapján eldönti, hogy egyes vethető növeényeket milyen sorrendben ültessenek egymás mellé, ha mindegyikből egy-egy sort szeretnének. Ha lehet, olyan növeényeket kell egymás mellé ültetni, amelyek védik egymást. Ha ez nem megy, akkor olyanokat, amelyek szeretik egymást, és ha ez sem lehetséges, akkor olyanokat, amelyek legalább nem ellenségei egymásnak.

Gyomnövények:

gyom(pipacs). gyom(csalán).
Vethető növények:
vethető(karalábé). vethető(hagyma). vethető(bab.) vethető(paradicsom). vethető(retek).
A vethető növények közötti kapcsolatok:
védi(hagyma, paradicsom). védi(paradicsom, hagyma). védi(paradicsom, karalábé). védi(karalábé, paradicsom).
szereti(paradicsom, bab). szereti(bab, paradicsom). szereti(karalábé, bab). szereti (bab, karalábé). szereti(retek, bab). szereti(bab, retek).
ellenség(hagyma, karalábé). ellenség(karalábé, hagyma). ellenség(karalábé, retek). ellenség(retek, karalábé). ellenség(hagyma, bab). ellenség(bab, hagyma). ellenség(hagyma, retek). ellenség(retek, hagyma).
Egy lehetséges vetési sorrendet megadó program:
 

vetés(A, B, C, D, E) ha    szomszéd(A, B) és    szomszéd(B, C) és    A<>C és    szomszéd(C, D) és    A<>D és    B<>D és    szomszéd(D, E) és    A<>E és    B<>E és    C<>E.

 
A szomszéd(A, B) formula igaz értéket ad eredményül, ha talál olyan A és B, egymástól különböző, vethető növényeket, hogy A és B védik vagy szeretik egymást, vagy legalább nem ellenségei egymásnak. Ezután kerül sor a szomszéd(B, C) formulára, amely az előbb kapott B-hez egy új C-t keres, és így tovább. Ha az adott B-hez nincsen olyan C, amelyre a szomszéd(B, C) formula igaz lenne, akkor a PROLOG rendszer az előző szomszéd(A, B) formulát újra kiértékelve előállít egy másik A, B párt, és a kiértékelést folytatja a szomszéd(B, C) formulával.

a) Írd fel a szomszéd(X, Y) formulát (felhasználható műveletek: és, vagy, nem)!

b) Add meg, hogy a fenti tudás alapján a felsorolt növények milyen sorrendben vethetők!

2. feladat: Sorozatok (16 pont)

Egy programnyelv sorozatokra a következő függvényeljárásokat definiálja (pl. a STRING típust tekinthetjük karakterek sorozatának):

a) Mit csinál a következő két függvényeljárás?
 

példa1(S) : első(elsőutániak(S)).

példa2(E, S):    Ha ürese(S) akkor HAMIS    különben Ha E=első(S) akkor IGAZ             különben példa2(E, elsőutániak(S)).

 
b) Az első elsőutániak, elejére, ürese és üres függvényeljárások felhasználásával írd meg rekurzív függvényeljárásként az alábbiakat:

3. feladat: Táblázatkezelő (9 pont)

Egy táblázatkezelő programról a következőket kell tudni:

• úgynevezett cellákból áll, amelyek sorokba és oszlopokba vannak rendezve;
• a sorokat egész számok, az oszlopokat betűk azonosítják (1-től, illetve A-tól kezdve);
• minden cellába egyetlen dolog írható: vagy egy képlet, vagy egy szám;
• képletekben hivatkozni lehet bármely cellára - saját cellára is;
• cellára hivetkozni a cella oszlop- és sorazonosítójával lehet, például A1, Q55;
• a cellák értékét A1 A2 A3 ... B1 B2 B3 ... sorrendben számolja ki.
Adva van a következő program: 

A1	0	B1	Ha sgn(A6)=sgn(A4) akkor A3 különben A1	C1	...
A2	9	B2	Ha sgn(A6)=sgn(A5) akkor A3 különben A2	C2	...
A3	(A1+A2)/2	B3	(B1+B2)/2	C3	...
A4	+A1*A1-4	B4	+B1*B1-4	C4	...
A5	+A2*A2-4	B5	+B2*B2-4	C5	...
A6	+A3*A3-4	B6	+B3*B3-4	C6	...

 A további (C, D stb.) oszlopokba írt képletek értelemszerűen a B-beliek módosításával kaphatók meg; a C-beliek például úgy, hogy a B-k helyébe C-t, az A-k helyébe B-t írunk.

a) Mit számol ki ez a program?

b) Közelítőleg milyen értéket kapunk J3-ban?

4. feladat: Számvektorok (15 pont)

A következő algoritmus számvektorokban (egydimenziós tömbökben) tárolt egész számok szoroz össze. A szorzandók az A() és a B(), 0-tól N-ig, illetve M-ig indexelt vektorokban vannak (N>=M), az eredményt a C() 0-tól K-ig indexelt vektorba kell tenni, a lehető legkevesebb művelet felhasználásával. Például az A() vektorban tárolt szám így értelmezendő:
a₀+a₁*10+a₂*10²+ ... +a_n*10ⁿ, ahol a_n<>0.
Egészítsd ki az algoritmust a ?x?-lel megjelölt helyeken! (A közölt részletek elhagyása esetén nem jár pont.)
 

Szoroz(N, A, M, B, K, C):   ÁTVITEL:=?1?   Ciklus I=0-tól ?2?-ig     C(I):=ÁTVITEL     Ciklus J=max(0, I-M)től ?3?-ig       C(I):=C(I)+A(J)*B(I-J)     Ciklus vége     ÁTVITEL:=?4?     C(I):=?5?   Ciklus vége   Ha ?6? akkor K:=N+M+1 : C(K):=?7?          különben K:=N+M Eljárás vége.

5. feladat: Csak formálisan (17 pont)

Egy nyelv formális leírására az alábbi szabályokat adjuk meg. A definiálandó fogalmakat <>-ek közé tettük, ::= vezeti be a definíciót, a | (vonás) vagy kapcsolatot jelöl, a {}-ek közé zártak ismétlődését jelentik legalább egyszer, a ... (3 pont) pedig a sorozat folytatására utal.

<mondat>::={<elem>{<szóköz>}}.

Jelentése: a mondat elemek legalább egytagú sorozata, minden elem után legalább egy szóköz áll, és a mondatot pont zárja.
<elem>::=<szó>|<szám>|<írásjel>
Jelentése: az elem szó vagy szám vagy írásjel.
<szó>::={<betű>}
Jelentése: a szó egy betűsorozat, amely legalább egy betűből áll.
<szám>::={<számjegy>}
<írásjel>::=,|;
<betű>::=a|b|...|z
<számjegy>::=0|1|...|9

a) A fenti szabályok szerint hol és miért hibás ez a mondat:

ez egy ,; 8szavas mondat : szava ez, de a -1 nem .
b) Módosítsd úgy a definíciót, hogy számnak lehessen előjele, és fixpontos valós alakban is fel lehessen írni (például +12.34)!

c) Egészítsd ki az alábbi programot a hiányzó Szóolvasás, Számolvasás, Írásjelolvasás eljárásokkal úgy, hogy a definíció szerint helyes mondatot elemekre bontson!
 

Elemző(P):   i:=1   Ciklus amíg i<=hossz(P)     Elágazás       P(i) Betű esetén Szóolvasás(P, i, SZO)                        Ki:SZO       P(i) Számjegy esetén Számolvasás(P, i, SZA)                            Ki: SZA       P(i) Írásjel esetén Írásjelolvasás(P, i, IR)                           Ki: IR       P(i)=Szóköz esetén i:=i+1     Elágazás vége   Ciklus vége Eljárás vége.

6. feladat: Turing-gép (12 pont)

A Turing-gép egy szalagból és egy író-olvasó fejből áll. A fej olvasás közben jobbra-balra mozoghat a szalagon, ha pedig nem mozog, akkor írhat rá. A szalagra írható, illetve onnan visszaolvasható jelek halmazát ábécének nevezzük.

A gép tetszőleges számú különböző állapotban lehet. A működését leíró program a gép minden lehetséges állapotához megadja, hogy a szalagról beolvasott jeltől függően melyik állapotába kerüljön, és a fej mit csináljon. A fejnek a következő parancsok adhatók: Jobbra lép (J) Balra lép (B), Jelet ír (jel). Ha valamelyik állapotban a beolvasott jelhez nincs parancs megadva, a gép megáll.

Például ábécé: {0, 1, 2}

Feltéve, hogy kezdetben a q1 állapotban van, e program (szabályhalmaz) hatására a gép a fej kezdeti pozíciójától jobbra eső összes 1-et átírja 2-vé, amíg csak 0-t nem talál és akkor megáll.

Tegyük fel, hogy a nemnegatív egész számokat a következőképpen ábrázoljuk:

0:1, 1:11, 2:111, ..., 12:1111111111111 stb., két ilyen számot pedig *-gal választunk el egymástól, például 11111*11.
Gépünk a q1 állapotban indul, a fej balról az első 1-en áll, és a szalagon két szám van, egymástól *-gal elválasztva:
...00011111*111111111000...
A szalag fenti tartalma mellett a gép a következő programot hajtja végre:
ábécé: {0, 1, *}
q1:1 -> q1:J
q1:* -> q2:1
q2:1 -> q2:J
q2:0 -> q3:B
q3:1 -> q3:0
q3:0 -> q4:B
q4:1 -> q4:0
Válaszolj az alábbi kérdésekre:
a) Mi a fenti program végrehajtásának eredménye a megadott számokkal?

b) Hol áll a fej a program befejeződése után?

c) Mi a program eredménye két tetszőleges nemnegatív egész szám esetén?

d) Mi az eredmény akkor, ha a szalagon kezdetben nem két, hanem csak egy nemnegatív szám van, például ...0011111100...? Hol áll most a fej a program befejeződése után?

7. feladat: Assembly (12 pont)

Assembly programot írtunk morzejelek vételére. A morzejeleket ember adja, így az egyes jelek és szünetek időtartama kis mértékben változhat. Ha a morzejel-bemeneten jelet érzékelünk, csupa 1-et tartalmazó byte-ot olvasunk be, ellenkező esetben csupa 0-t Feltesszük, hogy a regiszterek nem csordulnak túl. Az alábbi programrészlet alapján válaszolj a kérdésekre!
 

XOR BX,BX        ;BX:=BX XOR BX (bitenkénti kizáró 'vagy') C1: INC BX           ;BX növelése 1-gyel     IN AL,morzeport  ;1 byte beolvasása a morzejel-bemenetről     OR AL,AL         ;AL:=AL OR AL     JNZ C1           ;ugrás, ha az előző művelet eredménye nem 0     MOV AX,P         ;az AX regiszterbe tölti a P változó értékét     MOV CX,Q     SUB AX,BX        ;AX:=AX-BX     NEG AX           ;AX:=-AX     SUB CX,BX     JS C2            ;ugrás, ha az előző művelet eredménye negatív     CMP AX,CX        ;összehasonlítás     JG C2            ;ugrás, ha az előző műveletben AX>CX     MOV P,BX     MOV DL,0     JMP C3           ;ugrás C3-ra C2: MOV Q,BX     MOV DL,1 C3:

a) Hogyan különbözteti meg egymástól a vevő a rövid és a hosszú jeleket?

b) Mire szolgál a C1 címkénél kezdődő ciklus?

c) Mi a program eredménye, és hol keletkezik?

d) Milyen esemény bekövetkezése esetén kerül sor a JS C2, illetve a JG C2 ugrásokra?

e) Hogyan változnak a P és Q változók?

8. feladat: Monoton (6 pont)

a) Mi van h-ban az alábbi programrészlet végrehajtása után, ha a b[1..n] tömb elemei monoton növekvő sorozatot alkotnak?
 

VAR i,j,h: INTEGER; BEGIN   i:=1; h:=1;   WHILE i<n DO     BEGIN       j:=i+1;       WHILE (j<=n) AND (b[i]=b[j]) DO j:=j+1;       IF (h<j-i) THEN h:=j-i;       i:=i+1     END END.

b) Írj a fentivel azonos eredményt adó programot, amely csak két változót használ (például i-t és h-t), és csak egyszer pásztáz végig a tömbön!

Elérhető összpontszám: 100 pont