Einf. in das symbolische Programmieren      CIS, SS 2006, H.Leiss
=================================================================

Abgabe: Donnerstag, Do 29.6.06 bis 13 Uhr
-----------------------------------------

Aufgabe 9  
---------
Wir haben bestimmte Prolog-Terme als "unsere eigenen natürlichen Zahlen" 
ausgezeichnet, nämlich die, auf die das Prädikat nat/1 zutrifft:

   nat(0).
   nat(s(X)) :- nat(X).

Dann hatten wir die Addition unserer natürlicher Zahlen durch ein Prädikat 

   add(+Zahlterm,+Zahlterm,-Zahlterm für die Summe der beiden Zahlen)

definiert, durch

   add(0,M,M) :- nat(M).              % entspricht 0+M = M
   add(s(N),M,s(K)) :- add(N,M,K).    % entspricht (N+1)+M = (N+M)+1

Definieren Sie entspechend die Multikplikation zweier Zahlen durch
ein Prädikat

   mult(+Zahltermn,+Zahlterm,-Zahlterm des Produkts der beiden Zahlen).

Hinweis:
--------
Benutzen Sie Fallunterscheidung (bzw. Rekursion) nach dem ersten
Argument, und verwenden Sie add/3.                        Punkte 3


Aufgabe 10
----------
Wir haben in der Vorlesung ein Prädikat für binäre Bäume mit Zahlen an
den Blättern definiert, 

  baum(knoten(L,R)) :- baum(L), baum(R).
  baum(blatt(N)) :- number(N).

und dann ein Prädikat zum Sammeln der Blätter des Baums definiert.

a) Definieren Sie ein ähnliches Prädikat baum/1, für allgemeinere
   Bäume, bei denen eine Verzweigung in zwei oder mehr Teilbäume
   erlaubt ist, und bei denen die Blätter Prolog-Atome sein dürfen.  
                                                          Punkte 3

b) Passen Sie das Prädikat blaetter(+Baumterm,-Blattliste) so an, daß
   es für diese Bäume funktioniert.
   
   (1) indem Sie rekursiv die Liste der direkten Teilbäume bearbeiten
       und die Blattlisten vereinigen,                    Punkte 3

   (2) indem Sie mit einem Akkumulator beim Bearbeiten eines Teilbaums
       dessen Blätter im Akkumulator sammeln              Punkte 3

Aufgabe 11
----------
Angenommen, wir haben eine Grammatik mit bestimmten syntaktischen und
lexikalischen Kategorien, die durch Prolog-Terme benannt werden, zum 
Beispiel durch die mit den folgenden Eigenschaften:

   synkat(Term) :- member(Term,[np,ap,pp,s]).
   lexkat(Term) :- member(Term,[n,a,det,p,pron,grad,iv,tv]).

Als mögliche Syntaxbäume seien alle Bäume erlaubt, deren innere Knoten
mit einer syntaktischen Kategorie und deren Blätter mit einer
lexikalischen Kategorie und dem jeweiligen Wort des analysierten
Ausdrucks markiert sind. 

Damit die Anzahl der Konstituenten nicht eingeschränkt ist und
beliebige Prolog-Atome als Wörter erlaubt sind, definieren wir

   syntaxbaum(knoten(C,[B|Bs])) :- synkat(C), syntaxbaeume([B|Bs]).
   syntaxbaum(blatt(C,W)) :- lexkat(C), atom(W).

a) Wie sollte syntaxbaueme/1 definiert werden?           1 Punkt

b) Schreiben Sie ein Programm 

      pronominalisiere(+Syntaxbaum1,-Syntaxbaum2).

   das aus dem Eingabebaum Syntaxbaum1 einen Ausgabebaum Syntaxbaum2 
   macht, indem es alle np-Teilbäume durch pron-Teilbäume mit dem
   Pronomen 'es' ersetzt.

   Hinweis:                                              8 Punkte

   1. Gehen Sie rekursiv durch den Baum: wenn er ein Knoten mit Kategorie
      C = np ist, muß er ersetzt werden, sonst bearbeiten Sie die
      Teilbäume. (Machen Sie die Fallunterscheidung mit ! oder mit -> .)

   2. Benutzen Sie ein Hilfsprädikat

      pronominalisiereL(+Liste von Syntaxbäumen,
                        -Liste der pronominalisierten Syntaxbäume).

   
Ihr Programm sollte z.B. zum Syntaxbaum

    knoten(s,[blatt(pron,wir),
              blatt(tv,kennen),
              knoten(np,[blatt(det,die),
                         blatt(n,'Loesung'),
                         knoten(np,[blatt(det,der),blatt(n,'Aufgabe')]) 
                        ])
             ])

den 'pronominalisierten' Syntaxbaum

    knoten(s,[blatt(pron,wir),
              blatt(tv,kennen),
              blatt(pron,es)
             ])

ausgeben, also die umfassendsten Nominalphrasen durch das Pronomen ersetzen.