[Тупняк]Степень полинома

это вопрос?

о_О

да

Казалось бы, причем тут К.О.? Или тут в чем-то подвох?

Да.

>да

да. но если ты имеешь в виду кольцо полиномов по модулю приведенного многочлена, то нет

Хорошо. Тогда помогите осознать такую фразу, взятую из перевода одной очень известной книги:

«Если A(x) и B(x) - полиномы степени не выше n, их произведением (product) С(х) является полином степени не выше 2n - 1, такой что C(x) = A(x)B(x) для всех x из соответствующего поля.»

«Не выше n», значит самая большая степень есть n, и тогда утверждение «не выше 2n - 1» ложно.

> всех x из соответствующего поля.
Думаю, разгадка здесь.

потому что с 0 нумерация

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

>потому что с 0 нумерация

Какая разница, откуда нумерация? Старший член полинома степени n есть A*x^n, старший член полинома степени 2n - 1 есть C*x^(2n - 1)...

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

Не знаю, что значит «хитрое множество», но здесь (Кормэн, Лейзерсон, Ривест, Штайн) ничего сложнее комплексных чисел не вижу.

Значит, очепятка в (2n-1).

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

мда... надо бы в оригинале посмотреть. Только вот где его взять...

http://mitpress.mit.edu/algorithms/ нет этой страницы?

Да, ссылка хорошая. Но у меня перевод 2-го издания, а ссылка на errata на странице 2-го издания отправляет на 3-е издание, а там 30-й главы вообще нет в «проблемном» списке.

Просмотрщик amazon.com очень аккуратно отключает возможность просмотра результатов поиска с определением, содержание - пожалуйста, индекс - извольте, но не текст главы...

Кстати, далее по тексту написано вот это:

«Заметим, что degree(C) = degree(A) + degree(B), откуда вытекает, что если A - полином степени не выше Na, а В - полином степени не выше Nb, то С - полином степени не выше Na + Nb - 1. Тем не менее, поскольку полином степени не выше k является также полиномом степени не выше k + 1, мы будем говорить, что произведение С является полиномом степени не выше Na + Nb.»

...

Здесь неправильный перевод. В оригинале предложение звучит по-другому:

For polynomial multiplication, if A(x) and B(x) are polynomials of degree-bound n, we say that their product C(x) is a polynomial of degree-bound 2n — 1 such that C(x) = A(x)B(x) for all x in the underlying field.

Any integer strictly greater than the degree of a polynomial is a degree-bound of that polynomial. Therefore, the degree of a polynomial of degree-bound n may be any integer between 0 and n — 1, inclusive.

Похоже, они действительно степень полинома определяют как-то по-своему :) Как уже говорили выше, если считать с нуля, т.е. «наш» полином степени N обзывать «их» полиномом степени M=N+1, то «наш» полином степени 2N превратится в «их» полином степени 2N+1, т.е. 2M-1.

(Оригинал можно найти здесь: http://lib.homelinux.org)

Вот, так оно и есть.

>Здесь неправильный перевод.

Ёжкин кот! ведь до этого в переводе приводился термин «граница степени» (degree-bound), но потом слово «граница» куда-то исчезло. И как, спрашивается, после этого покупать переведённые книги? Кот в мешке получается...

> И как, спрашивается, после этого покупать переведённые книги? Кот в мешке получается...

Переводные, издательства «Мир», выпущенные примерно до 1993 года покупать, а главное читать, можно.

А кто сказал, что степени полиномов должны совпадать? Не выше n - значит pow(A(x)) <= n && pow(B(x)) <= n. Тогда если, скажем pow(A(x)) = n -1, а pow(B(x)) = n, то pow(C(x) = A(x)*B(x)) = pow(A(x)) + pow(B(x)) = 2n - 1.

Еще вопросы?

С уважением, математик-кун.