Klausur Einfuehrung in das symbolische Programmieren   SS 2001, CIS
====================================================   H.Leiss,S.Leonardi 17.7.2001
Sie sollten insgesamt etwa 20 Punkte erreichen!


Aufgabe 1 (Listen, Rekursion, Arithmetik)                               (2 Punkte)
----------
Definiere die Laenge von Listen in Prolog, durch ein Praedikat laenge(Liste+,Zahl).


Aufgabe 2 (Listen)                                                      (3 Punkte)
---------
Welche der folgenden Terme sind Listen in Prolog?

a) [a,b|[c,d]],  b) [a,b|[c|d]]  c) [a,[b],c]  d) [a,[b]|c]  

e) [a|[b]|[]]    f) [a|[[b]|[]]]


Aufgabe 3 (Unifikation)                                                 (5 Punkte)
---------
a) Was ist die Belegung der Variablen X,Y,Z  nach der Unifikation der beiden Terme

       f(X,g(2,X),Z)  und   f(h(Y),Z,g(Y,X))  ?               

b) Worin unterscheidet sich die Unifikation von dem Termvergleich  =  in Prolog?
   Gib einen Term t an, fuer den  unify(X,t)  mit `fail' antwortet, aber Prolog
   bei  ?- X = t.   nicht scheitert.                              


Aufgabe 4 (Suchbaum, Cut)
---------
a) Das Programm mit den 5 Klauseln                                     (5 Punkte)

1.    p(X,Y) :- q(X), true, r(Y).

2.    q(0).
3.    q(1).
4.    r(0).
5.    r(1).

sei gegeben. Stelle den vollstaendigen Suchbaum zur Anfrage

    ?- p(X,Y).

dar. (Mit Nummern der benutzten Klauseln an den Zweigen und der Belegung von
Variablen.)

b) Ersetze im Programm aus a) 'true' durch einen Cut '!'. Welche Antworten hat die
   Anfrage ?- p(X,Y).  noch?  Wie sieht der Suchbaum jetzt aus?          (3 Punkte)


Aufgabe 5 (DCG, Differenzlisten)
---------
Angenommen, Prolog hat folgende Definite-Clause-Regeln geladen:

   s --> np(nom,plur), aux(plur), v(partizip).
   np(nom,plur) --> [die,'Studenten'].
   aux(plur) --> [haben].
   aux(plur) --> [sind].
   v(partizip) --> [gearbeitet].
   v(partizip) --> [gekommen].

a) Prolog uebersetzt diese Regeln in eine Klauseldarstellung. Welche Klauseln ergeben 

   (i) listing(s), (ii) listing(aux), (iii) listing('-->') ?             (4 Punkte)

b) Wie sieht der Aufruf auf, mit dem Sie pruefen koennen, ob              (1 Punkt)
  
      die Studenten haben gearbeitet

   als Satz erkannt wird ?

c) Erweitere die Regeln um Merkmale, sodass die (ungrammatischen) Saetze 

      die Studenten haben gekommen 
      die Studenten sind gearbeitet

   nicht mehr als Saetze erkannt werden.                                 (3 Punkte)


Aufgabe 6 (Datentypen, Rekursion, Akkumulatoren)
---------
a) Definiere ein Praedikat                                               (3 Punkte)

      einfach/1, 

   das auf genau die Terme t zutrifft, die entweder atomar sind oder 
   aus einem 3-stelligen Funktionszeichen mit einfachen Teiltermen
   bestehen.

b) Ein "np-Teilterm" eines Terms t sei ein Teilterm von t, dessen        (5 Punkte)
   Funktionszeichen 'np' ist. Ein Vorkommen eines np-Teilterms von t ist
   "maximal", wenn es nicht in einem anderen np-Teilterm von t liegt.

   Definiere ein Praedikat 

      collectNPs(+Term,-Liste von Termen),

   das zu einem einfachen (s.o.) variablenfreien Term t eine Liste
   seiner maximal vorkommenden np-Teilterme ausgibt. Die np-Teilterme
   sollen in dieser Liste in derselben Reihenfolge angeordnet sein wie
   ihre Vorkommen in t. 
   
   Gib eine Definition mit einem Hilfspraedikat collNPs(+Term,+Acc,-Liste), 
   das im Akkumulator Acc die schon gefundenen np-Teilterme sammelt.
   
c) Wie ist die Definition aus b) zu aendern, damit in der Ausgabeliste   (2 Punkte)
   zuerst die np-Teilterme des mittleren Teilterms erscheinen?