Moltiplicazione di polinomi

Messaggioda Ambaraba » 23/01/2018, 11:56

Ciao a tutti!

Da qualche settimana sto seguendo un corso introduttivo sugli algoritmi offerto da Coursera https://www.coursera.org/learn/algorithmic-toolbox.
Tutto procedeva faticosamente e lentamente bene, finché non mi sono imbattuto in una lezione che tratta l'implementazione di un algoritmo divide et impera per la moltiplicazione di due polinomi.

Nello specifico, il mio cruccio sta nel fatto che per poterlo implementare entrambe i polinomi, \(\ A(x) \) e \(\ B(x) \), devono essere divisi in due parti e questo è proprio il passaggio che non capisco.
Ecco a una descrizione più dettagliata prendendo in considerazione un ipotetico polinomio \(\ A(x) \):

\(\ A(x) = D_1(x) x^{n/2} + D_0(x) \)

dove \(\ D_1(x) \) e \(\ D_0(x) \) sono:
\(\ D_1(x) = a_{n-1}x^{n/2-1} + a_{n-2}x^{n/2-2} + ... + a_{n/2} \)
\(\ D_0(x) = a_{n/2-1}x^{n/2-1} + a_{n/2-2}x^{n/2-2} + ... + a_0 \)

Non mi è assolutamente chiaro come si proceda per dividere \(\ A(x) \) in due parti...
La pagina di Wikipedia dedicata all'algoritmo di Karatsuba descrive, prima di passare all'algoritmo vero e proprio, un procedimento simile applicato ai numeri anziché ai polinomi https://en.wikipedia.org/wiki/Karatsuba_algorithm; mi è vagamente più chiaro anche se non riesco a capirlo del tutto.

Mi scuso per la banalità della domanda e per la poca precisione con cui ho esposto il problema, purtroppo provengo da un percorso di stampo linguistico e l'ultima matematica che ho visto è stata quella dell'esame di maturità nel lontano 2008.
Spero che qualcuno riesca a trovare la pazienza e la voglia di aiutarmi a capire, nei termini più semplici possibili, ciò che sta accadendo.

Grazie a tutti!
Ambaraba
Starting Member
Starting Member
 
Messaggio: 2 di 10
Iscritto il: 08/05/2017, 09:53

Re: Moltiplicazione di polinomi

Messaggioda killing_buddha » 24/01/2018, 16:37

Un polinomio ha un grado, diciamo $d$. Se $d$ è pari, puoi rompere il polinomio in $D_0 + x^{d/2}D_1$. Se è dispari, puoi decidere di romperlo al termine $(d-1)/2$ o $(d+1)/2$.
- "Everything in Mathematics that can be categorized, is trivial" (P. J. Freyd), which should be understood as: "category theory is good ideas rather than complicated techniques".
- "I always disliked Analysis" (P. J. Freyd)
Avatar utente
killing_buddha
Cannot live without
Cannot live without
 
Messaggio: 1952 di 5766
Iscritto il: 03/05/2008, 17:33

Re: Moltiplicazione di polinomi

Messaggioda dissonance » 25/01/2018, 10:39

Ci vogliono degli esempi. Provo. Se \(P(x)=1+ 2x+x^2+3x^3+x^4\), allora possiamo dividere \(P\) in due parti come
\[
P(x)=x^2(1+3x+x^2)+1+2x.\]
In questo caso \(D_1(x)=1+3x+x^2, D_0(x)=1+2x\).

Si tratta quindi di raccogliere a fattore comune \(x^{d/2}\) in tutti i monomi di grado uguale o superiore a \(x^{d/2}\).
dissonance
Moderatore
Moderatore
 
Messaggio: 13561 di 27757
Iscritto il: 24/05/2008, 19:39
Località: Nomade


Torna a Pensare un po' di più

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite