Einf. in das symbolische Programmieren CIS, SS 2002, H.Leiss ================================================================= Abgabe: Mittwoch, 19.06.02 in der Vorlesungsstunde. --------------------------------------------------- Aufgabe 13: ----------- In der Musterloesung zu Aufgabe 9 b) wurde flachmachen2(+Liste,-FlacheListe) so definiert: flachmachen2([],[]). % Fall 1 flachmachen2([E | Elemente], Ergebnis) :- % Fall 2 flachmachen2(Elemente, Flach), % Erstmal den Rest flach machen, zusammenfuegen(E, Flach, Ergebnis). % dann das E beruecksichtigen zusammenfuegen(E, Flach, Ergebnis) :- % Fallunterscheidung: liste(E), % Fall 2a: E ist eine Liste append(E, Flach, Ergebnis). zusammenfuegen(E, Flach, Ergebnis) :- not(liste(E)), % Fall 2b: E ist keine Liste Ergebnis = [E | Flach]. liste([]). % Test auf Listeneigenschaft liste([X|Xs]) :- liste(Xs). a) Schreibe die Fallunterscheidung mit Hilfe eines ! (Cut). (3 Punkte) b) Schreibe die Fallunterscheidung mit Hilfe von (If -> Then ; Else) (3 Punkte) c) Schreibe zusammenfuegen/3 ohne Verwenden von list/1. (3 Punkte) Gib die Ausgabe fuer die Eingabeliste [a,[a,b],[],[d,[e,f],g],[h,[],h],[i|[]],j,k] an. Es darf auch keine falschen alternativen Loesungen geben! Aufgabe 14: ----------- Wir wollen quicksort/2 so aendern, dass wir statt Listen von Zahlen Listen von Atomen sortieren koennen. Dabei sollen die Atome nach der lexikographischen Ordnung sortiert werden (d.h. die Woerter erscheinen in der Reihenfolge eines Lexikons). Dazu brauchen wir mehrere Schritte (vielleicht besser in der Reihenfolge b),c),a),d),e)): a) In SWI-Prolog kann man Atome mit atom_chars/2 in Character-Listen (4 Punkte) umwandeln (siehe Handbuch und teste am Rechner!), z.B. atom_chars('Aachen',['A',a,c,h,e,n]). (Character sind in SWI-Prolog 1-Buchstaben-Atome.) Schreibe damit zwei Praedikate atom_leq(+Atom,-Charliste) und atom_lt(+Atom,-Charliste), die den Vergleich von Atomen (analog zu =< und < bei Zahlen) auf den Vergleich der entsprechenden Characterlisten, chars_leq/2 und chars_lt/2 in c) unten, zurueckfuehrt. b) Bevor wir definieren koennen, wie man Character-Listen vergleicht, (4 Punkte) muessen wir einzelne Character vergleichen koennen. Dazu wir den Vergleich der entsprechende ASCII-Codenummern benutzen. Die Umwandlung von Charactern in ASCII-Nummern ist in SWI-Prolog atom_char(+Atom aus einem Buchstaben, -Zahl). Benutze diese Umwandlung, um zwei Praedikate char_leq(A,B) und char_lt(A,B) zu schreiben, mit denen zwei Character nach ihren ASCII-Codenummern verglichen werden. (Dabei sind Grossbuchstaben < Kleinbuchstaben.) Es sollte z.B. gelten: char_leq(a,a) und char_lt('A',a). c) Jetzt koennen wir die lexikographische Ordnung von Charakterlisten (8 Punkte) programmieren, chars_leq(Cs,Ds) und chars_lt(Cs,Ds). Definiere diese durch Fallunterscheidung und Rekursion im ersten Argument, und benutze char_leq/2 und char_lt/2 aus Teil b). Tip fuer chars_leq(Chars1,Chars2): --------------------------------- Fall 1. Chars1 = []. Soll dann chars_leq(Chars1,Chars2) gelten? Fall 2. Chars1 = [C|Cs]. Man muss festlegen: - Soll chars_leq([C|Cs],[]) gelten? - Unter welchen Umstaenden soll chars_leq([C|Cs],[D|Ds]) gelten? Ueberlege an einem Beispiel, wie man zwei Woerter buchstabenweise vergleicht, z.B. abends und aber. Man sollte z.B. erhalten: chars_leq([a,b,e,n,d,s],[a,b,e,r]). Bei chars_lt geht es analog, aber man muss mit [] aufpassen. d) Teste, ob die Praedikate atom_leq/2 und atom_lt/2 aus Teil a) jetzt (wo chars_leq und chars_lt da sind) ausfuehrbar sind und richtige Ergebnisse liefern. Man sollte z.B. erhalten: atom_leq(abends,aber). atom_lt('Abend',ab). e) Nun koennen wir quicksort anpassen. Schreibe (3 Punkte) quicksort_atoms(+Liste von Atomen,-Sortierte Liste dieser Atome), indem in quicksort/2 (bzw. partition/4) der Vorlesung die Zahlenvergleiche durch Vergleiche von Atomen nach Teil a) ersetzt werden. Was liefert der Aufruf: ?- quicksort_atoms([aber,abends,ahmen,alle,'Achmed',nach],Sortiert) Bemerkung: --------- Verzweifeln Sie nicht! Es sieht nach viel mehr Arbeit aus als es ist. Die Programme sind alle recht kurz und die _leq und _lt-Versionen gleichen sich sehr. Die logische Zerlegung des Problems ist durch die Aufgabenstellung ja schon erledigt! Wir koennen auch am Freitag schon etwas davon in der Uebungsstunde machen.