Wie funktioniert dieser deduktive Algorithmus aus der Informatik?
Hallo, ich habe folgende Aufgabe bekommen und mir ist nicht klar wie sie zu lösen ist:
Gegeben seien ein Fakt und eine Regel eines deduktiven Algorithmus (für natürliche Zahlen X und Y) wie folgt:
f(0,1).
X>0 AND f(X-1,Y) -> f(X,2*Y).Was sind die Ergebnisse der Anfragen:
f(X,64)?
f(X,67)?
f(3,Y)?Danke schonmal für Lösungen und Tipps dazu.
1 Antwort
Ich verstehe die Aufgabe so, dass zunächst nur für f(0,1) gesichert WAHR gilt.
In der zweiten Zeile soll dann für alle Paare (X, Y) mit X>0 geprüft werden, ob f(X, 2Y) WAHR ist. Hier wird also nicht direkt f(X,Y) ermittelt; dann könnte man die Formel ja sofort rekursiv auflösen.
Lösung mit Stift und Papier:
Wenn die Regel komplexer wäre oder mehr davon vorhanden wären, könnten auch Elemente benötigt werden, für die noch kein WAHR oder FALSCH berechnet wurde, dann würde das schnell unübersichtlich.
Allerdings wird in diesem Algorithmus nur auf Ergebnisse mit kleinerem X zugegriffen als aktuell betrachtet wird, und die Zahlenpaare stehen außerdem in einem festen Zusammenhang.
Ich empfehle dir deshalb, gezielt f(X,2Y) zu konstruieren, die die Bedingungen der linken Seite erfüllen. Du erkennst schnell ein Muster.
Lösung per Programm:
Mit einer der üblichen Sprachen kannst du so darangehen, dass ein zweidimensionales Array für f(X,Y) oder eine Menge initialisiert wird und das Programm immer wieder alle X, Y innerhalb bestimmter Grenzen durchgeht. Im Array würde an den entsprechenden Koordinaten WAHR oder ein Marker gesetzt, wenn f(X,Y) als WAHR erkannt wurde, bzw. der Menge würden entsprechende Paare (X,Y) hinzugefügt. Das müsste dann so lange durchgeführt werden, bis sich in einem Durchlauf keine Änderungen, d.h. neu hinzukommende f(X,Y) mit WAHR, mehr ergeben. Du sammelst also sukzessive alle f(X,Y) mit WAHR ein; Kandidaten für f(X,Y), die sich nach dem letzten Durchlauf (demjenigen, in dem sich keine Änderungen mehr ergaben) nicht in der Menge befinden bzw. auf deren Koordinaten im Array nicht der Wert WAHR steht, müssen FALSCH (bzw. UNDEFINIERT oder ein anderer Defaultwert) sein.
Leider weiß ich nicht, was bei deduktiven Algorithmen üblicherweise als Ausgabe erwartet wird:
- Wenn f(0,0) nicht als WAHR bewiesen werden kann, wird vermutlich FALSCH als Ausgabe erwartet, und wenn die Frage nach f(0,1) gestellt wird, wird dann vermutlich WAHR ausgegeben, weil das ja sogar schon so definiert ist. Soweit ist mir das noch klar.
- Wenn f(0,1) das einzige Paar mit X=0 ist, das WAHR ist, könnte für die Anfrage f(0,Y) aber entweder die Ausgabe WAHR erwartet werden (da sich das lösen lässt mit Y=1), oder es soll direkt Y=1 ausgegeben werden, damit dem Benutzer außer der Lösbarkeit an sich auch der dazu notwendige Parameter bekanntgegeben wird?
- Was soll für f(0,Y) ausgegeben werden, wenn ein anderes Paar, sagen wir f(0,999), ebenfalls WAHR wäre? Eine Liste wie "WAHR, Y=1, Y=999"?
Danke für die ausführliche und schnelle Antwort, hat mir auf jeden Fall weitergeholfen.