Su Algoritmo di Problemi: Somma di Polinomi

Su un Algoritmo di Analisi dei Problemi di alcuni interessanti algoritmo di problemi di linea popolare giudici Pagine mercoledì, 18 luglio 2012 la Somma di Polinomi Problema Nome:
come risolvere sommatorie

Analisi di alcuni interessanti algoritmo di problemi da giudici popolari online

Pagine

Mercoledì, 18 Luglio 2012

Somma di Polinomi

Problema Nome: Somma di Polinomi
UVa ID: 10302
Parole chiave: finito il calcolo, la matematica

Io sono una vera delizia per te, oggi. Io sono entusiasta di avere l’opportunità di scrivere su un argomento affascinante ho appena imparato a conoscere molto di recente. Questo post dovrebbe essere circa il problema 10302 da UVa archivi, ma non è semplicemente la soluzione specifica al problema, che è piuttosto banale, ma la teoria dietro di esso, che viene introdotto nella descrizione del problema.

Tutto è iniziato quando ho letto di questo problema per la prima volta. Se ancora non lo hai fatto, ti suggerisco di andare avanti e leggere ora. Leggere un paio di volte, se necessario…

Pronto? Va bene, hai trovato nulla di particolarmente interessante? Se sei riuscito a capire perfettamente tutto ciò che viene detto lì, ti saluto, sei un vero gentiluomo e uno studioso. Personalmente, ho trovato la descrizione del problema un po ‘ di confusione, e il sottile errori (avete notato qualcosa di divertente nella definizione di fattoriale polinomio?) non ha aiutato. Tuttavia, i concetti descritti, c’era qualche strano fascino per me, così mi ha spinto a fare qualche ricerca per conto mio. Sono così felice che ho fatto! Mi ha permesso di conoscere questa bellissima area della matematica che si potrebbe chiamare finito di calcolo (o discreta calcolo).

Prima di proseguire, vediamo rapidamente ricordare che la soluzione a questo problema consiste semplicemente calcolare l’espressione:

Una semplice ricerca per “somma consecutivo di poteri” porta innumerevoli documenti che presentano la forma chiusa espressione di una valutazione di questa somma:

Torneremo più avanti; per ora, continuiamo con l’argomento a portata di mano.

Finito di Calcolo – Calcolo per gli informatici

Naturalmente, le persone possono essere in disaccordo con questo, ma mi sembra che se avete qualche interesse in informatica, c’è una buona probabilità che troverete finito calcolo profondamente affascinante. Per me, questo è un altro esempio di qualcosa che mi ha fatto pensare: “perché non mi insegnano a scuola?!”. Magari finito il calcolo è nulla di nuovo per voi, e se è il caso, questo post sarà una specie di noioso, ma se la vostra formazione accademica, era un po ‘ simile al mio, hai imparato a conoscere il “tradizionale” rami di analisi i: calcolo differenziale e integrale —di cui parleremo semplicemente di fare riferimento a come “infinito calcolo” da qui— ma non si è mai sentito finito di calcolo.

Bene, io non sto sostenendo che questo articolo vi insegnerà tutto ciò che c’è da sapere su di esso, ma può essere un buon punto di partenza. Cominciamo con le basi; come suggerisce il loro nome, infinito di calcolo e calcoli sono finiti sotto-campi di Calcolo, ma si differenziano tra loro in un modo fondamentale. Infinito di calcolo riguarda le curve, le somme di infiniti termini e le funzioni che esiste nel campo dei numeri reali, mentre finite di calcolo è più interessato in sequenze, le somme di un numero finito di termini e funzioni che vivono nello spazio dei numeri interi. La figura seguente semplifica troppo le cose, ma illustra il tipo di cose che ogni tipo di calcolo messa a fuoco:

Uno dei più emblematici esempi di una funzione rilevante per la nostra discussione, che si manifesta frequentemente in informatica e matematica discreta, in generale, è la somma dei primi \(n\) numeri interi positivi:

Infatti, direi che se stai leggendo queste righe, è molto probabile che si conosce già l’equazione di cui sopra, dal cuore (e, forse, proprio come probabilmente avete sentito la storia affascinante dei giovani di Gauss e come ha stupito la sua insegnante, utilizzando un brillante ragionamento relative a tale formula). Tuttavia, si può dire che si sono ugualmente in grado di formulare espressioni in forma chiusa per le seguenti somme, senza alcun aiuto da libri o da altre fonti?

Beh, se sono attualmente in grado di rispondere affermativamente, gioire, dato che si sta per imparare un bel approccio per affrontare questi problemi. Voglio sottolineare che questo articolo è pensato per essere una semplice introduzione al finito il calcolo, ma si può trovare una più completa documento nel tutorial fa riferimento alla fine. Ti consiglio vivamente di leggere nella sua interezza per una spiegazione più dettagliata su molte delle cose di cui abbiamo parlato qui.

Definizioni

Let’s get started (ora!). Quello che vediamo qui è che, anche se le definizioni di base finito di calcolo sono necessariamente diverso le cose che si sanno già da infinito di calcolo, sono strettamente connesse con la loro infinita controparti. A causa di questo, se si conosce già le basi di infinito, di calcolo, di apprendimento finito di calcolo, sarà un gioco da ragazzi.

Iniziamo con le discrete derivati:

In matematica discreta, il più vicino si può arrivare a 0 (da destra) senza toccarlo è 1, che ci dà la semplice espressione di cui sopra. \(\Delta\) è la differenza finito operatore, che in questo caso rappresenta semplicemente la differenza tra il valore di una funzione valutata a un certo punto \(x\), e il suo valore quando valutate un gradino al di sopra \(x\). Questo dovrebbe dare un’idea del motivo per cui la descrizione del problema, si parla di “anti-differenze”, e perché la sua definizione l’aspetto che fa.

Avanti, andiamo a vedere uno dei più operazioni di base che verrà utilizzato più volte da ora in poi, l’elevamento a potenza o funzione “power”:

Che cosa è \(x^\sottolineare\)? Si tratta di un “calo di potenza” (la descrizione del problema, la chiama fattoriale polinomiale):

Perché utilizzare ad uno strano tipo di “potere”? Bene, diventerà evidente quando si vede come i “derivati” di polinomi lavoro finito calcolo:

Non è pulito? Ora che abbiamo coperto la base di finita “calcolo differenziale”, vediamo un po ‘ di finita “calcolo integrale”, che è ciò che faremo, in definitiva, si applicano per risolvere la sommatoria formulato in precedenza.

Una funzione \(g(x)\) è chiamato discreto anti-derivati, o anti-differenza di \(f(x)\) se \(\Delta g(x) = f(x)\):

Qui ho scelto di \(\Delta^<-1>\) per indicare il discreto anti–derivati. Una diversa notazione è usata nel tutorial fa riferimento alla fine, ma il significato è lo stesso. Si noti che le somiglianze con infinita calcolo ancora in possesso di:

L’ultimo elemento fondamentale è quello di formulare qualcosa di simile per il teorema fondamentale del calcolo, ma per il discreto mondo:

Dove \(F(x)\) rappresenta l’anti–derivati di \(f(x)\). Tutti questi elementi danno l’uso di strumenti sufficienti per affrontare il nostro problema originale, ma prima di passare agli esempi, voglio parlare di un paio di più le proprietà e le relazioni che sono eleganti e discreti controparti (clicca sull’immagine).

Trovo particolarmente interessante che il discreto controparte di \(e\) è 2. Se siete in informatica, non ho bisogno di spiegare come perfetto.

Ha Lavorato Esempio #1

Va bene, cerchiamo di applicare tutto questo in teoria è un problema reale. Torniamo alla nostra originaria di somma:

Come risolvere questo problema? Beh, il fondamentale teorema ci dice che se sapevamo che l’anti–differenza di \(x^3\) (let’s call it \(g(x)\)), quindi il calcolo della somma sarebbe una questione di valutazione di \(g(n+1) – g(1)\).

Ma per trovare \(g(x)\), prima sarebbe comodo se si potesse express \(x^3\) come somma delle cadute di poteri (un fattoriale polinomiale):

Con questo, la ricerca di anti–differenza è molto semplice:

Verifica che \(g(n+1)-g(1)\) è uguale alla forma chiusa formula presentato all’inizio di questo articolo è lasciato come esercizio per il lettore.

Ha Lavorato Esempio #2

Consideriamo ora la seguente sommatoria (preso dal tutorial a cui fa seguito), che illustra l’utilizzo di “integrazione per parti” finita calcolo:

L’osservazione chiave qui è che, grazie alla moltiplicazione dei derivati di proprietà, siamo in grado di formulare la seguente relazione —di nuovo, si noti la somiglianza con infinita calcolo:

Scegliamo \(u(x)=x\) e \(\Delta v(x)=2^x\), che ci aiuta a trovare l’anti–differenza che si desidera:

Trovare l’espressione in forma chiusa per la somma ora è banale:

Veramente bello, non è vero?

Siamo giunti al termine di questa breve introduzione al mondo di discreta calcolo, e tutto ciò che è di sinistra, per me, è per ringraziare il problema setter per la scrittura di questo problema in particolare per introdurre molti di noi a questi affascinanti idee matematiche. Vedi? Questo è uno dei motivi per cui amo algoritmo di risoluzione di problemi; una volta ogni tanto ci si imbatte in un gioiello come questo che ti aiuta a imparare le nuove ed emozionanti, e non sta imparando il punto di tutto questo? 🙂

Leave a Reply

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *