C/C++ symbolische Mathematik beibringen...

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

ths

@Jester & Gregor:
Die Sache mit der Prädikatenlogik hört sich bis hierher gut an

Obwohl ich jetzt, beim ersten flüchtigen durchlesen des Threads, nicht
ganz hinter die Logik steige. Ich werde mir die Beiträge nochmal durchlesen
müssen

Aber:
Geht das mit der Prädikatenlogik bis zum Letzten? Also ich denke jetzt mal
an meine Mathematik I + II Vorlesungen. Alleine schon die recht einfache
Integration und Differentiation über eine Veränderliche ist "harter Tobak".

Ich meine: Man kann ihm sagen:
Das ist die Kettenregel, dass die Summenregel etc.

Das ist noch kein Problem. Aber wenn es dann um die partielle Integration
geht, oder die Integration durch Substitution etc.

Das Programm muss ja selbst erkennen, wann es durch Substitution Integriert,
und wann durch partielle Integration oder in welchen Fällen lieber elementar.

Aber wenn so ein Programm an Mathematica oder Maple heran kommen soll, muss
man noch viel viel mehr können:

Wie sieht es mit Integration von mehreren Veränderlichen aus? Da fängt der
Spaß doch erst an :p Kurvenintegrale, Oberflächenintegrale, Volumenintegrale,
Bereichsintegrale etc. pp.

Differentialgleichungen n-ter Ordnung

Da gibt es zum Beispiel den speziellen Funktionsansatz für die inhomogene
Lösung einer Differentialgleichung 2. Ordnung. Das ist ne Tabelle zum
nachschlagen. Soll das Programm die Tabelle beinhalten? Wohl eher nicht...

Dann muss man dem Programm den Differentialoperator beibringen. Wenn es
das kann, kann man Taylerreihenentwicklung mit mehreren Veränderlichen
durchführen.

Fourierreihenentwicklung ist auch nicht ohne Wie kann die Software
die Sonderfälle erkennen, wie gerade / ungerade Funktion? Okay, dass
könnte sie ja schon. Alternierende Funktionen erkennen... hmmm.

Wie sieht es mit komplexen Zahlen aus? Das müsste die Software schaffen,
wenn sie das i bzw. j kapiert hat. Okay, dann braucht man aber auch
eine Erkennung, wann die Software in die Exponentialform wechselt.
Also sobald andere Operationen als Addition oder Subtraktion auftauchen,
immer in die Exponentialform gehen...

Aber wie will man Sachen erkennen, wie die Vereinfachungen bei der
Integration mehrerer Veränderlicher? Die Koordinatentransformation zum Beispiel.
Wie soll die Software erkennen, dass der zu berechnende Körper eine
Zylinderform hat? Dann muss sie nämlich eine Koordinatentransformation
in die Zylinderkoordinaten durchführen etc.

Das ist alles ne Menge Arbeit. Ich hatte auch schonmal die Idee, sowas
zu programmieren (in Java). Aber bei den Überlegungen kommt man zu vielen
Problemen.

Aber wie gesagt: Prädikatenlogik hört sich zumindest für den einfachen
Teil der Mathematik gut an.

Ich hatte natürlich auch schonmal nachgeforscht, wie das Andere machen.
Ich habe einen interessanten Ansatz der FH Wedel gefunden:
http://www.fh-wedel.de/~si/praktika/MultimediaProjekte/MathApplet/doc/umsetzung.html

Das wäre doch ne gute Idee.

So ein Programm wäre dann sogar ziemlich übersichtlich! Man hätte ja eine
Klasse pro Operator. Und das scheint ja auch zu funktionieren

Wäre ein schönes Projekt. Wollt ihr das wirklich programmieren? Wäre ja
cool

Da gibt es auch noch andere Probleme:
Die Formelzeichen müssen dynamisch gezeichent werden. Ein Wurzelzeichen
muss sich dem Ausdruck anpassen. Man muss Integrale unter Bruchstrichen,
und das wieder in Wurzeln packen können usw.

Das muss man auch alles hinbekommen wobei das gegen das
Mathematik-Modell dahinter vergleichber einfach ist...

Jester

Rein theoretisch müßte der Rechner sogar selbst die partielle Integration herleiten können. Das Problem ist, wie Du richtig festgestellt hast eine gute Heuristik zu haben, um zu wissen, welche Regelanwendungen Erfolg versprechen. Vielleicht könnte man den Ausdruck erstmal grob analysieren und dann sagen, okay, dieses Bündel an Regeln dürfte am meisten bringen, und dann arbeitet man mit einer Untermenge weiter. Integrale mit exp oder trigonometrischen Funktionen lassen sich gern mit partieller Integration lösen. Viele eindimensionale Integrationsprobleme lassen sich mit Standardsubstitutionen lösen. Man muß nur rausfinden von welchem Typ sie sind.

Auch die Prädikatenlogik 1.Ordnung ist nicht ganz ausreichend um alles mathematische auszudrücken. Dennoch ist sie schon so umfangreich, daß sie unentscheidbar ist. Man kann also letztlich nicht immer entscheiden, ob eine gegebene Aussage wahr oder falsch ist. Das Problem ist also sehr hart. Deswegen muß man hier sowieso mit Näherungen arbeiten.

In der Prädikatenlogik 1. Ordnung kann man ja nur über Variablen quantifizieren. Damit läßt sich sowas wie Induktion aber nicht durchführen. Dafür müßte man nämlich auch über Prädikate Quantifieren können:

etwa so:
Für alle Prädikate P: (P(0) und (P(n) => P(n+1))) => Für alle n: P(n)
Das ist +/- das 5. Peano-Axiom. In reiner Präd.-Log. 1. Ordnung ließe es sich nicht formulieren. Allerdings ist automatisches Beweisen in Logiken höherer Ordnung noch viel schwerer. In der Prädikatenlogik gibt's immerhin noch korrekte vollständige Algorithmen: Das heißt, gefundene Beweise sind korrekt und wenn ein Beweis existiert, so wird er auch gefunden. Sowas ist in höheren Ordnung meines Wissens nicht mehr gegeben. Es ist aber auch fraglich, ob der Rechner wirklich ne Induktion machen muß.

MfG Jester

ths

Aber dreht man sich nicht im Kreis:
Ich kann mit der Prädikatenlogik alleine nichts machen, weil die Heuristik
zunächst eine Entscheidung treffen muss.

Nun gut.

Aber die Heuristik muss dazu das "Wissen" der Mathematik haben -- also braucht
sie wiederum die Prädikatenlogik. Wenn die Heuristik die Regeln kennen und
können muss, dann brauchen wir ja keine Prädikatenlogik mehr. Oder?

Jester

Die Heuristik ist oberflächlicher und ungenauer.
Wenn Du Dir nen komplexen Term anschaust und den vereinfachen willst, dann weißt Du nicht sofort was rauskommt (zumindest bei mir isses so), aber es fallen einem sofort gewisse Rechenregeln ein, die was bringen *könnten*, nicht müssen(!). Und mit diesen probierst Du dann rum um es einfacher zu kriegen.

Und wenn jetzt unser Programm durch ansehen des Terms zumindest abschätzen kann, welche Rechenregeln zur Vereinfachung führen könnten, dann machen wir damit den Suchraum drastisch kleiner, weil sämtliche Regeln, die eh nix bringen aussortiert sind. Das Problem ist ja nicht, daß wir zu wenig Ausdruckskraft hätten mit der PL1, sondern daß wir soviel sagen können, daß der Suchraum riesig wird.

MfG jester

ths

Okay. Das ist aber zunächst im ersten Schritt nicht so schwer
Sagen wir mal zunächst, dass wir für jede Regel eine Klasse haben. Oder zumindest
eine Klasse pro Regel-Typ. Also eine Klasse für Integration, Grundrechenarten usw.

Dann würde die Heuristik die gegebenen Daten analysieren:

Ist eine Zeichenfolge "int" vorhanden? Ja --> Integration vormerken
Ist ein "+", "-", "*" oder "/" Zeichen vorhande? Ja --> Grundrechenarten vormerken
Ist ein "/"-Zeichen vorhanden? Bruchrechnung vormerken
Ist ein "(" oder ")" vorhanden? .... etc.

Damit kann man ganz ganz grob aufteilen, was man ganz sicher nicht braucht.
Als Symbole für Integral etc. könnte man sich auf die LaTeX-Befehle einigen.
Zumindest, wenn es Sinn macht.

Tja... dann geht es schon los, die Feinheiten zu suchen Und dann wirds
schwer

Eine Idee wäre:

Man würde eine Klasse mathParser basteln, die abstrakt ist. Sie kann also
nicht instanziert werden. Von ihr erben alle Rechenarten etc.

Dann könnte man zum Beispiel beim ersten Auftreten von "(" das passende
")" Zeichen suchen. Diesen Teil-String gibt man dem Konstruktor der
brackets-Klasse mit. Dieser ruft wieder den Parser auf (den hat er ja
geerbt) und der Parser analysiert den Rest des Teil-Strings.

Dadurch würde sich doch automatisch eine Art Tree-Struktur ergeben.

Wo speichert man die Referenzen (Zeiger) auf die Objekte? Man könnte
eine Singleton-Klasse haben, die in einem Array oder (in Java) in einer
ArrayList die Instanzen bewart.
Oder man bastelt sich etwas ähnliches, wie in dem Link den ich angegeben
hatte. Jedes Objekt hat eine Methoe hasNextNote() etc. Dann würe man
eine neue Instanz einer Klasse in dem Objekt speichern, die das neue
Objekte angelegt hat

-- Trigonometrische Funktionen auf exp zurückführen.
-- Universalsubstitution tan(x/2)
-- Paradigms of Artificial Intelligence Programming, http://www.norvig.com/paip/README.html

Walli

Meine laienhaften Vorstellungen zu dem Thema: Es muss doch "nur" möglich sein, dass ein Programm einen normierten Term bewerten kann und dann aus einem Katalog ermittelt welche Regeln Anwendung finden könnten und eine Art Brute-Force startet bis das gewünschte Ergebnis erzielt wurde. Natürlich muss es ein guter Algorithmus sein, denn sonst probiert er u.U. zemlich lange herum. Auch müssen geeignete Abbruchbedingungen vorliegen (z.B. Abbruch wenn die Umformung wieder einen Ursprungsterm ergibt).

ths

@MaSTaH:

Schau dir mal mein Mathematik-Dokument an:
http://www.cyberzone2001.de/documents/Mathematik.pdf

Dort sind ja auch viele Regeln aufgezählt. Und das ist nur ein relativ kleiner
Teil der Mathematik. Das müsste man dem Programm alles "beibringen" Und
noch mehr... im Dokument werden oft nur die einfachsten Fälle beschrieben.
Zum Beispiel bei DGLs nur bis zur 2. Ordnung, statt bis zur n-ten etc.

Also im Prinzip hast du ja Recht: "Nur" analysieren und bewerten. Aber
das wird richtig heftig... wie man in dem Dokument sieht.

Jester

@Mastah: Genau das ist der Ansatz, den wir hier auch verfolgen. Das blöde dabei ist, daß der Suchraum unendlich groß ist. Darum versuchen wir auf irgendeine Art unsinnige Sachen wegzuwerfen oder nur sinnvolle Sachen zu verfolgen. Damit bleibt der Suchraum zwar wahrscheinlich immer noch unendlich groß, aber ist dennoch viel kleiner, als wenn man alle Regeln stets zuließe. Nur, wie findet man welche Regeln Sinn machen? Woran sieht man, daß man fertig ist mit vereinfachen? Wie sieht man, daß die scheinbar unsinnige Regelanwendung nach 5 weiteren Umformungen plötzlich eine geniale Vereinfachung ermöglicht?

volkard

Jester schrieb:

Nur, wie findet man welche Regeln Sinn machen?

die klassische antwort heißt hier "neuronale netze". *grins*

Woran sieht man, daß man fertig ist mit vereinfachen?

wenn alle möglichkeiten gemacht wurden.

Wie sieht man, daß die scheinbar unsinnige Regelanwendung nach 5 weiteren Umformungen plötzlich eine geniale Vereinfachung ermöglicht?

einfach bis suchtiefe 5 alle regeln zulassen. tiefer werden nur regeln verfolgt, die zu "vereinfachengen" geführt haben, wobei "vereinfachung" was einfach messbares wie knotenanzahl im baum oder strlen(ausgabe) ist.

Jester

Jo, klingt vernünftig. Jetzt brauchen wir nur noch jemanden, der's implementiert. :p

Walli

Ich kann die 2 Stündchen leider nicht opfern, sonst würde ich das implementieren .

Walli

ths schrieb:

Also im Prinzip hast du ja Recht: "Nur" analysieren und bewerten. Aber
das wird richtig heftig... wie man in dem Dokument sieht.

Von der Mathematik her ist es ja nicht so heftig. Ausserdem arbeitet das Programm nur dumm irgendwelche Möglichkeiten ab. Die Hauptschwierigkeit besteht imho darin, die einzelnen Gesetze in eine Form zu bringen, die das Programm versteht und darin, den Term zu bewerten.

volkard

MaSTaH schrieb:

Ich kann die 2 Stündchen leider nicht opfern, sonst würde ich das implementieren .

der suchbaum ist nicht das ding. der sucher auch nicht. heuristiken wachsen mit der beschäftigung am problem und sind anfangs nichtmal relevant.
die transformationsregeln sind ein ding. die sauber hinschreiben zu können kannste in c++/java verbacken. da muss ne neue sprache her (oder lisp, wie immer).
wir brauchen allein mehr als ne woche, um nen mathematiker einzufangen, der uns sinnvolle regeln erzählt. eventuell ist es sogar für jeden nichtmathematiker unmöglich nen mathematiker einzufangen. fatales problem.

Walli

Das war auch nicht ganz ernst gemeint. Ich dachte das war klar .

ths

Ein paar Links zum Thema:

(CAS == Cumputer Algebra System)

Erklärung, wie man ein CAS erstellt (allgemein):
http://www.math.wpi.edu/IQP/BVCalcHist/calctoc.html

Ein kostenloses CAS, mit Quellcode in C++:
http://yacas.sourceforge.net/

Nochmal kostenloses CAS, mit Quellcode:
http://maxima.sourceforge.net/index.shtml

Für alle, die Lisp und Prolog noch nicht kennen:
http://de.wikipedia.org/wiki/PROLOG
http://de.wikipedia.org/wiki/Lisp

(PROLOG ist ja echt der Hammer -- werd mich mal mit beiden beschäftigen)

ths

Oh -- was interessantes:

Ladet euch mal das Prolog-Arbeitsbuch runter:
http://www.bildung-mv.de/download/fortbildungsmaterial/arbeitsbuch_prolog.pdf

Auf Seite 68 wird erklärt, wie man Prolog das Differenzieren (symbolisch!!!)
beibringt!

Also GENAU das, was wir suchen. Ist doch schonmal was. Wie kann ich aber
Prolog in eine grafische C / C++ / Java - Oberfläche einbinden?

Symbolisches Differenzieren ist trivial.