Может ли программа использоваться для упрощения алгебраических выражений?

Question

Мы знаем, 1+2+...+n равно n(n+1)/2.

Но можем ли мы получить тот же результат программно, если мы не знаем его заранее?

О том, почему у меня такой вопрос.

Подумайте о более сложной ситуации:

X1 + X2 + ... + Xk = n, где Xi является целым числом и> = 0.

Чего ожидать от X1^2+...Xk^2?

Результат неочевиден на первый взгляд, и мы хотим передать его в программу, чтобы уменьшить алгебру, как только мы разработали (подробное) математическое представление Ожидания X1^2+...Xk^2

Answer 1

Возможно, вы думаете о Системе компьютерной алгебры (CAS)? WolframAlpha - это бесплатная онлайн-версия, которая использует Mathematica (очень мощную систему CAS) на своем бэкэнде. Здесь вы можете увидеть, как он вычисляет / упрощает ваше выражение: WolframAlpha .

Ваш пример - это просто сумма квадратов , которая имеет довольно простую явную формулу: n(n+1)(2n+1)/6. В более общем смысле вы можете использовать формулу Фолхабера для вычисления Sum of n^p.

Answer 2

Хорошо, сначала несколько предложений о математической части вопроса, а затем о разработке программного обеспечения.

Есть электронная книга "A = B" Марко Петкова · сек, Герберта С. Уилфа и Дорон Цайлбергер, которая занимается решением (или показывает, что решения не существует) задач суммирования еще сложнее чем просто полиномы. рецензия на книгу Яна Вэнлесса заслуживает быстрого прочтения. Электронная книга доступна для бесплатной загрузки, но можно приобрести переплётные копии, например, с Амазонки.

A 2004 Trans. бумаги AMS Суммирование закрытой формы C -конечных последовательностей Грина и Уилфа также доступно онлайн.

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

Если в объем вашего проекта включено «ожидание» выражений, то существует ряд сложностей, сложенных поверх простой алгебраической манипуляции. Безусловно, необходимо уметь определять функции плотности вероятности для поддержки ожидаемых значений и, возможно, некоторого программного обеспечения для интеграции (хотя потенциальное ограничение выбора параметризованных распределений может привести к упрощенной проблеме поиска моментов этих распределений). Я действительно думаю, что это особенно хорошее приложение, к которому можно перейти, поскольку, казалось бы, простые выражения (суммы, макс / мин) случайных величин могут привести к кошмарному рассмотрению дел, хорошо подходящих для терпения компьютера.

Answer 3

РЕДАКТИРОВАТЬ , в связи с вашим недавним разъяснением поста.

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

Если вы программист на Лисп, использование Maxima - это еще один потенциал (бесплатный).это одно) решение.

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

---

X1+ X2 + ... + Xk = n, где Xi является целым числом и> = 0.

Чего ожидать от X1 ^ 2 + ... Xk ^ 2?

ThisТакие проблемы занимают много людей, чтобы понять, как это сделать на бумаге.

Давайте возьмем k = 2. Тогда X_1 + X_2 = n дает X_2 = n - X_1.

Таким образом, ожидаемое значение будет E = X_1^2 + (n - X_1)^2 = 2 X_1^2 -2n X_1 + n^2.

Эточитает

E = sum(p_k * (2 * k^2 - 2 * n * k + n^2), k = 0..infinity)

, где p_k = Prob(X_1 = k).Этот тип сумм, в зависимости от p_k, обычно очень сложно вычислить.Я бы сказал, что проблема еще сложнее, чем вычисление интегралов в замкнутой форме (для которых ни одно программное обеспечение полностью не реализует доступный - но неразрешимый - алгоритм Риша).

Чтобы убедить себя, возьмите, например,.p_k = 1 / (log(k) * k^4).

Найти формулу (или генератор формул) для нее, как минимум, очень трудная исследовательская задача.