количество сложений и умножений при вычислении формул

[Xaositect]

Модель выглядит так.
Алгоритмом сложности $c$ называется последовательность длины $c$ из шагов вида $r_k = s_1 + s_2$ или $r_k = s_1\cdot s_2$, где $s_1$,$s_2$ есть либо одно из $a_i$, либо одно из $x_i$, либо $r_i$ с $i<k$, либо константа $p$. Будем говорить, что алгоритм вычисляет $R(\vec{a},\vec{x})$, если $r_c = R(\vec{a},\vec{x})$
Правильным умножением называется шаг вида $r_k = s_1\cdot s_2$, где хотя бы одно из $s_1$, $s_2$ зависит от какого-либо из $a_i$.

[maxal]

st256
Еще как дают - буквально по определению. И существуют способы их вычисления лучшие чем перебор (хотя и экспоненциальные).
Эта картика дает кратчайшие аддитивные цепочки для $n<149$ - длина пути до конкретного $n$ как раз и дает минимальное число сложений:


Для $n=15$ минимальное количество сложений равно 5.

[st256]

maxal в сообщении #242475 писал(а):

st256
Еще как дают - буквально по определению. И существуют способы их вычисления лучшие чем перебор (хотя и экспоненциальные).
Эта картика дает кратчайшие аддитивные цепочки для $n<149$ - длина пути до конкретного $n$ как раз и дает минимальное число сложений:


Для $n=15$ минимальное количество сложений равно 5.

Интересно, кто только составлял эту картинку. При этом, боюсь, что слово "экспотенциальный" обозначает именно перебор.

Мне, в общем, этот пример в Новосибирске показали. В институте математики. Там этим методом гены сшивают (ищут способ побыстрее ген собрать). Причем этот пример иллюстрировал именно неразрешимость этой задачи. Т.е. только перебором. Мне почему-то показалось, что они правы.

-- Пт сен 11, 2009 22:24:03 --

Xaositect в сообщении #242474 писал(а):

Модель выглядит так.
Алгоритмом сложности $c$ называется последовательность длины $c$ из шагов вида $r_k = s_1 + s_2$ или $r_i = s_1\cdot s_2$, где $s_1$,$s_2$ есть либо одно из $a_i$, либо одно из $x_i$, либо $r_i$ с $i<k$, либо константа $p$. Будем говорить, что алгоритм вычисляет $R(\vec{a},\vec{x})$, если $r_c = R(\vec{a},\vec{x})$
Правильным умножением называется шаг вида $r_k = s_1\cdot s_2$, где хотя бы одно из $s_1$, $s_2$ зависит от какого-либо из $a_i$.

Чот совсем не понял... Понятие сложности алгоритма $\epsilon$-энтропию ввел Колмогоров (вроде). Сложность алгоритма, это грубо говоря информация о какой-то, допустим, функции, позволяющая собрать ее с точностью $\epsilon$. Но тем не менее, вроде дошло...

[Xaositect]

st256 в сообщении #242482 писал(а):

Чот совсем не понял... Понятие сложности алгоритма -энтропию ввел Колмогоров (вроде). Сложность алгоритма, это грубо говоря информация о какой-то, допустим, функции, позволяющая собрать ее с точностью . Но тем не менее, вроде дошло...

Есть разные понятия сложности. Бывает временнАя сложность, сложность по памяти, статическая сложность...

[st256]

Xaositect в сообщении #242484 писал(а):

st256 в сообщении #242482 писал(а):

Чот совсем не понял... Понятие сложности алгоритма -энтропию ввел Колмогоров (вроде). Сложность алгоритма, это грубо говоря информация о какой-то, допустим, функции, позволяющая собрать ее с точностью . Но тем не менее, вроде дошло...

Есть разные понятия сложности. Бывает временнАя сложность, сложность по памяти, статическая сложность...

А где почитать про это? Только не популярно, а со всеми доказательствами. И желательно советскую книгу. В английских часто доказательства не совсем корректные, типа и так понятно.

[maxal]

st256
Перебор перебору - рознь. Переборы разные бывают. Например, в худшем случае - это полный перебор, в лучшем - метод ветвей и границ (в некоторых случаях может снизить временную сложность даже до полиномиальной). Поэтому фраза "задача решается перебором" почти не несет смысловой нагрузки.

[Xaositect]

st256 в сообщении #242485 писал(а):

А где почитать про это? Только не популярно, а со всеми доказательствами. И желательно советскую книгу. В английских часто доказательства не совсем корректные, типа и так понятно.

Монографий советского времени я не знаю по этой теме. Наверное, потому, что в то время теория только формировалась. Можно посмотреть оригинальные статьи Колмогорова, Маркова, Карацубы, Бардзиня, Лупанова...
В качестве введения в тему могу посоветовать учебник моего научного руководителя: Алексеев В.Б. Введение в теорию сложности алгоритмов.

[st256]

maxal в сообщении #242488 писал(а):

st256
Перебор перебору - рознь. Переборы разные бывают. Например, в худшем случае - это полный перебор, в лучшем - метод ветвей и границ (в некоторых случаях может снизить временную сложность даже до полиномиальной). Поэтому фраза "задача решается перебором" почти не несет смысловой нагрузки.

Договорились

-- Пт сен 11, 2009 23:16:24 --

Xaositect в сообщении #242489 писал(а):

st256 в сообщении #242485 писал(а):

А где почитать про это? Только не популярно, а со всеми доказательствами. И желательно советскую книгу. В английских часто доказательства не совсем корректные, типа и так понятно.

Монографий советского времени я не знаю по этой теме. Наверное, потому, что в то время теория только формировалась. Можно посмотреть оригинальные статьи Колмогорова, Маркова, Карацубы, Бардзиня, Лупанова...
В качестве введения в тему могу посоветовать учебник моего научного руководителя: Алексеев В.Б. Введение в теорию сложности алгоритмов.

В советские времена она СФормировалась и более ее никто не трогал. Мозгов не хватало. Сейчас пожинаем плоды. Не могем даже процессор приличный сделать. Intel позорится с многоядерностью. Мы чуть круче, но тоже звезд с неба не хватаем...

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

[Xaositect]

st256 в сообщении #242495 писал(а):

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

Зря думаете, что не опускался
Именно Колмогоров поставил задачу: доказать или опровергнуть гипотезу: нельзя произвести умножение двух $n$-значных чисел быстрее, чем за $n^2$.
Ученик Колмогорова Карацуба доказал, что она не верна и построил алгоритм, перемножающий их за $O(n^{\log_2 7})$. Тоом, будучи школьником, обобщил метод Карацубы и улучшил оценку до $O(n^{1+\varepsilon})$.
Немцы Шёнхаге и Штрассен применили к этой задаче преобразование Фурье и получили оценку $O(n\log n\log \log n)$. Это было давно - кажется, в 60-х годах.
А в позапрошлом году их алгоритм улучшил Фюрер, получив верхнюю оценку $O(n\log n 2^{O(\log^* n)})$.

С нижними оценками все сложнее. Тривиальную оценку $2n$ вроде так и не улучшили.
Если как-то ограничивать свойства алгоритмов, то можно получить оценки порядка $n\log n$ (результаты Пападимириу и еще какие-то, в разных направлениях).

-- Пт сен 11, 2009 22:36:40 --

Сейчас у немцев сильные группы в этой области. Они(еще Штрассен) начали на этом поле серьезно использовать абстрактную алгебру. Наша кафедра собтрудничает с группой Blaser'а сейчас. Есть еще группа Burgisser'а
А американская Computer Science сейчас в основном концентрируется на $P$ vs $NP$. Лично мне это направление не кажется интересным, алгебраическая сложность - гораздо более красивый подход.

-- Пт сен 11, 2009 22:39:46 --

st256 в сообщении #242495 писал(а):

вот мне бы теоремку, что тот или иной алгоритм является самым быстрым в операциях сложения и умножения. Так нет такой теоремки ((

Для сумматоров есть такая теоремка. Минимальный по сложности сумматор требует $5n-3$ битовых операций. А для глубины схемы есть асимптотическая оценка $\log n$. Посмотрите вот эту статью, там есть ссылки: http://www.mathnet.ru/php/archive.phtml ... n_lang=rus
Для умножения все гораздо сложнее. Если Вы серьезно этим хотите заниматься - посмотрите все-таки Algebraic Complexity Theory. Очень хорошая книга.

[st256]

Xaositect в сообщении #242500 писал(а):

[quote="st256 в Зря думаете, что не опускался
Именно Колмогоров поставил задачу: доказать или опровергнуть гипотезу: нельзя произвести умножение двух $n$-значных чисел быстрее, чем за $n^2$.

Вот-вот... После этой статьи (Карацуба, что ли ее написал) мы у себя в универе поставили на наследии Колмогорова жирный крест... Не в том смысле, что мы его не уважаем. Мы его результаты применить не можем. Битовые дела на процессорах не работают. Там умножения и сложения - равноценные операции. С битовой точки зрения, понятно это дело совсем не так. А у нас - так

Мы мало интересуемся оценками. Почему, это долгий разговор. Кстати, и лукавыми алгоритмами типа Винограда (это когда сложения не учитывают). Мы деятели от сохи. Реализовать Винограда на проце - дохлый номер... Что б окончательно добить Израильского товарища, скажу, что я дискретную свертку (фильтрацию) могу делать за одно умножение на отсчет

Кстати, а кто Вы и откуда?

[Xaositect]

st256 в сообщении #242505 писал(а):

Кстати, а кто Вы и откуда?

Я с кафедры математической кибернетики ВМК МГУ. Пятикурсник.

На микросхемах, согласен, часто асимптотически оптимальные оценки часто не имеют смысла. Но статью про сумматоры посмотрите - там точка зрения приближена к практической.

[maxal]

О сложности логических схем есть также довольно популярная статья:
Н.В.Верещагин, А.Шень "Логические формулы и схемы"
http://www.mccme.ru/free-books/matpros5.html или http://mi.mathnet.ru/mp57

[Xaositect]

st256 в сообщении #242505 писал(а):

Что б окончательно добить Израильского товарища, скажу, что я дискретную свертку (фильтрацию) могу делать за одно умножение на отсчет

Я, кстати, плохо понял эту фразу. Можете пояснить конкретнее?

[st256]

maxal в сообщении #242508 писал(а):

О сложности логических схем есть также довольно популярная статья:
Н.В.Верещагин, А.Шень "Логические формулы и схемы"
http://www.mccme.ru/free-books/matpros5.html или http://mi.mathnet.ru/mp57

Увы! Это то, что у нас как раз не работает

-- Сб сен 12, 2009 00:17:39 --

Xaositect в сообщении #242510 писал(а):

st256 в сообщении #242505 писал(а):

Что б окончательно добить Израильского товарища, скажу, что я дискретную свертку (фильтрацию) могу делать за одно умножение на отсчет

Я, кстати, плохо понял эту фразу. Можете пояснить конкретнее?

Обычно в цифровых сигнальных процессорах свертка вычисляется так (думаю, Вы это знаете):
$Y_n = a_0 X_n + a_1 X_{n-1}+ a_2 X_{n-2} + ... + a_N X_{n-N}$
$Y_{n+1} = a_0 X_{n+1} + a_1 X_{n}+ a_2 X_{n-1} + ... + a_N X_{n-N+1}$
$Y_{n+2} = a_0 X_{n+2} + a_1 X_{n+1}+ a_2 X_{n} + ... + a_N X_{n-N+2}$
....
Т.е. вроде, как получается если сворачивать входную последовательность с последовательностью длины $N+1$, то необходимо $N+1$ умножений на отсчет. Я ж могу выполнить эту свертку за... одно перемножение на отсчет. Причем совершенно честное. Т.е. я не буду расписывать умножения как несколько сложений.

[Xaositect]

st256 в сообщении #242513 писал(а):

Т.е. вроде, как получается если сворачивать входную последовательность с последовательностью длины , то необходимо $N+1$ умножений на отсчет. Я ж могу выполнить эту свертку за... одно перемножение на отсчет. Причем совершенно честное. Т.е. я не буду расписывать умножения как несколько сложений.

Интересно. Я сходу не могу придумать, как это сделать.

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