Benutzer-Werkzeuge

Webseiten-Werkzeuge


kuenstliche_intelligenz_und_logische_programmierung

Aufgabentext

GK Informatik - Mecklenburg-Vorpommern 2003

1. Fakten und Regeln

Peter isst gerne Äpfel, Sandra Hamburger und Ines Bananen. Bananen und Äpfel sind Früchte. Wer Früchte isst, lebt gesund!
Formulieren Sie diese Aussagen als Fakten mit dem zweistelligen Prädikat isst, dem einstelligen Prädikat frucht und einer einstelligen Regel gesund.

2. Unifikation

2.1 Nennen Sie Bedingungen für die Unifizierbarkeit von Termen.
2.2 Sind folgende Terme unifizierbar? Begründen Sie Ihre Entscheidung.
a) tee = cola.
b) trinken(tee) = X.
c) trinken(tee,X) = trinken(Y,cola).
d) [frank|Rest] = [frank,trinkt,cola].
e) [frank,Rest] = [frank,trinkt,cola].

3. Kryptogramme Diese Aufgabe ist am PC zu lösen. Bewertet werden die Lauffähigkeit und die geforderten Details des Quelltextes. Falls aus irgendwelchen Gründen (z. B. Arbeitszeitprobleme) das Testen von Programmteilen nicht gelingt, sollten in geeigneter Form der vorgesehene Programmablauf und gegebenenfalls auch die erkannten Ursachen für die „Nichtlauffähigkeit“ aufgeschrieben werden.

3.1 Es soll das folgende Kryptogramm mit dem Computer gelöst werden. Dabei werden die Buchstaben durch Ziffern ersetzt. Verschiedene Buchstaben sollen verschiedenen Ziffern entsprechen und somit zu einer korrekten Lösung führen. (Kein Operator angegeben, Erstellen)

    H A U S
 +  H A U S
 ----------
  S T A D T

3.2 Erläutern Sie, wodurch sich effiziente Lösungen der Kryptogramme von weniger effizienten unterscheiden.

4. Rekursion

Gegeben ist das folgende PROLOG-Programm:

 loesung(A,B,C) :- A == B, C is A.
 loesung(A,B,C) :- A > B, D is A-B, loesung(D,B,C).
 loesung(A,B,C) :- A < B, D is B-A, loesung(A,D,C).

4.1 Begründen Sie, dass das gegebene PROLOG-Programm rekursiv ist.
4.2 Erläutern Sie schrittweise den Programmablauf bis zur Ausgabe des Ergebnisses bei der Anfrage loesung(8,4,C).
4.3 Vereinfachen Sie die erste Regel.

Lösungen

1. Fakten und Regeln

 isst(peter,aepfel).
 isst(sandra,hamburger).
 isst(ines,bananen).
 frucht(aepfel).
 frucht(bananen).
 gesund(Person):-isst(Person,Essen),frucht(Essen).

2. Unifikation

2.1 Terme sind unifizierbar, wenn sie

  1. identisch sind oder
  2. bis auf verschiedennamige Variablen identisch sind und diese Variablen innerhalb einer Klausel
  • so gebunden werden können, dass die Terme nach der Bindung identisch sind oder
  • bereits so gebunden sind, dass kein Unterschied zwischen den Termen besteht. (Das heißt: Zwei Terme sind unfizierbar, wenn sie aufgrund einer möglichen (gefundenen) Variablensubstitution identisch sind.)

2.2 a) nein, da nicht identische Terme
b) ja, {X/trinken(tee)}
c) ja, {X/cola, Y/tee}
d) ja, {Rest/[trinkt,cola]}
e) nein, da die Unifikation fehlschlägt, weil links zwei und rechts drei Elemente stehen und diese Listen eine fixe Länge haben.

3. Kryptogramme

 ziffer(0). ziffer(1). ziffer(2). ziffer(3).
 ziffer(4). ziffer(5). ziffer(6). ziffer(7).
 ziffer(8). ziffer(9).
 loesung:-
   ziffer(S),T is (S+S) mod 10, U1 is (S+S)//10,T\=S,
   ziffer(U),D is (U+U+U1) mod 10,U2 is (U+U+U1)//10,
   S\=D,T\=D,
   ziffer(A), A is (A+A+U2) mod 10, U3 is (A+A+U2)//10,
   U\=A,D\=A,S\=A,T\=A,
   ziffer(H),T is (H+H+U3) mod 10, U4 is (H+H+U3)//10,
   H\=A,H\=D,U\=H,U\=T,S\=H,T\=H,
   S is U4,
   write('Die Loesung lautet:'),nl,
   write(' '),write(H),write(A),write(U),write(S),nl,
   write('+ '),write(H),write(A),write(U),write(S),nl,
   write('------'),nl,
   write(' '),
   write(S),write(T),write(A),write(D),write(T).

Bildschirmausgabe:

 Die Loesung lautet:
   6041
 + 6041
 ------
  12082

3.2 Eine effiziente Lösung beginnt keinesfalls damit, zunächst die Variablen der Reihe nach mit allen verschiedenen Ziffern zu belegen. Es sollten besser für die Belegung einer weiteren Variablen die “vorgegebenen“ Verknüpfungen von bereits gebundenen Variablen genutzt werden. Zum Beispiel wird T eindeutig durch S bestimmt. Somit ist es überflüssig, alle möglichen Belegungen von S unabhängig von der jeweils aktuellen Bindung von T zu prüfen.

4. Rekursion

4.1 Definition einer Funktion oder eines Verfahrens durch sich selbst

4.2 loesung(8, 4, C).
Überprüfung der 1. Bedingung 8 == 4, nicht erfüllt
Überprüfung der 2. Bedingung 8 > 4, erfüllt
Berechnung D is 8-4
D = 4
Aufruf: loesung(4, 4, C).
Überprüfung der 1. Bedingung 4 == 4, erfüllt
Ausgabe: C = 4

4.3 loesung(A, A, A).

kuenstliche_intelligenz_und_logische_programmierung.txt · Zuletzt geändert: 2014/09/01 14:48 von admin