P1-WS04-MusterLoesung07.txt
Zur Navigation springen
Zur Suche springen
% -*-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