Tema
Registracija

"podijeli pa vladaj "algoritam

Odgovori Nova tema
Štampanje RSS teme Kopiraj vezu do teme Podeli na Facebook-u Podeli na X-u (Twitter) Idi na poslednju poruku
  • 2 odgovora
  • 3.529 pregleda
"podijeli pa vladaj "algoritam 24.10.2008. u 13:55 · pre 219 meseci #1
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...
Re: "podijeli pa vladaj "algoritam 24.10.2008. u 14:19 · pre 219 meseci #2
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
Re: "podijeli pa vladaj "algoritam 26.11.2008. u 20:45 · pre 218 meseci #3
Da, mozenje dva polinoma mozes uraditi na taj nacin.
Ukoliko bi imao polinom P(x)=p_0 + p_1 x + p_2 x^2 + \ldots p_n x^n njega mozes predstaviti kao P(x) = P_1(x) + P_2(x)x^{n/2} gde je
P_1(x) = p_0 + p_1 x + \ldots + p_{n/2 - 1} x^{n/2 - 1} i P_2(x) = p_{n/2} + p_{n/2 + 1} x + \ldots + p_n x^{n/2}

Na ovaj nacin bi mnozenje dva polinoma stepena n sve na mnozenje po 4 polinoma stepena n/2. Slozenost naivne interpretacije ovog bi opet dovela do slozenosti koja je O(n^2) medjutim mozes primetiti da se jedan od tih sabiraka moze dobiti preko drugih pa dobija sa je slozenost O(n^{log_2 3}).

Mnozenje dva polinoma mozes implementirati preko Fast Fourier transform (FFT) u slozenosti O(n \times \log{n}) koji se takodje svodi na metodu "podeli pa vladaj".
Potpis
Math is like love. A simple idea but it can get complicated.
Odgovori
Prijavite se da biste odgovorili u ovoj temi.PrijavaRegistracija

Premeštanje teme