Logik-Rätsel maschinell lösen

knivil

Mechanics schrieb:

Prolog. Da ist sowas schon optimiert.

Du erwartest zu viel von Prolog.

SeppJ

Antoras schrieb:

Der von dir genannte Algo kann doch aber nur eingesetzt werden, wenn bekannt ist ob eine Kugel schwerer oder leichter ist. Ich sehe aber nicht wie ich das bei meinem Problem herausbekomme. Ich möchte ja Wiegevorgänge vorgeben, die ich zwar analysieren kann, aber mit denen ich doch niemals genau herausbekomme was für ein Gewicht eine Kugel hat.

Das ist doch genau deine Problembeschreibung, die du im ersten Beitrag gegeben hast.

Darum geht es um mehrere Kugeln, die bis auf eine alle das gleiche Gewicht haben und man nur mit Hilfe einer Waage herausfinden soll welche dies ist.

Genau dieses Problem habe ich angegangen. Bei meiner Lösung muss man niemals das genaue Gewicht der Fehlkugel kennen, es läuft alles über Vergleiche. Man bekommt das Gewicht auch gar nicht heraus, man bekommt nur heraus, welche Kugel nicht passt und (für große Kugelmengen), ob sie schwerer oder leichter als die anderen ist.

314159265358979

SeppJ, du solltest cooky antworten.

SeppJ

314159265358979 schrieb:

SeppJ, du solltest cooky antworten.

cooky451 schrieb:

@SeppJ
Wie könnte man ein solches Problem in eine Formale Sprache (in ein Kalkül?) überführen, also wie könnte das aussehen? Jetzt haste mich ein bisschen neugierig gemacht, aber so konkrete Dinge findet man nicht im Netz.

Keine Ahnung, bin kein Informatiker. Ich dachte mir nur, dass das damit sicherlich möglich ist, da ich weiß, dass es existiert und zu so etwas gut ist.

Ich war jedenfalls schwer begeistert, als neulich jemand nach KI für allgemeine Spiele gefragt hat und ich mir erst einmal durchgelesen habe, wie man überhaupt Spielregeln so allgemein formulieren kann, dass man damit sowohl Schach als auch Poker beschreiben kann.
Hier ist der Thread:
http://www.c-plusplus.net/forum/303054

cooky451

SeppJ schrieb:

Keine Ahnung, bin kein Informatiker. Ich dachte mir nur, dass das damit sicherlich möglich ist, da ich weiß, dass es existiert und zu so etwas gut ist.

Hm.. schade, vielleicht findet sich ja noch jemand. Von Wikipedia kann ich ableiten, wie man ein Alphabet und eine Grammatik aufstellt, über Axiome Sätze wie "es gibt ein x, sodass gilt blubb" aufstellen kann, daraus über Ableitungsregeln wieder neue Sätze bilden kann, aber wie man ein Problem formal formuliert, das würde mich ja wirklich interessieren. Wobei Spielregeln bei denen man gewinnen und verlieren kann ist doch quasi das Gleiche, das gucke ich mir mal an.

volkard

cooky451 schrieb:

SeppJ schrieb:

Keine Ahnung, bin kein Informatiker. Ich dachte mir nur, dass das damit sicherlich möglich ist, da ich weiß, dass es existiert und zu so etwas gut ist.

Hm.. schade, vielleicht findet sich ja noch jemand. Von Wikipedia kann ich ableiten, wie man ein Alphabet und eine Grammatik aufstellt, über Axiome Sätze wie "es gibt ein x, sodass gilt blubb" aufstellen kann, daraus über Ableitungsregeln wieder neue Sätze bilden kann, aber wie man ein Problem formal formuliert, das würde mich ja wirklich interessieren. Wobei Spielregeln bei denen man gewinnen und verlieren kann ist doch quasi das Gleiche, das gucke ich mir mal an.

Ähm. Du möchtest "Gödel Escher Bach" lesen.

Antoras

@SeppJ

SeppJ schrieb:

Um herauszufinden, ob die Fehlkugel schwerer oder leichter ist, vergleichst du zuerst die eine Hälfte der Kugeln mit der anderen. Dann nimmst du die schwerere Hälfte und vergleichst wieder zwei Hälften von dieser Hälfte.

Der erste Satz ist so weit ok. Am Beispiel 3,4,2 > 1,7,6 würde man rechts mit links vergleichen. Ich sehe jetzt nicht wie ich die schwere Hälfte unterteilen kann und wieder herausbekomme wie das Verhältnis zueinander ist. Woher kommt die Information wie 3,4,2 zueinander stehen? Die muss ich doch erst anhand der anderen Beispiele ermitteln. Oder habe ich deine Idee jetzt falsch verstanden?

Das Problem musst du selbst formulieren (in Prolog üblicherweise als Menge von Hornklauseln repräsentiert). Die Logik-Kalküle können dir dann Auskunft über Erfüllbarkeit etc. geben. Dazu gibt's auch einiges an Literatur ("Logik für Informatiker" von Schöning (bzw. Martin Kreuzer unter dem gleichen Titel)

Der Tipp von volkard ist überdies sehr nützlich (wenngleich ich das Buch in Teilen unnötig aufgebläht gefunden habe).

knivil

cooky451 schrieb:

z.B. für 9 Kugeln:

a = {1, 2, 3}, b = {4, 5, 6}, c = {7, 8, 9}

a != b
a == c

4 != 5
4 != 6

-> 4

Das ganze Ding nennt sich constraint programming. a,b,c sind deine Domains, gefolgt von den Nebenbedingungen. Geschicktes Suchen in Algorithmenform fuehrt dann zur Loesung.

Wobei Spielregeln bei denen man gewinnen und verlieren kann ist doch quasi das Gleiche, das gucke ich mir mal an.

Habe in meinem Seminar/Praktikum/whatever: General Game Playing http://www.eclipseclp.org/ benutzt, geht ganz gut. Nach diesen Stichworten im Netzt einfach suchen.

volkard

JFB schrieb:

Der Tipp von volkard ist überdies sehr nützlich (wenngleich ich das Buch in Teilen unnötig aufgebläht gefunden habe).

Ich habe geschwelgt. Und gelernt. Viel. Grandios…
Und erst die Hälfte kapiert. me silly.

Ist aber definitiv kein Nachschlagewerk, was im Schrank stehen muss. Hälfte reicht ja. Vielleicht sollten wir einen GEB-Pool bilden. Man liest es meist nicht zweimal, fürchte ich. Und falls doch, kann man es ja nochmal ordern.
JFB hat anscheinend eins frei. Da ist es nur noch eine Sache des Portos.

Ich mag mich noch noch trennen, weil es so geil war, und ich es eigentlich am nächsten Wochenende wieder anfangen will, und dann am nächsten, am nächsten, ein endloses Band.

edit: Vielleicht auch einen größeren Pool. TAOCP muß man auch lesen aber nicht stehen haben.

nachtfeuer

volkard schrieb:

Ich habe geschwelgt. Und gelernt. Viel. Grandios…
Und erst die Hälfte kapiert. me silly.

Ist aber definitiv kein Nachschlagewerk, was im Schrank stehen muss. Hälfte reicht ja. Vielleicht sollten wir einen GEB-Pool bilden. Man liest es meist nicht zweimal, fürchte ich. Und falls doch, kann man es ja nochmal ordern.
JFB hat anscheinend eins frei. Da ist es nur noch eine Sache des Portos.

Ich mag mich noch noch trennen, weil es so geil war, und ich es eigentlich am nächsten Wochenende wieder anfangen will, und dann am nächsten, am nächsten, ein endloses Band.

Man kann es eigentlich auch beim Buchhändler um die Ecke bestellen, und am nächsten Tag abholen, die haben ja Großhändler wie z.B. http://www.libri.de/shop/action/productDetails/1339897/douglas_r_hofstadter_goedel_escher_bach_ein_endloses_geflochtenes_band_3423300175.html

Als ich das Buch das erste mal durchgesehen hatte, fand ich es gar nicht so prickelnd. Das lag aber hauptsächlich an dem KI-Teil, die Bilder vom Escher kannte ich zur Genüge und Gödel hatte ich damals eh schon ganz intuitiv verstanden, das war nur eine formale Bestätigung, nichts wirklich neues. Aber die Art und Weise, wie Gödel an den Beweis heran ging, war, schon beeindruckend.

..und irgendwo ist auch wieder klar, dass so vieles auf die Arbeiten von Cantor zurückgeht, und das ist irgendwie schade, dass solche Bücher wie gesammelte Aufsätze von Cantor nicht aktuell bleiben (weil sie so grundlegend und einflußreich sind und didaktisch möglicherweise auch verständlicher, da ja original (mit etwas Glück).

Man könnte sich natürlich auch extra Logik-Bücher besorgen, wie
http://www.amazon.de/Einführung-mathematische-Logik-Moderne-Mathematik/dp/3525405405/
http://www.amazon.de/Haskell-Logic-Maths-Programming-Computing/dp/0954300696/

Und ein neueres Buch von Format ist sicher auch das hier:
http://www.amazon.de/Grenzen-Mathematik-Reise-Kerngebiete-mathematischen/dp/382742559X/
(oder das hier? )
http://www.amazon.de/Das-Geheimnis-transzendenten-Zahlen-Einführung/dp/3827422744/
(hmm...oder doch dann lieber sowas hier, ganz allgemeiner Natur..)
http://www.amazon.de/Die-Entdeckung-Unteilbaren-Quanten-Quarks/dp/3827424844/
(wäre dann aber gar nicht mehr so richtig logisch? nachvollziehbar? Kirre?

cooky451

Hm.. Bücher zur Logik, interessant. Was ist denn eine typische Fragestellung der Logik, wenn eine typische Frage der Mathematik wäre, ein x zu finden, das die Gleichung x + 1 = 3 erfüllt?

nachtfeuer

cooky451 schrieb:

Hm.. Bücher zur Logik, interessant. Was ist denn eine typische Fragestellung der Logik, wenn eine typische Frage der Mathematik wäre, ein x zu finden, das die Gleichung x + 1 = 3 erfüllt?

Ob das auch wirklich wahr ist, und das mit Sicherheit und welcher Sicherheit und unter welchen Bedingungen. Wahrheiten, die wir auswendig kennen, oder fleißig geübt haben, stehen erstmal im Zweifel.
Wie wäre es z.B. mit x + 5 = 3? Auch nicht unmöglich. Und versuch mal x + 3 mit Binärzahlen, die kennen gar keine 3.
Auf welche Zahlenmenge bezieht sich deine Aussage, auf welche kann man sie anwenden?
Warum sollte 1 + 1 = 2 sein?

Und...gibt es die Menge aller Mengen oder nicht?

cooky451

Also Fragestellungen wie warum 1 + 1 = 2 sind würde ich erstmal als trivial ansehen, genau so wie den Rest den du geschrieben hast. Das legt doch die Grammatik bereits fest. Ob 2 jetzt 2 oder 10 oder was auch immer ist, interessiert doch gar nicht. Dass es das Ergebnis von 1 + 1 gibt, das mag weniger trivial sein, bzw. dass jede Addition mit natürlichen Zahlen wieder eine natürliche Zahl ergibt.

nachtfeuer schrieb:

Und...gibt es die Menge aller Mengen oder nicht?

Hehe, das war dann die einzig interessante Frage. Hatten wir aber schon mal. Wie war das? Für jedes Element soll entscheidbar sein, ob eine Menge es enthält oder nicht. Bei der Menge die alle Mengen enthält, die nicht sich selbst enthalten, ist somit nicht entscheidbar ob sie sich selbst enthält oder nicht. Daher müssen wir entweder festlegen, dass alle Mengen sich enthalten, oder dass keine Menge sich selbst enthalten darf. Und weil die Mathematiker zu faul sind immer Ausnahmeregelungen zu basteln, nimmt man letzteres. Und daher gibt es auch nicht die Menge aller Mengen. Joa, ich hoffe ich habe das noch halbwegs zusammen bekommen.

Aber das Beispiel mit x + 1 = 3 war absichtlich gewählt. Es scheint natürlich trivial, und das war gewollt. Ein Algorithmus könnte solche Aufgaben lösen, nicht aber ein (einfacher) Taschenrechner. Daher habe ich mich gefragt, ob es genau solche Probleme auch in der Logik gibt, und wie diese formuliert werden.

hustbaer

cooky451 schrieb:

Hm.. Bücher zur Logik, interessant. Was ist denn eine typische Fragestellung der Logik, wenn eine typische Frage der Mathematik wäre, ein x zu finden, das die Gleichung x + 1 = 3 erfüllt?

Ich würde "Wem gehört der Fisch?" als klassische Logik-Aufgabe ansehen.

SeppJ

Antoras schrieb:

@SeppJ

SeppJ schrieb:

Um herauszufinden, ob die Fehlkugel schwerer oder leichter ist, vergleichst du zuerst die eine Hälfte der Kugeln mit der anderen. Dann nimmst du die schwerere Hälfte und vergleichst wieder zwei Hälften von dieser Hälfte.

Der erste Satz ist so weit ok. Am Beispiel 3,4,2 > 1,7,6 würde man rechts mit links vergleichen. Ich sehe jetzt nicht wie ich die schwere Hälfte unterteilen kann und wieder herausbekomme wie das Verhältnis zueinander ist. Woher kommt die Information wie 3,4,2 zueinander stehen? Die muss ich doch erst anhand der anderen Beispiele ermitteln. Oder habe ich deine Idee jetzt falsch verstanden?

Ok, nehmen wir dein Kugelbeispiel, die 4. Kugel ist leichter. Ich erweitere es sogar auf 16 Kugeln, damit wir uns die Sonderbehandlung von N ungerade ersparen und damit man wenigstens mal sieht, dass das Verfahren effizient ist.
Ich wiege:
1,2,3,4,5,6,7,8 : 9,A,B,C,D,E,F,G.
zweite Hälfte ist schwerer. Schlussfolgerung: Noch keine, aber die Information ist später nützlich.
Ich wiege:
9,A,B,C : D,E,F,G
beide gleich schwer. Schlussfolgerung: die Fehlkugel ist leichter als die anderen und sie ist in 1-8.
Ich wiege:
1,2,3 : 6,7,8
beide gleich schwer. Schlussfolgerung: Die Fehlkugel ist in 4,5
Ich wiege:
4 : 5
zweite Hälfte ist schwerer. Schlussfolgerung: Die Fehlkugel ist 4.

Auf dein altes Beispiel übertragen (1-7) ist die Methode sogar trivial:
Ich wiege:
1,2,3 : 5,6,7
beide gleich schwer. Schlussfolgerung: Die Fehlkugel ist 4.

Ein bisschen modifiziert, die Fehlkugel sei 5 und sie sei leichter. Dann geht mein Algortihmus:
Ich wiege:
1,2,3 : 5,6,7
erste Hälfte ist schwerer. Schlussfolgerung: 4 ist keine Fehlkugel
Ich wiege:
1 : 3
beide gleich schwer: Schlussfolgerung: 1,3 sind keine Fehlkugeln
ich wiege:
2 : 3
beide gleich schwer: Schlussfolgerung: 2 ist keine Fehlkugel und die Fehlkugel ist leichter als die anderen.
Ich wiege:
5 : 7
zweite Hälfte ist schwerer: Schlussfolgerung: 5 ist die Fehlkugel.

Hier sieht man, dass mein Algorithmus für kleine N leicht umständlich werden kann.

@volkard: Ja, die erste Hälfte war ein Erlebnis. Aber irgendwann verliert sich der Autor IMHO einfach in einer Unmenge von (mal mehr, mal weniger passenden) Analogien und Querbezügen, sodass es fürchterlich schwer wird, irgendwie seinem Punkt noch zu folgen (auch das ironischerweise eine seltsame Art der Selbstbezüglichkeit ;))

cooky451

hustbaer schrieb:

Ich würde "Wem gehört der Fisch?" als klassische Logik-Aufgabe ansehen.

Ne, da hast du etwas nicht verstanden. Die Frage ist generell nicht zu beantworten, du hast das wohl mit "Wie teuer ist der Fisch?" verwechselt. :p

hustbaer

Also ich meine das da
http://de.wikipedia.org/wiki/Zebrar�tsel

Wobei ich Fisch statt Zebra in Erinnerung hatte.
Und wieso soll das nicht zu beantworten sein?