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!