[es] - podijeli pa vladaj algoritam

bbosnjak
Brankica Bošnjak
student

Član broj: 198700
Poruke: 2
*.mathos.hr.

Profil

^{24.10.2008. u 13:55 - pre 200 meseci}

Zanima me "podijeli-pa-vladaj" algoritam za mnozenje 2 polinoma stupnja n.
Znam samo da mnozenje 2 polinoma stupnja n svedem na vise mnozenja polinoma stupnja n=2. Radi jednostavnosti promatram n kao potenciju broja 2.
Ideje? hvala...

Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*

+1 Profil

Re: "podijeli pa vladaj "algoritam

^{24.10.2008. u 14:19 - pre 200 meseci}

Problem koji si naveo licno ne bih resavao D&C metodom.
Ne izgleda mi prirodno.

Samo mnozenje polinoma je relativno jednostavno.

Pretpostavimo da su polinomi zapisani kao n realnih vrednosti u nizu
(koeficijenti polinoma)

Imajuci dva takva niza, p1, i=0..n i p2[j], j=0..m (p1 i p2 su nizovi koji
predstavljaju polinome p1 i p2 stepena n i m respektivno, a p1 je koeficijent
uz i-ti stepen u polinomu p1)

resenje se dobija tako sto se oformi niz p[k],k=0..n+m, inicijalizuje na 0
svaki clan niza p[k] = 0 i zatim
dvostrukom petljom

Code:

  for i = 0 .. n do
     for j = 0 .. m do
        p[i+j] = p[i+j] + p1[i]*p2[j]

odrede koeficijenti polinoma p umnoshka p1 i p2 (p=p1*p2)

D&C metoda pretpostavlja da se problem moze reshiti svodjenjem na
isti problem manje kompleksnosti dok se ne dodje do trivijalnog resenja

pogledaj http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm za referencu

Eventualna implementacija bi mozda bila:
(razbijanje gornje petlje na)

mnozenje polinoma jednostavnim polinomom sa jednim koeficijentom
nesto po sledecoj formuli:

p = pt1+pt2+ ... +ptm

gde je ptq = p1*p2[q], q = 0..m
ili drugim recima, podeli p2 na sumu polinoma gde je svaki polinom zapravo jedan stepen u polinomu p2
i sa svakim od tih mini polinoma pomnozi p1 i saberi ih.

znaci ako je p1 = x2 + 3*x +4 a p2 = 2*x4 - 7*x3 + 3x + 2

onda je rezultat
p = (x2+3*x+4) * (2)+
(x2+3*x+4) * (3x)+
(x2+3*x+4) * (-7*x3)+
(x2+3*x+4) * (2*x4)

Ali i dalje mi to ne izgleda kao prirodna implementacija D&C
Ako neko ima bolju ideju, nadam se da ce je izneti