arithmetischen Ausdruck vereinfachen

[g.sandra.1995]

Mit Vielen CAS Programme wie Maple und Mathematica kann man arithmetischen Ausdruck vereinfachen (simpltfy). Hat man Idee wie geht das technisch? Wird etwa den Ausdruck in einem Baum oder so umgewandelt? Hat man weiterführenden Literatur? Links?

 

[Technipion]

Wird etwa den Ausdruck in einem Baum oder so umgewandelt?

Damit bist du schon verdammt nahe dran! Es wird zunächst ein parse tree erstellt. Auf dem können dann weitere Operationen ausgeführt werden.

Hat man weiterführenden Literatur? Links?

Puh, du schneidest damit natürlich ein riesen Thema an. Computeralgebrasysteme und symbolische Mathematik wären hier wohl passende Stichwörter.

Für den ganz plumpen Einstieg hat Computerphile mal ein nettes Video auf YouTube hochgeladen:

YouTube Video



Gruß Technipion

 

[ComFreek]

Genau, im Grunde genommen arbeiten simplifier auf Baumstrukturen. Aber in der Mathematik ist es nichttrivial zu entscheiden, was genau der Simplifier machen soll.

Am Anfang mag es noch einfach sein. Wenn wir als Eingabeterme z. B. nur rationale Zahlen, Brüche derer und Wurzeln betrachten, könnten wir einfache Heuristiken haben wie: wenn Bruch im Nenner eines Bruches, multipliziere mit dessen Kehrbruch stattdessen. Wenn Wurzel im Nenner eines Bruchs, dann erweitere den Bruch damit usw.
Solche Heuristiken i.Allg. auszuarbeiten, sodass Menschen die maschinell vereinfachten Ausdrücke tatsächlich als vereinfacht bezeichnen würden, ist schwer.
Unter anderem werden sehr viele Vereinfachungen nur noch bedingt anwendbar sein. Zum Beispiel kannst du `sqrt(a^2)` nur dann zu `a` vereinfachen, wenn `a >= 0` angenommen wird. Und wenn `a` keine Variable ist, sondern ein komplexer Ausdruck, dann musst du dafür erst einmal entscheiden, um dieser komplexe Ausdruck `>= 0` ist. (Das sollte i. Allg. unentscheidbar im Sinne der Berechnungstheorie sein )

 

[Technipion]

Ich schließe mich da @ComFreek uneingeschränkt an. Gefragt war hier ja ursprünglich nur die technische Seite des Ganzen. Die besteht im Wesentlichen aus dem Parsen der Terme/Ausdrücke und Aufspannen in einem Baum. (Wie genau der Baum aufgebaut ist, hängt natürlich auch von deinem CAS ab...)

Danach allerdings kommt erst die harte Nuss. Mathematik. Und zwar nicht zu wenig davon. Ich hatte selbst einmal versucht ein kleines CAS in Python zu programmieren. Fühlt sich in etwa an wie ein Spaziergang. Durch den Dschungel. Nackt. Nachts.

Respekt an die vielen (teilweise OpenSource) CASe da draußen!

Gruß Technipion

PS: Da dies im Java-Forum gepostet wurde, sei hier mal auf dieses coole Projekt verlinkt.