Как манипулировать математическими символами?

Question

Это больше «образовательный» вопрос.:)

Хотя я, вероятно, в конечном итоге хотел бы сделать что-то подобное.

Итак, допустим, я получил уравнение.Это может быть любое уравнение, если оно не смешно, а человек, который хорошо разбирается в математике, может решить его.

Скажем так ... 0 = (x-1) (x + 2)

или ... y = (x ^ 2), y = 1 / x

Или синусоидальные функции и т. Д. В основном, мы выполняем математику, как в школе.

вопрос в том, как бы я написал компьютерную программу для решения этой проблемы?Я знаю, что это возможно, потому что такие программы, как Mathematica, Maple и т. Д., Делают это десятилетиями!Но я не могу найти хорошую документацию о том, как сделать даже простой решатель уравнений.

Я не ожидаю ответов, которые скажут мне, «это именно то, как вы это делаете», потому что, конечно, такая вещьцелая большая программа, а не просто фрагмент кода.

Но только общий обзор или ссылки на некоторые хорошие документы?Это было бы прекрасно!Спасибо:)

Особенно, какие структуры данных и алгоритмы необходимы.

Если это не удастся, мне просто нужно выяснить, КАК Я РЕШУ УРАВНЕНИЯ, и закодировать это.Но на это уходит буквально месяцы (я уже делал подобные вещи, формализуя свой собственный мыслительный процесс в коде, он работает, но он медленный).

Answer 1

Взгляните на некоторые статьи о символических манипуляциях .

Книга Питера Норвига PAIP описывает очень простую систему символьных манипуляций и решения уравнений, так чтостоило бы прочитать.Он знакомит с основами программы ИИ под названием MacSyma , которая в итоге легла в основу Mathematica .

Answer 2

Wolfram Alpha будет эталоном, который вам наиболее доступен.

Ваши входные данные являются строками, поэтому первым шагом является написание лексера / парсера, который разбивает эти строки на токены и помещает их в абстрактное синтаксическое дерево (AST).

Вы не делаетеСкажите, на каком языке вы хотите это реализовать, но я бы порекомендовал посмотреть на ANTLR .Это генератор парсера, который может помочь вам создать AST.Вам нужно будет придумать грамматику для ваших уравнений.

Когда у вас есть AST, ваш решатель будет обходить дерево и связывать более конкретные операции с символами, такими как "+", "-" и т. Д.Чем больше операторов вы сможете обработать, тем более мощным и всеобъемлющим будет ваш решатель.

Но есть много сложностей, с которыми вам придется иметь дело или исключить:

1. Не все уравнения имеют решения.
2. Не все уравнения имеют решения в замкнутой форме.
3. Не все уравнения являются линейными.
4. Множество интересных задач состоит из множества связанныхуравнения (подумайте линейная алгебра).
5. Вам много нужно много знать о численных методах для тех случаев, когда замкнутая форма не удается.

Я бы порекомендовал вам начать с простогоарифметика и полиномы и работать вверх.Стивен Вольфрам не написал Mathematica за один день.

Answer 3

Основной метод состоит в представлении структуры математического уравнения в компьютерной программе.Эта идея очень похожа на то, что делают компиляторы, но компиляторы в основном преобразуют свои входные данные в машиночитаемый формат, но системы компьютерной алгебры в основном выдают выходные данные того же формата, что и их входные данные, но преобразуются некоторым интересным способом.В любом случае непосредственный вывод - это абстрактное синтаксическое дерево.Следующим шагом будет применение некоторых методов сопоставления с образцом (аналогично тому, как работают регулярные выражения), а также некоторых механических преобразований для переписывания дерева некоторым полезным способом.

Если вы хотите увидеть, как это может быть на самом делеготово, SymPy - это библиотека математических символов Python, которая имеет открытый исходный код и сосредоточена главным образом на аспектах манипулирования символами в этой теме.

Answer 4

В дополнение к полезным ответам других людей: эта ссылка кажется интересной: http://en.wikipedia.org/wiki/Pattern_matching также интересен "синтаксис абстрактного дерева".По сути, речь идет о «сопоставлении с образцом» в синтаксическом дереве!Вроде как регулярное выражение, но для кода.

Я уже написал свой собственный "синтаксис абстрактного дерева" :) Так что я уже немного иду по пути к символическому манипулятору.