Bearbeiten von „P1-WS04-MusterLoesung07.txt“

<pre>
% -*-prolog-*-
%
%                       P1 Übungen WS2004/2005
%                  Musterlösung Blatt 7 (Hans Meine)
%
%---------------------------------------------------------------------
%                         1. Datenaggregation
%---------------------------------------------------------------------
%
% Beispieldaten von Aufgabenblatt:

spiel(4,kiel,magdeburg,30,28).
spiel(4,lemgo,essen,27,23).
spiel(4,minden,nordhorn,32,28).
spiel(5,solingen,schwerin,29,32).
spiel(5,nordhorn,lemgo,20,21).
spiel(5,eisenach,wetzlar,28,34).

% (a) sum(+Liste,?Summe)
%     berechnet die arithmetische Summe der Elemente einer Liste

sum([], 0).
sum([Kopf|Rest], Summe) :-
    sum(Rest, Restsumme),
    Summe is Kopf + Restsumme.

% (b) tore(?Mannschaft,?Treffer,?Gegentreffer)
%     bestimmt eigene und gegenerische Tore berechnet, unabhängig
%     davon, ob das Spiel zu Hause oder auswärts stattfand.

tore(Mannschaft, Treffer, Gegentreffer) :- % Heimspiel
    spiel(_, Mannschaft, _, Treffer, Gegentreffer).

tore(Mannschaft, Treffer, Gegentreffer) :- % Auswärtsspiel
    spiel(_, _, Mannschaft, Gegentreffer, Treffer).

% (c) tor_verhaeltnis(+Mannschaft, ?Treffer, ?Gegentreffer)
%     berechnet Summe aller Tore bzw. Gegentore in allen Spielen der
%     Mannschaft, indem alle Ergebnisse in Listen gesammelt und mit
%     dem sum/2 aus (a) aufaddiert werden:

tor_verhaeltnis_1(Mannschaft, Treffer, Gegentreffer) :-
    findall(Tore, tore(Mannschaft, Tore, _), Trefferliste),
    sum(Trefferliste, Treffer),
    findall(Gegentore, tore(Mannschaft, _, Gegentore), Gegentrefferliste),
    sum(Gegentrefferliste, Gegentreffer).

%     (Wie das + im dokumentierten Prädikatskopf schon andeutet, muß
%     Mannschaft instanziiert werden, damit findall nur die Spiele
%     einer Mannschaft findet.)
%
%     Da (d) so ähnlich gelöst werden kann, bilden wir noch ein
%     Hilfsprädikat:
%     trefferlisten(+Mannschaft, ?Trefferliste, ?Gegentrefferliste)
%     bildet die Listen aller Treffer beziehungsweise aller Gegentreffer:

trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste) :-
    findall(Tore, tore(Mannschaft, Tore, _), Trefferliste),
    findall(Gegentore, tore(Mannschaft, _, Gegentore), Gegentrefferliste).

%     ..damit kann tor_verhaeltnis/3 etwas kürzer formuliert werden:

tor_verhaeltnis(Mannschaft, Treffer, Gegentreffer) :-
    trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste),
    sum(Trefferliste, Treffer),
    sum(Gegentrefferliste, Gegentreffer).

% (d) tore_durchschnitt(+Mannschaft,
%                       ?Treffer_Durchschnitt, ?Gegentreffer_Durchschnitt)
%     berechnet die durchschnittliche Zahl von Treffern und
%     Gegentreffern pro Spiel einer Mannschaft (unter Benutzung des
%     eben definierten trefferlisten/3-Prädikats und des eingebauten
%     length/2 für Listen):

tore_durchschnitt(Mannschaft, Treffer_Durchschnitt, Gegentreffer_Durchschnitt) :-
    trefferlisten(Mannschaft, Trefferliste, Gegentrefferliste),
    sum(Trefferliste, Treffer),
    sum(Gegentrefferliste, Gegentreffer),
    length(Trefferliste, AnzahlSpiele),
    Treffer_Durchschnitt is Treffer / AnzahlSpiele,
    Gegentreffer_Durchschnitt is Gegentreffer / AnzahlSpiele.

% (e) punkte(+Mannschaft, ?Plus, ?Minus)
%     berechnet die in einem Spiel von einer Mannschaft erzielten
%     Tabellenpunkte, unabhängig davon, ob das Spiel zu Hause oder
%     auswä rts stattfand:

punkte(Mannschaft, 2, 0) :-
    tore(Mannschaft, Treffer, Gegentreffer),
    Treffer > Gegentreffer.

punkte(Mannschaft, 1, 1) :-
    tore(Mannschaft, Unentschieden_Treffer, Unentschieden_Treffer).

punkte(Mannschaft, 0, 2) :-
    tore(Mannschaft, Treffer, Gegentreffer),
    Treffer < Gegentreffer.

% (f) punkte_verhaeltnis(+Mannschaft, ?Plus, ?Minus)
%     errechnet das das Punkteverhältnis aus allen Spielen einer
%     Mannschaft.

punkte_verhaeltnis(Mannschaft, Plus, Minus) :-
    findall(Plus, punkte(Mannschaft, Plus, _), Pluspunkte),
    sum(Pluspunkte, Plus),
    findall(Minus, punkte(Mannschaft, _, Minus), Minuspunkte),
    sum(Minuspunkte, Minus).

% (g) Man müßte tore/3 und punkte/3 um jeweils eine Argumentstelle für
%     den Spieltag und/oder Spieltyp (heimspiel/auswaerts) erweitern,
%     ebenso für alle darauf aufbauenden Prädikate, die zur Auswertung
%     benötigt werden, und anschließend die findall-Aufrufe in diesen
%     Prädikaten dementsprechend um die Bedingungen erweitern, z.B.

punkte_verhaeltnis_spieltyp(Mannschaft, Plus, Minus, Spieltyp) :-
    findall(Plus, punkte(Mannschaft, Plus, _, Spieltyp), Pluspunkte),
    sum(Pluspunkte, Plus),
    findall(Minus, punkte(Mannschaft, _, Minus, Spieltyp), Minuspunkte),
    sum(Minuspunkte, Minus).

%     wobei punkte/4 aus sechs Regeln der folgenden Form besteht:

punkte(Mannschaft, 2, 0, heimspiel) :-
    spiel(_, Mannschaft, _, Treffer, Gegentreffer),
    Treffer > Gegentreffer.

punkte(Mannschaft, 2, 0, auswaerts) :-
    spiel(_, _, Mannschaft, Gegentreffer, Treffer),
    Treffer > Gegentreffer.

%     Die Eingrenzung auf einen Saisonteil kann besonders elegant
%     erfolgen, wenn man ein Hilfsprädikat definiert wie:

zeitraum(Tag, erste_saisonhaelfte) :- Tag < 18.
zeitraum(Tag, zweite_saisonhaelfte) :- Tag >= 18.
zeitraum(_, ganze_saison).

%     damit können dann Anfragen nach beliebigen Zeiträumen ermöglicht
% 	  werden, wie folgt skizziert:

punkte_verhaeltnis_zeitraum(Mannschaft, Plus, Minus, Zeitraum) :-
    findall(Plus, (punkte_tag(Mannschaft, Plus, _, Plustag),
                   zeitraum(Plustag, Zeitraum)), Pluspunkte),
    sum(Pluspunkte, Plus),
    findall(Minus, (punkte_tag(Mannschaft, Minus, _, Minustag),
                    zeitraum(Minustag, Zeitraum)), Minuspunkte),
    sum(Minuspunkte, Minus).

%---------------------------------------------------------------------
%                            2. Umkodieren
%---------------------------------------------------------------------

% schlage_wort_nach(?Deutsch, ?Englisch, ?Woerterbuch)
% sucht Deutsch/Englisch Wortpaar in Woerterbuch (einer Liste von
% "Paaren", wobei letzteres lt. Aufgabenblatt Listen mit zwei
% Elementen sind).

schlage_wort_nach(Deutsch, Englisch, [[Deutsch, Englisch]|_]).
schlage_wort_nach(Deutsch, Englisch, [_|Woerterbuch]) :-
    schlage_wort_nach(Deutsch, Englisch, Woerterbuch).

% schlage_wort_nach(?Deutsch, ?Englisch)
% benutzt ein vorgegebenes Woerterbuch, um ein Wort nachzuschlagen

schlage_wort_nach(Deutsch, Englisch) :-
    schlage_wort_nach(Deutsch, Englisch,
                      [[hund,dog], [mann,man], [frau,woman], [katze,cat],
                       [die,the], [der,the], [schlaeft,sleeps]]).

% uebersetzung(?Deutsch, ?Englisch)
% kann in beiden Richtungen auf primitive Weise übersetzen, ruft
% einfach auf rekursive Weise auf jedem Wort schlage_wort_nach/2 auf.

uebersetzung([], []).
uebersetzung([DeutschesWort|RestDeutsch],
             [EnglischesWort|RestEnglisch]) :-
    schlage_wort_nach(DeutschesWort, EnglischesWort),
    uebersetzung(RestDeutsch, RestEnglisch).

% Tests zeigen was passiert, wenn mehrer Wörter gleich übersetzt sind;
% es werden einfach alle Alternativen ausgegeben:

% ?- uebersetzung(Deutsch, [the, dog, sleeps]).
% Deutsch = [die, hund, schlaeft] ;
% Deutsch = [der, hund, schlaeft] ;
% No

% Wenn man unbekannte Wörter behandeln will, kann man natuerlich
% einfach einen Fakt hinzufügen, der das Wort unübersetzt läßt:

schlage_wort_nach(Wort, Wort, []).

% Jetzt funktioniert zwar die folgende Anfrage:

% ?- uebersetzung([der, hund, schlaeft, gut], X).
% X = [the, dog, sleeps, gut]

% aber alternative Anfragen führen zu Unglück:
% X = [the, dog, sleeps, gut] ;
% X = [the, dog, schlaeft, gut] ;
% X = [the, hund, sleeps, gut] ;
% X = [the, hund, schlaeft, gut] ;
% ...

%---------------------------------------------------------------------
%                        3. Listenmanipulation
%---------------------------------------------------------------------

% (a) Schreiben Sie zwei Prädikate prefix/2 und suffix/2, die
%     überprüfen, ob eine Liste Anfangs- bzw. Endstück einer zweiten
%     Liste ist.

prefix([], _).
prefix([E|R], [E|X]) :- prefix(R, X).

suffix(X, X).
suffix(S, [_|X]) :- suffix(S, X).

%     Anfragen, bei denen nur der Präfix/Suffix instanziiert sind,
%     terminieren, aber geben nur eine Lösung, bei der die gesamte
%     Restliste durch eine Variable dargestellt wird:

% ?- prefix([a,b,c],X).
% X = [a, b, c|_G232] ;
% No

% (b) Implementieren Sie eine Variante von prefix/2 bzw. suffix/2, bei
%     denen die leere Liste nicht zur Lösungsmenge gehört.

%     Hierfür muß lediglich der Rekursionsabschluß dementsprechend
%     geändert werden:

prefix_nonempty([E], [E|_]).
prefix_nonempty([E|R], [E|X]) :- prefix_nonempty(R, X).

suffix_nonempty([E|R], [E|R]).
suffix_nonempty(S, [_|X]) :- suffix_nonempty(S, X).

% (c) Implementieren Sie eine weitere Variante der beiden Prädikate,
%     die ausschließlich echte Präfixe bzw. Suffixe ermittelt. Echt
%     sei ein Präfix bzw. Suffix einer Liste, wenn es ungleich der
%     Liste selbst ist (vgl. Teilmenge <-> echte Teilmenge).

%     Hierfür muß wiederum lediglich der Rekursionsabschluß so
%     geändert werden, daß die Liste selbst mindestens ein Element
%     mehr als der Präfix/Suffix hat (hier als Varianten der Prädikate
%     aus (b), analog auch für die Originale aus (a) machbar):

real_prefix([E], [E,_|_]).
real_prefix([E|R], [E|X]) :- real_prefix(R, X).

real_suffix([E|R], [_,E|R]).
real_suffix(S, [_|X]) :- real_suffix(S, X).

% (d) Vergleichen Sie Unterschiede und Gemeinsamkeiten zwischen den
%     Prädikaten prefix/2, suffix/2 und append/3. Wie lassen sich die
%     Gemeinsamkeiten bei der Definition der Prädikate ausnutzen?

%     Die Beziehungen können am einfachsten durch die folgenden
%     Prädikatsdefinitionen ausgedrückt werden:

prefix_by_append(Prefix, List) :-
    append(Prefix, _, List).

suffix_by_append(Suffix, List) :-
    append(_, Suffix, List).

%     Diese Prädikatsdefinitionen verhalten sich in jeder Hinsicht wie
%     die einfachsten Prädikate aus (a).

%---------------------------------------------------------------------
%                       4. Häufigkeitswörterbuch
%---------------------------------------------------------------------

haeufigkeiten(Text, Haeufigkeiten) :-
% zuerst benutzen wir flatten, weil uns die verschachtelte
% Struktur der Text-Liste nicht interessiert, im Gegenteil bei der
% Rekursion sogar stört:
    flatten(Text, Wortliste),
% anschließend sortieren wir alle Woerter, damit unsere
% Zählaufgabe sich darauf beschränkt, Sequenzen von direkt
% aufeinanderfolgenden Wörtern zu zählen:
    msort(Wortliste, Woerter),
% jetzt brauchen wir ein Hilfsprädikat, um rekursiv die Liste
% durchzugehen und die Worthäufigkeiten zu bestimmen:
    zaehle_woerter(Woerter, Haeufigkeiten_Roh),
% anschließend ist das Ergebnis noch nach den Wörtern sortiert,
% nicht wie gewünscht zuerst nach den Häufigkeiten, aber das ist
% schnell erledigt:
    sort(Haeufigkeiten_Roh, Haeufigkeiten).

% zaehle_woerter/2 bekommt die sortierte Liste der Wörter und soll
% Sequenzen von gleichen Wörtern zählen. Hierfür verwenden wir ein
% weiteres Hilfsprädikat, das alle aufeinanderfolgenden Vorkommnisse
% des gleichen Wortes zusammenfaßt und rufen dieses rekursiv für jedes
% neue Wort auf. Mit den Ergebnissen des Hilfsprädikats bauen wir die
% Liste mit den Häufigkeiten auf:

zaehle_woerter([], []).
zaehle_woerter(Woerter, [[Anzahl, Wort]|Haeufigkeiten]) :-
    zaehle_wort(Woerter, Wort, Anzahl, Restwoerter),
    zaehle_woerter(Restwoerter, Haeufigkeiten).

% zaehle_wort(Wortliste, Wort, Anzahl, Restliste)
% nimmt das erste Wort aus der Wortliste und zählt die folgenden
% Vorkommnisse des gleichen Wortes. Restliste wird mit dem Suffix der
% Wortliste unifiziert, der bleibt wenn alle Vorkommnisse von <Wort>
% entfernt wurden.

% Rekursionsabschluß (nötig, weil die folgenden Regeln nur auf Listen
% mit mindestens zwei Elementen angewendet werden können)
zaehle_wort([Wort], Wort, 1, []).

% Rekursionsabschluß / Zählen beenden, wenn man auf ein anderes Wort
% trifft (und _nur_ dann):
zaehle_wort([Wort,NaechstesWort|Woerter], Wort, 1, [NaechstesWort|Woerter]) :-
    Wort \= NaechstesWort.

% Rekursion falls Wort noch mehrfach in der Liste - ein Vorkommnis
% wegnehmen und nach diesem Wort weitersuchen/zählen, rekursiv Anzahl
% um einen erhöhen.
zaehle_wort([Wort,Wort|Woerter], Wort, Anzahl, RestWoerter) :-
    zaehle_wort([Wort|Woerter], Wort, Nochanzahl, RestWoerter),
    Anzahl is Nochanzahl + 1.

% Test der Prädikate anhand des "Textes" vom Aufgabenblatt mit Hilfe
% der angegebenen Definition

portray(X) :- write_term(X,[max_depth(30)]).

% und formatiert:

% ?- haeufigkeiten(
% |        [[wenn, hinter, fliegen, fliegen, fliegen, fliegen, fliegen, nach],
% |         [blaukraut, bleibt, blaukraut, und, brautkleid, bleibt, brautkleid],
% |         [wenn, du, denkst, du, denkst, denkst, du, nur, du, denkst]],
% |        Haeufigkeiten).
% 
% Haeufigkeiten = [[1, hinter],
%                  [1, nach],
%                  [1, nur],
%                  [1, und],
%                  [2, blaukraut],
%                  [2, bleibt],
%                  [2, brautkleid],
%                  [2, wenn],
%                  [4, denkst],
%                  [4, du],
%                  [5, fliegen]] ;
%
% No

</pre>