Løsninger til udvalgte eksamensopgaver udleveret i forbindelse med S&L-kurset 2000

Her følger i en noget komprimeret form udvalgte eksamensopgaver med besvarelser. Bemærk, at opgaverne er stillet i forbindelse med tidligere kurser (nogle for meget længe siden), og de må ikke opfattes som typiske eksamensopgaver. Besvarelserne er ikke udformet som idealbesvarelser, men rummer kun det tekniske indhold.

Der skal gives et enkelt råd om eksamensbesvarelser. Begrund din løsning, specielt hvis du er usikker på at den nu er helt rigtig: Det kan være meget svært for bedømmerne at give point for en forkert løsning uden begrundelse, men hvis ræsonnementet, der er leder frem til løsningen er skrevet ned, er stor set rigtigt, ku' der måske falde lidt af alligevel... Læg også mærke til, om der eksplicit bedes om begrundelse i opgaveformuleringen.

Slutteligen gør jeg opmærksom på, at det er redigeret sammen hurtigt, og at HTML-versionen er produceret ved ªSave as HTML´ fra Word (med de allernødvendigste tilpasninger), så, øh... Syntaksdiagrammer er ikke lavet med tegneprogrammer, men vha. ªskrivemaskinegrafik´, så måske I skal gætte lidt, hvordan pilene skal vende o.lign.

Sommer 1987, Opgave 4

Denne opgave drejer sig om strukturer og lister i Prolog. Det gennemgående eksempel i opgaven har at gøre med bøger, biblioteker og litteratursøgning.

En bog er angivet ved en struktur beskrevet som følger:

bog( forfatter, titel, antal-sider, type)

Her er to eksempler på bøger:

bog( bratko, prolog, 423, faglitteratur)
bog( dumas, de_3_musketerer, 777, underholdning)

Et bibliotek er angivet som en liste af bøger, f.eks.:

[ bog( sayers, de_9_klokkeslag, 288, krimi),

bog( bratko, prolog, 423, faglitteratur),

bog( tanenbaum, structured_osv, 465, faglitteratur),

bog( lang, intrigernes_hus, 192, krimi),

bog( dumas, de_3_musketerer, 777, underholdning)

]

Spørgsmål 1

 Forklar i ord, hvad det vil sige, at et givet bibliotek tilfredsstiller prædikatet p defineret som følger:

p( [ bog( rifbjerg, _, _, _) | _]).

p( [_|Rest] ) :- p(Rest).

Løsning: At p holder, betyder, at der mindst en bog af Rifbjerg i argumentet – mere præcist, at argumentet er en liste, og at ét af elementerne svarer til en bog af Rifbjerg.

Eksempel på forespørgsel:

:- eksempel_bogliste(B),p(B)

no

Overvej iøvrigt forespørgsel p(X) . . .

:- p(X)

Nº1 X = [bog(rifbjerg, _1172, _1173, _1174)|_1168]

Spørgsmål 2

Definer et prædikat i Prolog, som, givet et bibliotek, finder en liste af alle bibliotekets titler. Prædikatet skal have følgende form:

titler( bibliotek, liset-af-titler)

Besvarelse:

titler([], []).

titler( [ bog( _, Titel, _, _) | Mere], [Titel | FlereTitler]):-

titler( Mere, FlereTitler).

 

Eksempel på forespørgsel:

 

:- eksempel_bogliste(B),titler(B, T)

Nº1 B = [bog(sayers .....],

T = [de_9_klokkeslag, prolog, structured_osv,

intrigernes_hus, de_3_musketerer]

Spørgsmål 3

 Definer et prædikat i Prolog som, givet et bibliotek, finder en liste af alle kriminalromaner, dvs. alle bøger hvis type er krimi. Prædikatet skal have følgende form:

krimier( bibliotek, liste-af-krimier)

Besvarelse:

krimier( [], [] ).

krimier( [ bog( F, T, N, krimi) | Mere],

[ bog( F, T, N, krimi) | FlereKrimier]):-

!,

krimier( Mere, FlereKrimier).

krimier( [ _ | Mere],

FlereKrimier):-

krimier( Mere, FlereKrimier).

 

Eksempel på forespørgsel:

:- eksempel_bogliste(B),krimier(B, K)

Nº1 B = [bog(sayers .....],

K = [bog(sayers, de_9_klokkeslag, 288, krimi),

bog(lang, intrigernes_hus, 192, krimi)]

Udråbstegnet i anden klausul er vigtigt! Såfremt det ikke var der, ville der kunne genereres flere løsninger, hvor kun den første er rigtig. Overvej hvilke!

Spørgsmål 4

 Til brug i en sommerhusferie ønsker vi at udtage en liste af bøger fra et bibliotek som
- ikke indeholder faglitteratur,
- ikke overstiger 800 sider.
Definer et prædikat i Prolog med følgende form:

ferielæsning( bibliotek, bogliste, antal-sider)

For et givet bibliotek skal prædikatet kunne generere de mulige udtag af ferielitteratur (som beskrevet ovenfor) i form af lister af bøger. prædikatet oplyser yderligere det samlede antal sider i en funden liste.

Løsning:

ferielæsning( [], [], 0).

ferielæsning( [bog( _, _, _, faglitteratur) | Mere],

MereFerie, AntalSider):-

!,

ferielæsning( Mere, MereFerie, AntalSider).

% Bemærk, de to følgende regler ofte begge kan vælges

% for den samme bogliste, så der her kan genereres alternative løsninger.

 

 

 

ferielæsning( [bog( F, T, N, A) | Mere],

[bog( F, T, N, A) | MereFerie],

AntalSider):-

% A er ikke = faglitteratur!

ferielæsning( Mere, MereFerie, FlereAntalSider),

AntalSider is FlereAntalSider + N,

AntalSider =< 800.

ferielæsning( [_ | Mere], MereFerie, AntalSider):-

ferielæsning( Mere, MereFerie, AntalSider).

Betragt følgende forespørgsel, hvor der er bedt om alle svar

?- eksempel_bogliste(B),ferielæsning(B, FL, S)

Nº1 B = [bog(sayers .....],

FL = [bog(sayers, de_9_klokkeslag, 288, krimi),

bog(lang, intrigernes_hus, 192, krimi)],

S = 480

Nº2 B = [bog(sayers .....],

FL = [bog(sayers, de_9_klokkeslag, 288, krimi)],

S = 288

Nº3 B = [bog(sayers .....],

FL = [bog(lang, intrigernes_hus, 192, krimi)],

S = 192

Nº4 B = [bog(sayers .....],

FL = [bog(dumas, de_3_musketerer, 777, underholdning)],

S = 777

Nº5 B = [bog(sayers .....], FL = [], S = 0

No more solutions

 

 

Vinter 1986/87, Opgave 2

Denne opgave drejer sig om Prologs listebegreb og kan løses på baggrund af Bratkos bog.

Opgaven går ud på at analysere kokkunikationen mellem hunde og katte. det antages at hunde råder over ordforrådet vov, vruf, grr, piv og hyl, og katte over mjav, mjaav, hvæs og krads. Det kan beskrives i Prolog ved en række fakta: 

hundelyd( vov).
   .
   .
   .
kattelyd( mjav ).
   .
   .
   .

Spørgsmål 1

 Definer et prædikat, som afgør om en struktur er en liste af hundelyde. f.eks. skal følgende være opfyldt: 
    hundetale( [vov, vov, vov, grr])

Løsning:

hundetale( []).

hundetale( [H | Mere]):-

hundelyd(H),

hundetale( Mere).

Eksempler på forespørgsler

:- eksempel_dialog(D),hundetale(D)

no

:- hundetale([vov, vov])

Nº1 yes

 

Følgende spørgsmål 2 og 3 løses nemmest derekte uden brug af prædikaterne hundetale (spg. 1) og append.

Spørgsmål 2

En dialog mellem hund og kat kan repræsenteres som en liste af hunde- og kattelyde. AF hensyn til en dyrepsykologisk underøgelse ønsker man et prædikat, som kan adskille en dialog mellem hund og kat i to lister, der indeholder hver af de to parters ytringer. Definer et sådant prædikat, adskil, så f.eks. følgende er opfyldt: 
adskil( [mjav, vov, vov, vruf, grr, hvæs, krads, piv, piv],
        [vov, vov, vruf, grr, piv, piv],
        [mjav, hvæs, krads] ).
Løsning:

adskil( [H | Mere], [H | MereH], MereK):-

hundelyd(H),

adskil( Mere, MereH, MereK).

adskil2( [K | Mere], MereH, [K | MereK]):-

kattelyd(K),

adskil( Mere, MereH, MereK).

adskil( [], [], []).

Bemærk, der er ingen udråbstegn i klausulerne. Overvej, hvad effekten af udråbstegn efter hundelyd(H) og kattelyd(K) måtte være. Hint: man ville få samme svar, men . . .

Spørgsmål 3

 Nu viser det sig imidlertidm at dyrespsykologerne ikke er tilfredse med prædikater fra spørgsmål 2: Det fremgør ikke af de to lister. hvornår dialogen skifter, f.eks. hvor sekvensen af hundelyde har været adskilt af kattelyde. Der ønskes derfor en ny udgave af adskil som indsætter et skilletegn, en *, i de to adskilte lister, svarende til et indlæg fra modparten. Der skal f.eks. gælde følgende: 
adskil( [mjav, vov, vov, vruf, grr, hvæs, krads, piv, piv],
        [*, vov, vov, vruf, grr, *,  piv, piv],
        [mjav, *, hvæs, krads, *] ).
Løsning:

Et noget tricket spørgsmål, som sikkert kan løses på mangfoldige måder, og sikkert også mere elegant end det følgende...

adskil( [H1, H2 | Mere], [H1 | MereH], MereK):-

hundelyd(H1),

hundelyd(H2),

adskil( [H2 | Mere], MereH, MereK).

adskil( [H, K | Mere], [H, * | MereH], MereK):-

hundelyd(H),

kattelyd(K),

adskil( [K | Mere], MereH, MereK).

 

 

adskil( [K1, K2 | Mere], MereH, [K1| MereK]):-

kattelyd(K1),

kattelyd(K2),

adskil( [K2 | Mere], MereH, MereK).

adskil( [K, H | Mere], MereH, [K, *| MereK]):-

kattelyd(K1),

hundelyd(K2),

adskil( [H | Mere], MereH, MereK).

adskil( [H], [H], []):-

hundelyd(H).

adskil( [K], [], [K]):-

kattelyd(K).

adskil( [], [], []).

 

(Bemærk, at det ikke er eksakt den løsning, som er ønsket i opgaveteksten!)

Spørgsmål 4

 Dette spørgsmål handler om magtforholdet mellem hunde og katte. Vi siger, at hunden er den sejrende i en dialog, hvis 1) hunden får indført det sidste ord og 2) dette ikke er hyl eææer piv; i modsat fald er katten den sejrende. Definer et prædikat, sejrende, som beskriver dette: første parameter forventes at repræsentere en dialog, anden parameter forventes at angivelse af den sejrende part. Der skal f.eks. gælde følgende: 
sejrende( [mjav, vov, vov, vruf, grr, hvæs, krads, piv, piv], kat).
Løsning:

sejrende( [_, E | L], S):- % læg mærke til liste-mønstret,

!, sejrende( [E | L], S). % som sørger for, at denne regel "stopper"

% når der er netop et element tilbage

% i listen

sejrende([hyl], kat):- !.

sejrende([piv], kat):- !.

sejrende([H], hund):-

hundelyd(H), !.

sejrende(_, kat).

Vinter 2000, Opgave 5 (10% af 4 timer)

Denne opgave drejer sig om oversættelse af imperative sprog og går ud på at udvide eksemplet i ªSprog og abstrakte maskiner´, 2. rev. udgave 1999, afsnit 6.3, som beskriver en oversætter fra while-sproget til Mini-stak-og-variabel-maskinen. Vi er interesseret i at udvide sproget med en særlig løkke-konstruktion, som er en krydsning mellem de traditionelle while- og repeat-løkker. Den adskiller sig fra de to ved at have testet for udhop i midten, og vi repræsenterer abstrakte syntakstræer for konstruktionen ved Prologtermer af formen:

loop_exit(sætning1, betingelse, sætning2)

og betydningen skitseres således: Først udføres sætning1; hvis dernæst betingelsen er opfyldt standser løkker; ellers forsættes med sætning2 og der startes forfra i løkken.

Opgavens eneste spørgsmål lyder som følger. Skriv en oversættelsesregel i Prolog med de hjælpeværktøjer, som er benyttet i afsnit 6.3, således at den kan indgå som en del af den samlede oversætter (som altså bliver en oversætter for et nyt sprog, som indeholder den nye loop_exit-konstruktion samt alle de faciliteter, vi kender fra while-sproget).

Løsning:

sætning(loop_exit(S1,B,S2),K):-

sætning(S1,Ks1),

betingelse(B,Kb),

sætning(S2,Ks2),

ny_etikette(Start1),

ny_etikette(Start2),

ny_etikette(Slut),

K <- Start1 + Ks1

+ Kb

+ n_hop(Start2)

+ hop(Slut)

+ Start2 + Ks2

+ Slut.

 

 

Vinter 2000, Opgave 6 (10 %)

Denne opgave drejer sig om operatordefinitioner i Prolog og kan besvares på baggrund af Bratkos bog. En Prologterm, som indeholder funktorer, der er erklæret som operatorer, kan skrives på flere alternative måder. Med de sædvanlige operatordefinitioner for aritmetiske operatorer er f.eks. de to udtryk 1*2+3*4 og +(*(1,2),*(3,4)) to forskellige skrivermåder for én og samme term i Prolog. Den sidste form, eksemplificeret ved +(*(1,2),*(3,4)), kalder vi her den kanoniske skrivemåde for termen.

Spørgsmål 1

Antag, at følgende operatorer er defineret i et Prologprogram:

:- op( 500, xfx, #).

:- op(500, xfy, @).

:- op( 500,yfx, &).

Hvad er den kanoniske skrivemåde for termen, som også kan skrives således:

a @ b # c & d

Løsning:

Følgende lille test verificerer den korrekte løsning:

| ?- write_canonical(a @ b # c & d).

@(a,&(#(b,c),d))

Den er nem at finde også uden at man har et Prolog system til rådighed, bare man kan tænke så langt som at tegne nogle træer og sætte præcedenstal på. Så finder man hurtigt ud af, at det eneste træ som opfylder betingelserne defineret ved de det X'er og y'er (se Bratko, s. 86-87) er dette:

                        @ 500
                       / \
                      /   \
                   0 a     & 500
                          / \
                         /   \
                    500 #     d 0
                       / \
                      /   \
                   0 b     c 0

Spørgsmål 2

Giv en operatordefinition i Prolog for symbolet ª?´, således at følgende kanoniske form

?(?(#(a,b),#(c,d)),#(e,f))

kan skrives alternativt sådan her:

a#b ? c#d ? e#f

Vi antager definitionen for ª#´ fra spg. 1 stadig er gyldig.

Løsning

:- op(600, yfx, ?).

 

 

Vinter 2000, Opgave 7

 

Denne opgave drejer sig om regulære udtryk og tilstandsmaskiner og kan løses på baggrund af ªSprog og abstrakte maskiner´ (2. rev. udgave), kapitel 4 og 11. Vi antager et alfabet, som omfatter netop de fire bogstaver a, b, c og d og ikke andre, og opgaven går ud på at tegne to tilstandsmaskiner.

Spørgsmål 1

Tegn en deterministisk tilstandsmaskine uden tomme træk (dvs. ingen pil har tom etikette), som accepterer netop de strenge over vores alfabet, som beskrives ved følgende regulære udtryk:

a*bac

Løsning:

      _a
     / \
     \ /   b         a       c
----->0-------->0------->0-------->(0)

 

 

Spørgsmål 2

I ªSprog og abstrakte maskiner´, afsnit 11.4, beskrives Knuth-Morris-Pratt-strengsøgningsmetoden, og dette spørgsmål gå ud på at anvende de samme principper på det lidt mere generelle problem, nemlig at lede efter en delstreng beskrevet ved et regulært udtryk. Spørgsmålet lyder: Tegn en tilstandsmaskine, som accepterer strenge over vores alfabet, som indeholder en delstreng beskrevet ved det regulære udtryk a*bac.

Eksempler på strenge, som skal accepteres:

acdcaaaabac, asdcbac

Løsning:

 

      _a,c,d           ___b_________
     / \              /             \
     \ /       b      V       a     |     c
----->0-------------->0------------>0----------->(0)
    / ^              / \  \         | 
    | |c,d           \_/b |         |a,d
    | \___________________/         |
     \______________________________/

 

 

Opgave 1 (15%)

I denne opgave betragtes den simple heltals Java maskine (IJVM), som Mic-1 microprogrammet i Tannenbaum implementerer.

Antag at vi har følgende programstump i Java:

j=4; k=3; r=1;

for (i=0; i<j; i++)

r = r+k;

r = r-2;

Der er flere måder at oversætte dette til IJMV, for eksempel ved at oprette variable, og gemme alle mellemresultater ved brug af ISTORE, eller ved at anvende stakken til at opbevare alle mellemberegninger.

I det følgende antages at en oversætter ved oversættelse af programstumpen producerer følgende IJVM kode:

BIPUSH 4

ISTORE j // j=4;

BIPUSH 3

ISTORE k // k=3;

BIPUSH 1 // r=1;

BIPUSH 0 // i=0;

L1: DUP

ILOAD j

ISUB

IFLT L2 // if ( (i-j) < 0 )

POP

BIPUSH 2

ISUB // r=r-2;

GOTO L3

L2: SWAP

ILOAD k

IADD

SWAP // r=r+k;

BIPUSH 1

IADD // i=i+1;

GOTO L1

L3: ISTORE r

Spørgsmål 1

Vil en udførsel af denne kodestump resultere i det samme resultat, som man ville forvente af en udførsel af Java programstumpen?

Svaret skal begrundes, eventuelt ved at redegøre for hvilke værdier de fire variable i, j, k og r har efter udførelsen i de to tilfælde.

Hvis der er forskel, hvilken betydning har en sådan så?

Løsning:

Java programmet giver:

j = 4

k = 3

r = 11

i = 4

IJVM programmet giver:

j = 4

k = 3

r = 11

i = ???

Den eneste forskel er, at værdien af tællevariablen "i" ikke gemmes. Det vil sige, at hvis værdien af denne variabel skal bruges senere i programmet, så vil en oversættelse af programmet ikke give det forventede resultat. I praksis vil værdien af en sådan tællevariabel ikke blive brugt senere i programmet, hvilket nogle oversættere konstaterer, og derfor ikke spilder CPU tid på at gemme resultater der ikke skal anvendes. I praksis vil de to programmer derfor give det samme resultat.

Spørgsmål 2

Udvid Mic-1 microprogrammet med operationen "INEG", der negerer værdien øverst på stakken.

Eksempel:

Hvis stakken til at begynde med indeholder:

[4 2 ...]

vil stakken efter udførsel af INEG indeholde:

[-4 2 ...]

Løsning:

ineg1 H = TOS

ineg2 MDR = TOS = -H;

ineg3 MAR = SP; wr; goto Main1

Mic-1 tillader kun negering på A bussen, hvorfor indholdet af TOS først skal kopieres til H registeret.