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

Abgabe: Donnerstag, Mi 8.6.06 bis 13 Uhr
----------------------------------------

Aufgabe 7                                                   
---------
In Prolog fasst man die Atome und die Zahlen als "atomare Terme"
zusammen. 
(Eingebaute Testpraedikate dafuer sind: atom/1, number/1, atomic/1.)

a) Schreibe ein Prolog-Praedikat,                        (3 Punkte)

      element(+Atomarer Term,+Liste von atomaren Termen)    

   mit dem man feststellen kann, ob ein Term (hier: = Atomarer Term
   oder Liste) in einer Liste von atomaren Termen vorkommt. 

   Sie können annehmen, daß die Eingabeliste nur atomare Terme enthaelt. 

b) Schreibe (mit Teil a)) ein Praedikat                  (5 Punkte)

      difference(+Liste1,+Liste2,-Ergebnis),

   das bei Eingabe zweier Listen von atomaren Termen, Liste1 und Liste2, 
   im dritten Argument, Ergebnis, eine Liste der Elemente ausgibt,
   die in Liste1 vorkommen, aber nicht in Liste2. 

c) Schreibe --ohne das element/2 aus (a)-- ein Praedikat 

      insert(+Liste atomarer Terme, +atomarer Term,-erweiterte Liste),

   das einen Term in eine Liste einfügt, wenn er darin noch nicht 
   vorkommt. 
                                                         (3 Punkte)
   Hinweis: 
   Vergleiche den Term mit dem ersten Element der Liste ...

c) Schreibe ein Praedikat 

      set(+Liste atomarer Terme, -Liste der Elemente darin),

   das aus eine Liste eine Menge macht, d.h. im Ausgabeargument 
   sollen dieselben Elemente wie in der Eingabeliste vorkommen,
   aber jedes nur einmal, wie bei

      ?- set([a,b,3,b,a,a,3],Menge).
      Menge = [3,b,a].

   Hinweis: 
   Benutze einen Akkumulator, der die von der Eingabeliste schon 
   gesehenen Elemente sammelt (jedes nur einmal), und das naechste 
   Element der Eingabe bei 

      set([X|Xs],GeseheneElemente,Menge) :- ...

   nur dann sammelt, wenn man es nicht schon gesehen hat.  (6 Punkte)


Aufgabe 8:                                                 (2 Punkte)
---------
Wir hatten in der Vorlesung heute eine Variante von quicksort mit
einem Akkumulator besprochen (s.Folien), die hier im Unterschied 
zum normalen 'quicksort' mit 'quicksort2'bezeichnet wird.

Wählen Sie eine Liste von 10 Zahlen und stellen sie mit 

    ?- time(quicksort(+Liste)).  % Leider falsch war: time(quicksort,+Liste).

bzw. mit
  
    ?- time(quicksort2(+Liste)). % Leider falsch war: time(quicksort2,+Liste).

fest, wie lange das Sortieren dauert und wie viele Beweisschritte
(= 'inferences' in der Meldung von Prolog) das SWI-System in beiden
Fällen braucht. (Siehe auch ?- help(time).)

Machen Sie die Liste doppelt und 3-mal so lang und prüfen Sie 
nochmal den Unterschied. 

Wie gross ist im Durchschnitt der 3 Versuche das Verhaeltnis 

         Beweisschritte von quicksort2
         -----------------------------
         Beweisschritte von quicksort

bei Ihren Beispielen?                                     (Punkte 4)