C/C++ symbolische Mathematik beibringen...

Jester

Das ist dann allerdings schon ziemlich kompliziert. Vielleicht sollte man erstmal klein Anfangen und den Rechner nach einer vorgegebenen Regelliste arbeiten lassen, wobei er immer die erste, die gerade paßt verwendet. Noch dazu könnte man die Auflösung in mehrere Schritte teilen:

Auf Normalform (was immer das dann auch genau sein mag) bringen
Lösungsverfahren ansetzen

Bashar

Warum sollte ein symbolischer Integrierer dazulernen müssen? Die Integralregeln sind ja nun nicht unbedingt heftig in Bewegung, idealerweise kann er einfach alles.
Ansonsten war das eine rhetorische Frage. Jedes Problem der KI hat die Tendenz, nicht mehr als KI zu gelten, sobald es gelöst ist.

Winn

Jester schrieb:

Vielleicht sollte man erstmal klein Anfangen und den Rechner nach einer vorgegebenen Regelliste arbeiten lassen...

Das sehe ich genauso ! Natürlich kann man C/C++ nichts beibringen, so daß er daraus "Neues" entwickelt... aber symbolisches Rechnen, wie ich es meinte bzw. nachdem ich suche, ist in Maple, Matlab, MathCad, Mathematica usw. schon umgesetzt worden...

Brauche doch keine KI, um C/C++ die "abstrakte (=symbolische)" Matrizenrechnung beizubringen oder allgemeiner lineare Algebra.

BorlandUser

Ich weiß jetzt nicht, ob ich euch so richtig verstanden habe. Aber ein Programm, was aufgrund der gegebenen Gleichung selbst entscheidet, was es damit tun soll, ist natürlich schon eine recht große Herausforderung. Aber wenn Du Dir vorstellst, daß Du mit Gleichung, wie z.B. Dein 'A*(B+C)=A*B+A*C' arbeitest und der PC mit diesen Gleichung ohne Zahlen arbeiten soll, dann würde ich das ganze vielleicht mit einem binären Baum angehen, um die Struktur der eingegebenen Gleichung erst einmal aufzunehmen. Danach müßtest Du eigentlich nur noch Vorgaben erstellen, nach denen diese Gleichung bearbeitet werden soll. Du könntest z.B. sagen, daß alle Klammern aufgelöst werden sollen. Oder man könnte z.B. A*A zu A² machen. Ich habe mal ein Programm für die gesamte Mathematik der Oberstufe geschriebenen. Und mit diesem binären Baum ließ sich das ganze recht angenehm lösen.

Winn

BorlandUser schrieb:

... dann würde ich das ganze vielleicht mit einem binären Baum angehen, um die Struktur der eingegebenen Gleichung erst einmal aufzunehmen...

Ich habe mal ein Programm für die gesamte Mathematik der Oberstufe geschriebenen. Und mit diesem binären Baum ließ sich das ganze recht angenehm lösen.

Das hab ich mir auch schon überlegt, es liegt einfach nahe es in einer Baumstruktur einzugliedern... in welcher Sprache hast Du denn Dein Programm für die Oberstufe geschrieben ? Quellcode ?

BorlandUser

Ich habe es damals in C++ für UNIX und Windows geschrieben. Es war ein wenig schwer es portabel zu bekommen, da ich die lineare Algebra auch mit 3D-Darstellungen veranschaulichen wollte. Lief ganz gut. Ich kann mal nach dem Quellcode schauen. Ist jetzt aber schon einige Zeit her. Und das Programm ist nach meinem Abitur nicht mehr wirklich viel zum Einsatz gekommen. Ich schau aber gerne mal nach. Kann aber etwas dauern und ich kann leider nichts versprechen.

Risch-Algorithmus. Ich kenne aber kein Buch dazu.

Eine große Schwierigkeit ist es auch, jeden Ausdruck auf eine kanonische Form zu bringen (d.h. gleiche Ausrücke auch als gleich zu erkennen.

volkard

Winn schrieb:

Gute Begriffe, Links, Bücher... wenn ihr was wißt, bitte, her damit.

keine ahnung. aber für mich wäre der naheliegende weg, nen lisp-interpreter in c++ zu implementieren (und die klassen würde ich xlisp nennen, wenn es xlisp nicht schon gäbe. vielleicht auch lisp plus plus (tip!)) und den gleichungslöser dann in lisp bauen.

CRIUIX

Matrizen sind was für 3D Spiele. Jede gute Spiele Engine kapselt eine Klasse die mit Matrizen rechnen kann. Aber jede x beliebige Formel lösen, geht nur, wenn die Formel mit vielen vielen case Anweisungen zerlegt und analysiert wird.Für jede Möglichkeit muß dann eine andere Methode aufgerufen werden die das Ganze ausrechnet. Alles nur viel Fleissarbeit. Mathematik ist logisch und so lassen sich auch alle Gesetzte in Programm packen. Aber dafür ist bereits reichlich Anwendersoftware erstellt die auch bestens funktioniert.

Jester

@CRIUIX:

Genau! Und deswegen lernen Informatiker im Studium fast nur 10-FingerSystem, damit sie nachher schnell tippen können! Möglicherweise dann auch in Partnerarbeit, so mit 20 Fingern!

Mal im Ernst: glaubst Du wirklich, daß die sich bei z.B. Maple hingesetzt haben und das ganze mit switch-case analysiert haben und jeden einzelnen Fall einzeln implementiert haben? Nicht? Ich auch nicht. Sowas macht man mit allgemeinen Regeln, die man zum Beispiel in Prädikatenlogik oder ähnlichem kodiert. Die läßt man dann vom Rechner anwenden. Das einzige was man wirklich programmieren muß ist ein kleiner Parser, ein Term-Matcher und einen ordentlichen Suchalgorithmus mit ner guten Heuristik.

MfG Jester

rüdiger

@Jester
ich glaube er weiss einfach absolut nicht wo von er spricht.

Gregor

Jester schrieb:

Mal im Ernst: glaubst Du wirklich, daß die sich bei z.B. Maple hingesetzt haben und das ganze mit switch-case analysiert haben und jeden einzelnen Fall einzeln implementiert haben? Nicht? Ich auch nicht.

Ich auch nicht. Allerdings habe ich vor einiger Zeit festgestellt, dass mir bei so simpel erscheinenden Dingen, wie dem Vereinfachen von mathematischen Termen, einfach keine allgemeine Herangehensweise einfällt. Wie geht man da ran, ohne massenhalft sehr spezielle Regeln aufzustellen, die man dann mit ifs oder ähnlichen Dingen nacheinander abhakt.

Hier mal ein Auszug aus einer Klasse MulFunction, die ich vor längerer Zeit mal geschrieben habe. Ich hoffe, mein Problem (bzw. meine offensichtlich falsche Herangehensweise) wird dadurch klar. Die Klasse ist wäre nach dieser Art natürlich noch lange nicht fertig. Eigentlich müßten da dann noch etliche weitere Regeln rein.

@Override
   public final Function getSimplifiedFunction()
   {
      List<Function> functionList = new LinkedList<Function>();
      for (final Function function : getFunctionList()) functionList.add(function.getSimplifiedFunction());
      functionList = simplifyMulFunctions(functionList);
      functionList = simplifyConstFunctions(functionList);
      functionList = simplifyEqualFunctions(functionList);
      Function tempFunction = simplifyDivisionFunctions(functionList);
      if (tempFunction != null) return tempFunction.getSimplifiedFunction();
      // ToDo
      if (functionList.size() == 0) return ConstFunction.ONE;
      if (functionList.size() == 1) return functionList.get(0);
      return new MulFunction(functionList.toArray(new Function[0]));
   }

   private static List<Function> simplifyConstFunctions(final List<Function> functionList)
   {
      double value = 1.0;
      final Iterator<Function> iterator = functionList.iterator();
      while (iterator.hasNext())
      {
         final Function function = iterator.next();
         if (function instanceof ConstFunction)
         {
            value *= ((ConstFunction)function).getValue(0);
            iterator.remove();
         }
      }
      if(value == 0.0)
      {
         functionList.clear();
         functionList.add(ConstFunction.ZERO);
      }
      if(value != 1.0) functionList.add(ConstFunction.valueOf(value));
      return functionList;
   }

   private static List<Function> simplifyMulFunctions(final List<Function> functionList)
   {
      final List<Function> outList = new LinkedList<Function>();
      for (final Function function : functionList)
      {
         if (function instanceof MulFunction)
         {
            final List<Function> tempFunctions = simplifyMulFunctions(((MulFunction)function).getFunctionList());
            for (final Function tempFunction : tempFunctions) outList.add(tempFunction);
         }
         else
         {
            outList.add(function);
         }
      }
      return outList;
   }

   private static Function simplifyDivisionFunctions(final List<Function> functionList)
   {
      final List<Function> dividendList = new LinkedList<Function>();
      final List<Function> divisorList = new LinkedList<Function>();
      for (final Function function : functionList)
      {
         if (function instanceof DivisionFunction)
         {
            final DivisionFunction divFunction = (DivisionFunction) function;
            dividendList.add(divFunction.getDividend());
            divisorList.add(divFunction.getDivisor());
         }
         else
         {
            dividendList.add(function);
         }
      }
      if(divisorList.size() == 0) return null;
      final MulFunction dividend = new MulFunction(dividendList.toArray(new Function[0]));
      final MulFunction divisor = new MulFunction(divisorList.toArray(new Function[0]));
      return new DivisionFunction(dividend,divisor);
   }

   private static List<Function> simplifyEqualFunctions(final List<Function> functionList)
   {
      final List<Function> outList = new LinkedList<Function>();
      while(functionList.size() != 0)
      {
         Iterator<Function> iterator = functionList.iterator();
         final Function function = iterator.next();
         iterator.remove();
         final List<Function> sumList = new LinkedList<Function>();
         sumList.add(ConstFunction.ONE);
         while (iterator.hasNext())
         {
            final Function currentFunction = iterator.next();
            if (function.equals(currentFunction))
            {
               iterator.remove();
               sumList.add(ConstFunction.ONE);
            }
            else if(currentFunction instanceof PowerFunction)
            {
               final PowerFunction powerFunction = (PowerFunction) currentFunction;
               final Function base = powerFunction.getBase();
               if (function.equals(base))
               {
                  sumList.add(powerFunction.getExponent());
                  iterator.remove();
               }
            }
         }
         final Function[] sumFunctions = sumList.toArray(new Function[0]);
         if (sumFunctions.length > 1)
         {
            outList.add(new PowerFunction(function,new SumFunction(sumFunctions)).getSimplifiedFunction());
         }
         else outList.add(function);
      }
      return outList;
   }

Walli

CRIUIX schrieb:

Mathematik ist logisch und so lassen sich auch alle Gesetzte in Programm packen.

Du solltest dich von der Vorstellung lösen, dass die Mathematik nach den Potenzgesetzen aufhört .

Jester

@Gregor: Kannst Du vielleicht kurz erklären, was die Klasse genau macht? Ich steig ehrlich gesagt nicht so ganz durch.

Mein Ansatz wäre folgender:

m(x,y) ist das Produkt von x,y. Jetzt kann ich in Zum Beispiel Prädikaten logik folgende Axiome formulieren.

Für alle x,y: m(x,y) = m(y,x) // Kommutativität
Für alle x,y,z: m(m(x,y),z) = m(x,m(y,z)) // Assoziativität
Für alle x: x!=0 => m(x,i(x)) = 1 // Inverse
Für alle x: m(x,1) = x // 1 neutral

etc. solche Axiome auch für Addition.

Dann brauchst Du einen Parser, der einen Term in einen solchen Ausdruck umwandelt und eine Funktion, die alle anwendbaren Regeln findet. Damit kannst Du das ganze im Prinzip als Suche auffassen. Du hast Deinen Ausgangspunkt gegeben und Du kennst die möglichen Schritte, also kannst Du nen Suchbaum aufspannen. Was Dir noch fehlt ist ein guter Zieltest, ob Du bereits fertig bist mit vereinfachen, sowie ne gute Heuristik, die sagt welche Schritte Du anwenden solltest. Vielleicht sind Schritte, die die Termlänge verkürzen besser als andere... oder sowas in der Art.
Um auch Konstanten zusammenfassen zu können, könntest Du die Verarbeitung von sowas wie m(4,5) nicht durch den normalen Algorithmus behandeln lassen, sondern duch eine selbsgebaute Funktion, die das ganze einfach ersetzt.

MfG Jester

Gregor

Jester schrieb:

@Gregor: Kannst Du vielleicht kurz erklären, was die Klasse genau macht? Ich steig ehrlich gesagt nicht so ganz durch.

Das ist da ja auch nur ein kleiner Ausschnitt der Klasse.

Bei mir bilden Funktionen so eine Art Baumstruktur. Diese Klasse MulFunction steht hierbei für eine Funktion, die mehrere andere Funktionen miteinander multipliziert, also in etwa so ein Ding:

f(x) = g(x) * h(x) * i(x).

Die kann natürlich oft vereinfach werden. Das einfachste Beispiel wäre, wenn z.B.

h(x) = 0

gelten würde.

Dann würde f(x) zu f(x) = 0 vereinfacht werden. Wenn h(x) stattdessen 1 wäre, dann würde f(x) zu f(x) = g(x) * i(x) vereinfacht werden. Um diese Art von Vereinfachungen geht es mir. Die Art, wie ich es mache, scheint mir sehr aufwändig zu sein. Ich frage mich halt, ob man solche Vereinfachungen nicht irgendwie auf sehr wenige Regeln zurückführen kann. Was wäre zum Beispiel, wenn ich eine Funktion f(x) = sin²(x) + cos²(x) hätte. Muss man da explizit eine Regel angeben, dass das 1 ist, oder kann man das auch eleganter lösen?

Auf der Ebene, auf der ich diese Funktionen (oder Terme) momentan betrachte, gibt es einfach viel zu viele Regeln, die zu einem unglaublich riesigen, schlecht wartbaren Codeberg führen würden, wenn man die konsequent alle einprogrammiert.

Eine zweite Sache ist die Repräsentation von solchen Regeln. Wie macht man das und wo macht man das am Besten. Java scheint mir nicht gerade eine ideale Sprache zu sein, um solche Regeln damit zu repräsentieren. ...C++ genausowenig. Welche Sprache wäre dafür geeignet? Prolog? ...oder sollte man die zur Laufzeit zum Beispiel aus einer XML-Datei oder so in eine geeignete Datenstruktur einlesen und damit arbeiten?

Walli

Also ich denke Prolog wäre sehr geeignet um solche Regeln zu formulieren. Es gibt meines Wissens auch eine Schnittstelle zwischen Prolog und C++.

Jester

Ja, Prolog könnte eine Lösung sein. Ich weiß aber nicht, wie gut Prolog mit Gleichheiten umgehen kann. Die sind in der Logik grundsätzlich etwas eklig, weil sie nicht so schön mit sich Arbeiten lassen, wie Implikationen. Man hat grundsätzlich 2 Richtungen, und dadurch, daß sich die ganzen Funktionsausdrücke schachteln lassen erhält man stets einen unendlich großen Suchraum.

Zum Ausdrücken der Regeln eignet sich wie gesagt die Prädikatenlogik sehr gut. Allerdings wirste auf Grund der oben genannten Probleme ne gute Heuristik brauchen, nach der Du die Regeln anwendest, sonst wird der Suchraum zu groß.
Die Variablen x,y,z müssen keine einzelnen Zahlen sein, sondern können selbst wieder komplexe Ausdrücke sein.

Eine Möglichkeit wäre, die Gleicheiten nur von links nach rechts zuzulassen. Das ist wohl die häufigste Benutzung. Leider muß man dann manche Sachen explizit angeben:

Zum Beispiel beim ausklammern:

Für alle x,y,z:
add(mul(x,y),mul(x,z)) = mul(x,add(y,z))

Man beachte, daß aufgrund der Kommutativität der Beweiser jetzt schon ganz allegemein ausklammern kann. Er muß nur auf die Idee kommen alles nach vorne zu schieben was gemeinsam ist.

wenn wir jetzt m(x,1) = x nur von rechts nach links verwenden, dann kann der Beweiser add(x,x) nicht vereinfachen. Lassen wir auch die andere Richtung zu, so kann er daraus add(m(x,1),m(x,1)) machen und daraus m(x,add(1,1)) machen und daraus dann mit Hilfe einer speziellen Rechenprozedur außerhalb der Prädikaten logik mul(x,2).

Der Vorteil der Darstellung in Prädikatenlogik ist, daß man auch Aussagen über Funktionen treffen kann, die nicht definiert sind:

Für alle x: sin(add(x,mul(2,Pi))) = sin(x) besagt, daß sin 2Pi periodisch ist. Die Additionstheoreme kann man genauso einfach angeben und schon kann er mit sin+cos rechnen. Ein paar Axiome zu exp und dann kann er das auch.

Weiterhin ist es problematisch die richtigen Einsetzungen in die Regeln zu finden:

mul(add(mul(a,a),neg(mul(b,b)), i(add(a,b))

das ist (a^2-b2)/(a+b)

wenn der Computer jetzt auf die Idee käme ein paar Axiome anzuwenden, wie:

(I) für alle x: add(x,0) = x
(II) für alle x: add(x,neg(x)) = 0

dann könnte er daraus folgendes machen:
(I) => mul(add(add(mul(a,a),neg(mul(b,b)), 0), i(add(a,b))
(II) => mul(add(add(mul(a,a),neg(mul(b,b)),add(mul(a,b),neg(mul(a,b)), i(add(a,b))

Das heißt: a^2-b2 = a^2-b2 + 0 = a^2-b2 + ab - ab jetzt das Kommutativ und assoziativgesetz der Addition:

a^2+ab - ab - b^2 jetzt bemerkt er, daß sein Distributgesetz greift:
a(a+b) - b(a+b)
jetzt noch a+b ausklammern und fertig.
Nur, wie kommt der Rechner auf die Idee? Wenn man ihm so viel Zeit läßt diesen Weg zu finden, dann braucht man entweder ne sehr gute Heuristik, die dem Rechner sagt: da gibt's was zu holen, oder alternativ kann man natürlich auch einfach die binomischen Formeln in Prädikatenlogik formulieren. Das ist zwar redundant, aber effektiv und spart dem Rechner das raten welche Variablen er dazu erfinden muß.

In vielen Fällen ist das wohl einfacher.
Man kann leicht zeigen, daß für alle x: x= i(i(x))

x = mul(x,1) = mul(x, mul(i(x), i(i(x)) = mul(mul(x,i(x)), i(i(x)) = mul(1,i(i(x)) = i(i(x)), aber der Rechner würde wahrscheinlich lange brauchen. Also geben wir ihm vielleicht auch noch diese Info. Ähnlich ist es mit für alle x: mul(0,x) = 0.

Dennoch kann man mit einer ausreichend großen Regelmenge gute Ergebnisse erreichen.

MfG Jester

volkard

zuerst hat mich ein lehrer gelernt, daß ich (a+b)^2 immer zu a^2+2ab+b2 vereinfachen soll. binomische formel heißt das.
und kaum drei jahre später (oder waren es eher 10?) meint einer, ich solle a^2+2ab+b2 zu (a+b)^2 vereinfachen.
ja, was denn nu? und wie soll ich dem bot was beibringen, was ich selber nicht weiß?
soll ein matheprogramm zu a^2+2ab+b2 oder zu (a+b)^2 vereinfachen?

Jester

Ich finde (a+b)^2 schöner. Eben, weil man da auch (a+b) kürzen kann. Ein Schritt, der einem sonst durch die Lappen geht. Aber man muß natürlich irgendwie definieren, wann ein Term einfacher ist als ein anderer.

MfG Jester