C/C++ symbolische Mathematik beibringen...

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.

ths

mfdg schrieb:

Symbolisches Differenzieren ist trivial.

Symbolisches integrieren auch Und alles andere auch... für einen
Menschen. Jedes Problem für sich ist doch kein Problem Nur alles jederzeit
zu ermöglichen in einem Programm ... das ist doch das Problem

volkard

ths schrieb:

mfdg schrieb:

Symbolisches Differenzieren ist trivial.

Symbolisches integrieren auch Und alles andere auch... für einen
Menschen. Jedes Problem für sich ist doch kein Problem Nur alles jederzeit
zu ermöglichen in einem Programm ... das ist doch das Problem

war eher anders gemeint, nehme ich an. in zwei oder drei bildschirmen voll mit lisp baut man nen symbolischen ableiter. als übung für anfänger findet man den in büchern.
symbolischen integrieren hingegen ist gemein. so gemein, daß ich noch kein computeralebrasystem gesehen habe, das mich in dieser hinsicht befriedigte. mußte oft in büchern nachgucken und rumprobieren, bis ich ne umformung gefunden hatte, von der ausgegend das prog es schaffte. zum glück ist aber differenzieren trivial, und darum konnte ich mit dem prog immer die probe machen.

ths

Ist das sooo gemein zu programmieren? Ich habs noch nicht
probiert Ich werde es mal mit der Prädikatenlogik mit Prolog
probieren ... 1,5 Wochen Semester-Ferien hab ich ja noch