Aaron, thank you for the quick and comprehensive answer! :) On 26 май, 02:19, Aaron Meurer <[email protected]> wrote: > On May 25, 2012, at 3:39 PM, Natalia Smirnova > > > > > > > > > > <[email protected]> wrote: > > Hello, > > > I integrated Sympy into the learning system which is meant for > > "replacing the pencil and paper that students would ordinarily use to > > solve math homework problems." > > In this system a student is expected to enter full solution of the > > problem, step by step. > > > I use Sympy to compare expressions, entered by student (exp1), with > > expressions stored for the possible solutions of the task being solved > > (exp2). > > Roughly it's like that: if simplify(exp1 - exp2) == 0, then student > > entered a correct step. > > > My science advisor wonders about the simplification procedure in > > Sympy. He says - how come, the problem of simplification is > > algorithmically unsolvable, how it works? So, the question is: > > > - Can the procedure of expression simplification be described this way > > -http://cane.yuntech.edu.tw/member/WRC2004/Computer%20Algebra%20Papers... > > - part 5.2. "Implementations"? > > I don't think we apply that exact method, but the basic idea is the > same. We have a bunch of targeted simplification functions. Most of > these live in the simplify module. For example, factor() powsimp(), > trigsimp(), combsimp(), and so on. In simplify(), we try to apply > these intelligently to the input expression. For example, trigsimp is > used only if the expression contains trigonometric functions. We apply > different combinations of these, and then pick the answer that is the > simplest, based on a metric. The original expression is included in > this test, so simplify() should never make an expression more > complicated. The metric we use is count_ops(), which is just the total > number of operations in the expression. In the development version of > SymPy, you can make your own metric function to pass in to simplify(). > > > > > - Is there any data about how often simplification of expressions > > doesn't work? How can "the class of expressions" - for which > > simplification in Sympy is done well - be described? > > Unfortunately not really, since simplify() is mostly a heuristic that > we are constantly trying to improve. The only kind of expressions that > you can say for certain will always simplify to zero when it is zero > in SymPy are rational functions, because they can be put into > canonical form (p/q, where p and q are polynomials with gcd 1 and, > say, q is monic), so you know a ration function is identically zero if > and only if its canonical form is 0/1. Algorithms exist to > canonicalize algebraic expressions, but they haven't been implemented > for the most part yet. For transcendental expressions, there exist > only heuristics. > > In my personal experience, if an expression is really zero but doesn't > simplify to such, it's usually for one of two reasons: > > - The simplification required to reduce the expression to zero is > quite complicated. To even simplify such an expression by hand > requires a bit of ingenuity. This case is rare, but it does come up. > It probably wouldn't come up in your situation, unless the takes a > completely novel route that is correct but way off from your expected > solution. > > - The simplification is not valid for some values if the variables. > This is much more common. In SymPy, we assume all Symbols are complex > by default, and try to avoid simplifications that are not valid for > all complex numbers. For example, sqrt(x**2) == x is true only when x > is positive. Even the identity log(exp(x)) == x is not true for all > complex x (because if you replace x with x + 2*pi*I*n, exp(x) remains > the same). The easiest way to avoid this is to put the necessary > assumptions on your variables, like Symbol("x", real=True). Also, many > simplification functions like logcombine() and expand() have force > options that you can pass to force simplifications regardless of > assumptions (we probably should add this option to simplify() itself). > > If you come across an expression that simplify() can't handle, and > you're sure it's not just because of assumptions, then it should be > considered a bug, and should be reported on our issue tracker on > Google Code. This is especially true if the simplified form of the > expression is just 0. > > Aaron Meurer
-- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
