2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3, 4, 5  След.
 
 количество сложений и умножений при вычислении формул
Сообщение11.09.2009, 06:58 
Предположим, есть двуместные операции из $a$ и $b$ в $c$ - вычитание и сложение:
$c=a+b$
$c=ab$
доказано ли утверждение, что минимально возможное количество этих операций при вычислении формулы вида

$y=\sum\limits_{i=1}^{N} a_i x_i $

равно $2N-1$? И если доказано, то где?

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 16:20 
Аватара пользователя
Очевидная идукция:
При $N=1$ выражение считается в одно действие.
Если $N>1$, то последнее действие - это сложение:

$\sum\limits_{i=1}^{N} a_i x_i =\sum\limits_{i=1}^{n} a_i x_i +\sum\limits_{i=n+1}^{N} a_i x_i $

Отсюда минимально возможное число действий - это $(2n-1)+(2(N-n)-1)+1)=2N-1$.

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 17:27 
Аватара пользователя
bot в сообщении #242368 писал(а):
Если $N>1$, то последнее действие - это сложение:

Почему?

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 17:32 
Аватара пользователя
Ага. Если все $a_i$-ые равны $0$, то ваще никаких операций не надо :)

Вообще, конечно, задача нуждается в основательной формализации. Что значит "операции при вычислении формулы"?

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 17:39 
Аватара пользователя
Ну формализация понятна. Каково минимальное число действий, гарантирующее вычисление такой суммы при любых коэффициентах. Под действием понимаем либо сложение двух чисел либо их умножение.

-- Пт сен 11, 2009 17:49:03 --

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

Профессор Снэйп в сообщении #242399 писал(а):
Ага. Если все -ые равны , то ваще никаких операций не надо

Надо и ровно столько же. :)

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 17:49 
Аватара пользователя
Ну да.
Известные методы получения "очевидных" нижних оценок в таких случаях очень интересны.
Если доказать, что сложений нужно не меньше $n-1$, просто: достаточно рассмотреть множество переменных $x_i$, от которых зависит функция, то с умножениями все хуже.

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 17:55 
Аватара пользователя
Ну можно и совсем формально:
Сколько надо поставить пар скобок, чтобы выражение стало термом. Определение терма по индукции дать?
Xaositect в [url=http://dxdy.ru/post242396.html#p242396]сообщении #242396
[/url]
писал(а):
Почему?

Ответил на вопрос?

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 18:03 
Аватара пользователя
bot в сообщении #242408 писал(а):
Ответил на вопрос?

А почему это выражение нельзя упростить?

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 18:29 
Аватара пользователя
А как Вы это себе представляете? Впрочем, такого действие условием и не предусматривалось.

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 18:37 
Аватара пользователя
bot в сообщении #242425 писал(а):
А как Вы это себе представляете? Впрочем, такого действие условием и не предусматривалось.

Условем предусматривается минимальное кол-во операций для вычисления выражения и никак не указан их порядок или взаимное расположение.
То есть, если Вы говорите, что упростить выражение нельзя, нужно доказать, что его упростить нельзя(это можно доказать, я сейчас перечитваю Algebraic Complexity Theory и думаю, как бы это попроще изложить).

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 18:54 
Аватара пользователя
видимо имеется ввиду максимум минимумов числа операций для всех таких выражений :)
только сдается мне, что если подставляемые числа заданы в явном виде или с помощью неких уравнений, то сия сумма будет считаться быстрее.

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 19:05 
Господа, должен вас огорчить. Эта задачка не столь тривиальна. Есть серьезные подозрения, что ее можно решать только перебором. Вариант с индукцией, к сожалению, неправильный. Вообще, последний из великих, кто рассматривал нечто подобное - Колмогоров. Сейчас с этим никто не работает. Толи не могут, толи просто не в курсе, что такие задачи есть...

Задачка попроще: за сколько операций сложения можно вычислить сумму вида:

$y=x+x+x+x+x+x+x+x+x+x+x+x+x+x+x=15x$

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 19:20 
Аватара пользователя
Вот нижняя оценка количества умножений:
Рассмотрим алгоритм, использующий сложения, вычитания и умножения, и вычисляющий $\sum\limits_{i = 1}^n a_i F_i(\vec{x})+F_0(\vec{x})$.
Будем считать "правильные" умножения, в которых хотя бы один из сомножителей зависит от каких-то $a_i$, и докажем, что их не менее $n$. По индукции.
База. $n=1$. Для вычисления $a_1 F(\vec{x}) + F_0(\vec{x})$ нужно одно правильное умножение.

Переход. $n>1$. Пусть алгоритм имеет сложность(кол-во правильных умножений) $c$. Рассмотрим первое правильное умножение. Оно вычисляет произведение $(\sum\limits_{i=1}^n \alpha_i a_i + A(\vec{x}))(\sum\limits_{i=1}^n \beta_i a_i + B(\vec{x}))$. Без ограничения общности $\alpha_1 = 1$.
Рассмотрим новый алгоритм, который работает так: сначала он вычисляет $a_1 = - \sum\limits_{i=2}^n - A(\vec{x})$, а затем работает так же, как исходный. Так как в этом случае $(\sum\limits_{i=1}^n \alpha_i a_i + A(\vec{x})) = 0$, первое правильное умножение можно убрать, т.е. мы получили алгоритм вычисления какой-то функции $\sum\limits_{i=2}^{n}a_i G_i(\vec{x}) + G_0(\vec{x})$, имеющий сложность $c-1$. По предположению индукции $c-1\geq n-1$.

-- Пт сен 11, 2009 19:22:17 --

Тут есть неточности, но их в принципе можно устранить (например, надо указать, что $F_i$ должны быть неконстантными, линейно независимыми и проверить это для $G_i$)
Это изложение на основе статьи Винограда "On the Number of Multiplications Required to Compute Certain Functions" и шестой главы "Algebraic Complexity Theory", авторы Burgisser, Clausen, Shokrollahi.

-- Пт сен 11, 2009 19:27:10 --

st256 в сообщении #242453 писал(а):
Задачка попроще: за сколько операций сложения можно вычислить сумму вида:

Конкретно для 15 я уже не помню значение. Для $n$ есть оценка $\log n + \frac{\log n}{\log \log n} (1+o(1))$

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 19:35 
Аватара пользователя
st256 в сообщении #242453 писал(а):
Задачка попроще: за сколько операций сложения можно вычислить сумму вида:

$y=x+x+x+x+x+x+x+x+x+x+x+x+x+x+x=15x$

Ответ на подобные задачи дают аддитивные цепочки.
http://en.wikipedia.org/wiki/Addition_chain

 
 
 
 Re: Может теория графов, а может что-то иное, но не суть важно
Сообщение11.09.2009, 20:41 
Ночь, наверное поэтому торможу. Что такое "правильные" умножения? Как понять, что сомножитель сам от себя зависит?

Xaositect в сообщении #242455 писал(а):
Будем считать "правильные" умножения, в которых хотя бы один из сомножителей зависит от каких-то $a_i$, и докажем, что их не менее $n$.


-- Пт сен 11, 2009 21:43:11 --

Вообще-то Вы привели алгоритм Винограда, а он только умножения вроде бы учитывает....

-- Пт сен 11, 2009 21:45:04 --

maxal в сообщении #242460 писал(а):
st256 в сообщении #242453 писал(а):
Задачка попроще: за сколько операций сложения можно вычислить сумму вида:

$y=x+x+x+x+x+x+x+x+x+x+x+x+x+x+x=15x$

Ответ на подобные задачи дают аддитивные цепочки.
http://en.wikipedia.org/wiki/Addition_chain


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

 
 
 [ Сообщений: 73 ]  На страницу 1, 2, 3, 4, 5  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group