Математическая логика и теория алгоритмов. Стенюшкина В.А. - 92 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

причём степень R(x) меньше степени P
2
(x).
Доказательство Применим метод математической индукции по степени
делимого
P
1
(x). Если P
1
(x)=0 или его степень меньше P
2
(x), то (5.2) выполняет-
ся для
Q(x)=0 и R(x)=P
1
(x). Если P
1
(x)
≠
0, то
∧
P
1
(x)=
∧
P
2
(x)+k, k
≥
0 (
∧
− знак сте-
пени многочлена). Образуем полином
P
′
?
(x)=P
1
(x)-(a
m
/b
n
) x
k
P
2
(x). Очевидно,
∧
P
′
?
(x)<
∧
P
?
(x). Теперь, если
∧
P
′
?
(x)=0 или
∧
P
′
?
(x)>
∧
P
2
(x), то существование до-
казано; в противном случае по предположению метода имеет место разложение
типа (6.2), то есть
P
′
?
(x)=
P
2
(x)Q
0
(x)+R(x) для некоторых Q
0
(x) и R(x) с неравен-
ством
∧
R(x)<
∧
P
2
(x). Из построения
P
′
?
(x) находим в этом случае P
?
(x)=
P
2
(x)
(Q
0
(x)+(a
m
/b
n
)x
k
)+R(x), что доказывает существование Q(x) и R(x). Эти полино-
мы входят в кольцо
J[x], при этом либо R(x)=0, либо
∧
R(x)<
∧
P
2
(x). Единствен-
ность доказываем от противного. Если, кроме
Q(x), R(x), существуют Q
1
(x),
R
1
(x), удовлетворяющие условию (6.2). Путём вычитания равенств типа (6.2)
находим
R(x)-R
1
(x)=P
2
(x)(Q
1
(x)-Q(x)), откуда P
2
(x)/(R(x)-R
1
(x)), что возможно
лишь при
R(x)=R
1
(x), и затем Q(x)=Q
1
(x). Теорема доказана.
Примечание Если
J-поле, то коэффициент b
n
обратим.
5.3 Полиномиальное деление с остатком
Алгоритм PDF
Вход: P
1
(x)=
i
m
i
i
xa
∑
=0
, P
2
(x)=
i
n
i
i
xb
∑
=0
над полем, m≥n≥0, b≠0.
Выход: Q(x)=
i
nm
i
i
xq
∑
−
=0
, R(x)=
i
n
i
i
xr
∑
−
=
1
0
, удовлетворяющие основной теореме.
Шаги алгоритма:
1 Для
k от (m-n) до 0 выполнять
Q
k
:=a
n+k
/b
n
для
j от (n+k-1) до k выполнять
a
i
:=a
i
-q
k
b
j-k
{Основной цикл}
2 Вернуть
q
i
, i=0..(m-n) {Коэффициенты полинома Q(x), вычисленного
на шаге
1} и r
i
=c
i
, i=0..(n-1){Коэффициенты полинома R(x), вычисленные по c
i
,
i=0..(n-1)
на шаге 1}
{Выход}
Пример - Пусть
P(x)=7x
5
+4x
3
+2x+1, P
2
(x)=x
3
+2 –полиномы с целыми
коэффициентами. Так как старший коэффициент
P
2
(x) обратим, можно приме-
нить PDF. (Алгоритм работает над областью целостности J при условии, что
b
n
обратим в J). Опуская запись степеней x, имеем:
704 0
21
700 14
10
02 
         причём степень R(x) меньше степени P2(x).
         Доказательство Применим метод математической индукции по степени
делимого P1(x). Если P1(x)=0 или его степень меньше P2(x), то (5.2) выполняет-
ся для Q(x)=0 и R(x)=P1(x). Если P1(x) ≠0, то ∧P1(x)= ∧P2(x)+k, k≥0 (∧ − знак сте-
пени многочлена). Образуем полином P′?(x)=P1(x)-(am /bn ) xk P2(x). Очевидно,
∧
  P′?(x)< ∧P?(x). Теперь, если ∧P′?(x)=0 или ∧P′?(x)> ∧P2(x), то существование до-
казано; в противном случае по предположению метода имеет место разложение
типа (6.2), то есть P′?(x)= P2(x)Q0(x)+R(x) для некоторых Q0(x) и R(x) с неравен-
ством ∧R(x)< ∧P2(x). Из построения P′?(x) находим в этом случае P?(x)= P2(x)
(Q0(x)+(am/bn )xk)+R(x), что доказывает существование Q(x) и R(x). Эти полино-
мы входят в кольцо J[x], при этом либо R(x)=0, либо ∧R(x)< ∧P2(x). Единствен-
ность доказываем от противного. Если, кроме Q(x), R(x), существуют Q1(x),
R1(x), удовлетворяющие условию (6.2). Путём вычитания равенств типа (6.2)
находим R(x)-R1(x)=P2(x)(Q1(x)-Q(x)), откуда P2(x)/(R(x)-R1(x)), что возможно
лишь при R(x)=R1(x), и затем Q(x)=Q1(x). Теорема доказана.
         Примечание Если J-поле, то коэффициент bn обратим.

       5.3 Полиномиальное деление с остатком

       Алгоритм PDF
                     m                     n
       Вход: P1(x)= ∑ ai x i , P2(x)= ∑ bi x i над полем, m≥n≥0, b≠0.
                     i =0                 i =0
                        m−n                 n −1
       Выход: Q(x)= ∑ qi x i , R(x)= ∑ ri x i , удовлетворяющие основной теореме.
                         i =0              i =0

        Шаги алгоритма:
        1 Для k от (m-n) до 0 выполнять
        Qk:=an+k/bn
        для j от (n+k-1) до k выполнять
        ai:=ai-qkbj-k
{Основной цикл}
        2 Вернуть qi, i=0..(m-n) {Коэффициенты полинома Q(x), вычисленного
на шаге 1} и ri=ci, i=0..(n-1){Коэффициенты полинома R(x), вычисленные по ci,
i=0..(n-1)                      на                шаге                    1}
{Выход}
        Пример - Пусть P(x)=7x5+4x3+2x+1, P2(x)=x3+2 –полиномы с целыми
коэффициентами. Так как старший коэффициент P2(x) обратим, можно приме-
нить PDF. (Алгоритм работает над областью целостности J при условии, что bn
обратим в J). Опуская запись степеней x, имеем:


               704 0                 10
        21                      02
               700 14

Страницы