Informatik/Jahrgangsstufe Q/001 Klausuren/Q2/2002-2003-1

1. INFORMATIK-KLAUSUR
Name:
Bearbeitungszeit: 180 min
Info 13 LK (GA)
23.09.2002
− Seite 1 −
Aufgabe 1: Du kennst vielleicht diese russischen Holzpüppchen, in
denen immer noch eine kleinere drin steckt. Rechts ist
eine schematische Abbildung von solchen
ineinandersteckenden russischen Puppen:
katarina
olga
natasha
a) Stelle die drei direkten Lagebeziehungen in Form von
Fakten in Prolog dar: direktin(... , ...).
b) Definiere ein Prädikat in/2 (d. h. ein Prädikat mit zwei
Parametern), dass uns sagt welche Puppe (direkt oder
indirekt) in welcher anderen Puppe steckt. Die Anfrage
in(katarina,natasha) z.B. sollte wahr sein,
während in(olga,katarina) fehlschlagen sollte.
Hinweis: Nutze dabei auch das Prädikat aus Teilaufg. a).
c) Welche Ausgabe erhältst du bei der Anfrage in(X,katarina)?
d) Welche Ausgabe erhältst du bei der Anfrage in(X,Y), wenn alle Lösungen
angefordert werden?
e) Stelle das Backtracking beim Aufruf in(katarina,irina) grafisch dar.
irina
Aufgabe 2: Folgende Reisemöglichkeiten stehen zur Auswahl:
byCar(auckland,hamilton). /*
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).
←
/*
/*
/*
Dies bedeutet: Man kommt mit dem
Auto von Auckland nach Hamilton.
Die anderen Prädikate sind ebenfalls so zu lesen.
byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).
*/
*/
*/
*/
byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(losAngeles,auckland).
a) Schreibe ein Prädikat travel/2, welches herausfindet, ob es möglich ist, von
einer Stadt zu einer anderen Stadt zu reisen. Die Wahl des Verkehrsmittels soll
dabei keine Rolle spielen.
Beispiel: Dein Programm sollte die Anfrage travel(valmont,raglan)
mit ‘yes’ beantworten.
b) Plant man seine Reise etwas genauer, so ist es interessant zu wissen, über welche
Stadt man zum Ziel gelangt. Schreibe deshalb ein Prädikat travel/3, welches
dir ausgibt, über welche Zwischenpunkte du von der einen Stadt zur anderen
gekommen bist.
Beispiel: Dein Programm sollte bei der Anfrage
travel(valmont,paris,go(valmont,metz,go(metz,paris))) die Antwort
‘yes’ ausgeben. Fragt man dein Programm nach
travel(valmont,losAngeles,X) so sollte es
X = go(valmont,metz,go(metz,paris,go(paris,losAngeles))) ausgeben.
c) Zur noch besseren Routenplanung ist auch eine Ausgabe des Verkehrsmittels
zweckmäßig. Erweitere dein Prädikat travel/3, so dass es dir nicht nur mitteilt,
über welche Zwischenpunkte die Reise geht, sondern auch sagt, mit welchem
Verkehrsmittel die einzelnen Teilstücke zurückgelegt wurden.
Beispiel: die Anfrage travel(valmont,losAngeles,X) sollte
X = car(valmont, metz, train(metz, paris, plane(paris, losAngeles)))
ausgeben.
Bitte wenden
Name:
1. INFORMATIK-KLAUSUR
23.09.2002
Info 13 LK (GA)
Bearbeitungszeit: 180 min
− Seite 2 −
Aufgabe 3: Im Zusammenhang mit Listen haben wir im Unterricht bereits einige Prädikate
kennen gelernt. Hier sollen nun neue Prädikate entwickelt und analysiert
werden:
a) Betrachte das folgende Prädikat wti/4:
wti(_, _, [], []).
wti(X, Y, [X | Rest], [Y | Rest]).
wti(Z1, Z2, [X | Rest], [X | NeuerRest]):Z1 \= X,
wti(Z1, Z2, Rest, NeuerRest).
I) Welche Ausgabe wird bei der Anfrage wti(3,9,[1,2,3,4,5],X)
produziert?
II) Notiere die Ausgabe zur Anfrage wti(1,2,[0,1,1,0,0,0,1,0],Y).
III) Beschreibe allgemein die Wirkung des Prädikats wti/4.
b) Erweitere das oben angegebene Prädikat, so dass die unter a.III) beschriebene
Aktion auf die ganze Liste ausgeweitet wird.
c) Schreibe ein Prädikat restliste/3, welches von einer Liste die Restliste
nach dem ersten Auftreten eines Elements zurück gibt.
Beispiel: restliste([1,2,3,4,5],3,X) wird mit X = [4,5] beantwortet.
d) Gegeben ist das folgende Programm:
wti( [], Liste, Liste ).
wti([Head|Tail], SListe, X ) :split( Head, Tail, Kleiner, Groesser),
wti(Groesser, Rest, X ),
wti(Kleiner, SListe, [Head|Rest]).
/* split(X,Liste,Kleine,Grosse) teilt die Liste
*/
/* bezüglich des Vergleichselements X in die zwei */
/* Listen Kleine und Grosse.
*/
Im ersten Aufruf sollte das dritte Argument immer eine leere Liste sein.
Beispiel: wti([4,3,8,7,1,5,4,8],Ergebnis,[]).
I) Welche Ausgabe wird bei obigem Beispiel getätigt?
II) Gib dem Prädikat einen aus Informatikersicht sinnvollen Namen.
III) Beschreibe die Unterschiede zu dem aus dem Unterricht bekannten
ähnlichen Verfahren.
e) In der folgenden Routine split/4 aus obigen Programm haben sich Fehler
eingeschlichen. Kommentiere jeden Fehler, indem du angibst, inwiefern sich
dieser Fehler äußert (Compilerfehler, Laufzeitfehler). Korrigiere jeden Fehler
einzeln oder gib das gesamte Teilprogramm in korrekter Form an.
split(_, [], K, G).
split(Element, [Head|Tail], Kleiner, Groesser):Head <= Element,
split(Element, Tail, hilfKleiner, Groesser),
append(Head, hilfKleiner, Kleiner).
split(Element, [Head|Tail], Kleiner, Groesser):=
Head > Element,
split(Element, Tail, Kleiner, Groesser),
append(Head, Groesser, Groesser).
Bitte wenden
Name:
Info 13 LK (GA)
1. INFORMATIK-KLAUSUR
Bearbeitungszeit: 180 min
23.09.2002
− Seite 3 −
Aufgabe 4: Aus dem Unterricht kennst du die Baumstruktur. Ein Baum konnte
6
entweder leer (nil) oder eine Wurzel mit zwei Teilbäumen
(baum(W,L,R)) sein.
3
9
a) Stelle den rechts abgebildeten Baum mit Hilfe des Prädikats baum/3
dar.
4
7
10
b) Zeichne den zum folgenden Ausdruck zugehörigen Baum:
baum(2, baum(1, nil, nil), baum(7, baum(3, nil,
8
baum(6, nil, nil)), baum(8, nil, nil)))
c) Implementiere ein Prädikat knotenanzahl/2, welches als Input einen Baum und als
Output die Anzahl der Knoten des Baumes enthält.
Beispiel: knotenanzahl(baum(3,baum(2,nil,nil),baum(5,baum(4,nil,nil),nil)),X)
würde X = 4 ausgeben.
d) Implementiere ein Prädikat baumhoehe/2, welches die Anzahl der Ebenen − also
die Baumhöhe − eines Baumes ausgibt.
Hinweis: Der Baum aus Teilaufgabe a) hat übrigens die Höhe 4!
Ich wünsche dir viel Erfolg!
Name:
1. INFORMATIK-KLAUSUR
23.09.2002
− Seite 4 −
Bearbeitungszeit: 180 min
Info 13 LK (GA)
LÖSUNGEN:
Aufgabe 1: a) Eine Möglichkeit ist die folgende:
direktin(katarina,olga).
direktin(olga,natasha).
direktin(natasha,irina).
b) in(X,Y):- direktin(X,Y).
in(X,Y):- direktin(Z,Y), in(X,Z).
c) Ausgabe ‚no’
d) Ausgabe: X = katarina Y = olga ;
X = olga Y = natasha ;
X = natasha Y = irina ;
X = katarina Y = natasha ;
X = olga Y = irina ;
X = katarina Y = irina
e)
in(katarina, irina)
direktin(katarina, irina)
schlägt fehl
direktin(natascha, irina),
ist erfüllt
in(katarina,natasha)
direktin(katarina, natasha)
schlägt fehl
direktin(olga, natasha),
ist erfüllt
in(katarina,olga)
direktin(katarina, olga)
ist erfüllt
Aufgabe 2: a) Eine Möglichkeit ist:
traveldirekt(X,Y):- byCar(X,Y); byTrain(X,Y); byPlane(X,Y).
travel(X,Y):- traveldirekt(X,Y).
travel(X,Y):- traveldirekt(X,Z),travel(Z,Y).
b) Die Erweiterung könnte wie folgt aussehen:
traveldirekt(X,Y):- byCar(X,Y); byTrain(X,Y); byPlane(X,Y).
travel(X,Y,go(X,Y)):- traveldirekt(X,Y).
travel(X,Y,go(X,Z,F)):- traveldirekt(X,Z),travel(Z,Y,F).
c) Mit Fahrzeugangabe:
travel(X,Y,car(X,Y)):- byCar(X,Y).
travel(X,Y,train(X,Y)):- byTrain(X,Y).
travel(X,Y,plane(X,Y)):- byPlane(X,Y).
travel(X,Y,car(X,Z,F)):- byCar(X,Z),travel(Z,Y,F).
travel(X,Y,train(X,Z,F)):- byTrain(X,Z),travel(Z,Y,F).
travel(X,Y,plane(X,Z,F)):- byPlane(X,Z),travel(Z,Y,F).
Aufgabe 3: a) I) X = [1,2,9,4,5]
II) X = [0,2,1,0,0,0,1,0]
III) Das erste vorkommende Element der Liste, welches mit dem ersten
Argument des Prädikats wti übereinstimmt, wird durch das zweite
Argument ersetzt. Die so gewonnene Liste wird im 4. Argument
zurückgegeben.
1. INFORMATIK-KLAUSUR
Name:
Bearbeitungszeit: 180 min
Info 13 LK (GA)
23.09.2002
− Seite 5 −
b) wti(_, _, [], []).
wti(X, Y, [X | Rest], [Y | NeuerRest]):wti(X,Y,Rest,NeuerRest).
wti(Z1, Z2, [X | Rest], [X | NeuerRest]):Z1 \= X,
wti(Z1, Z2, Rest, NeuerRest).
c) restliste([X | Rest], X, Rest).
restliste([_ | End], X, Rest):restliste(End, X, Rest).
d) I) Ergebnis = [1,3,4,4,5,7,8,8]
II) Ein sinnvoller Name wäre Quicksort.
III) Der wesentliche Unterschied ist der, dass das Prädikat keinen appendBefehl benötigt. Dies gelingt, indem immer eine Liste „mitgeschleppt“
wird, in der sofort die Vereinigung der beiden Teillisten gespeichert
wird. Deshalb muss allerdings auch am Anfang eine leere Liste
mitgegeben werden, da diese am Schluss wieder hinten angefügt wird.
e) Die richtige Prozedur müsste wie folgt aussehen:
split(_, [], [], []).
split(Element, [Head|Tail], Kleiner, Groesser):Head =< Element,
split(Element, Tail, Kleiner1, Groesser),
append([Head],Kleiner1,Kleiner).
split(Element, [Head|Tail], Kleiner, Groesser):Head > Element,
split(Element, Tail, Kleiner, Groesser1),
append([Head],Groesser1,Groesser).
Die Fehler im einzelnen:
1. Zeile: bei einer leeren Liste sollte sowohl die Kleiner- als auch die
Groesser-Liste leer sein. In der falschen Version sind K und G
undefiniert. (Laufzeitfehler).
3. Zeile: <= ist falsch. Richtig: =< (Compilerfehler)
4. Zeile: hilfKleiner muss HilfKleiner heißen, da eine Variable
benötigt wird. (Compilerfehler)
5. Zeile: append benötigt 3 Listen. Head ist aber nur ein Element.
Besser: [Head]. (Compilerfehler).
6. Zeile: := ist falsch. Richtig :- (Compilerfehler).
9. Zeile: Groesser ist sowohl Input- als auch Outputvariable.
(Laufzeitfehler).
Aufgabe 4: a) baum(6,baum(3,nil,baum(4,nil,nil)),
baum(9,baum(7,nil,baum(8,nil,nil)),
baum(10,nil,nil)))
2
1
b) Wie rechts abgebildet.
c)
knotenanzahl(nil,0).
knotenanzahl(baum(W,L,R),Anz):knotenanzahl(L,AnzL), knotenanzahl(R,AnzR), Anz is 1+AnzL+AnzR.
d) baumhoehe(nil,0).
baumhoehe(baum(W,L,R),H):baumhoehe(L,H1), baumhoehe(R,H2), H1>H2, H is H1+1.
baumhoehe(baum(W,L,R),H):baumhoehe(L,H1), baumhoehe(R,H2), H1=<H2, H is H2+1.
7
3
8
6